Mistake-Bounded Language Generation
arXiv:2605.10809v1 [cs.LG] 11 May 2026
Jon Kleinberg∗ Departments of Computer Science and Information Science Cornell University Ithaca, NY
Charlotte Peale Department of Computer Science Stanford University Stanford, CA
Omer Reingold Department of Computer Science Stanford University Stanford, CA May 12, 2026
Abstract We investigate the learning task of language generation in the limit, but shift focus from the traditional time-of-last-mistake metric of a generator’s success to a new notion of mistake-bounded generation. While existing results for language generation in the limit focus on guaranteeing eventual consistency, they are blind to the cumulative error incurred during the learning process. We address this by shifting the goal to minimizing the total number of invalid elements output by a generation algorithm. We establish a formal reduction to the Learning from Correct Demonstrations framework of Joshi et al., enabling a general recipe for deriving mistake bounds via weighted update rules. For finite classes, we provide an algorithm that simultaneously achieves an optimal last-mistake time of Cdim(L) and a mistake bound of ⌊log2 |L|⌋, whereas for the non-uniform setting of countably infinite streams of languages, we prove a fundamental trade-off: achieving logarithmic mistakes O(log i) necessarily precludes convergence guarantees established in prior work. Finally, we show that our framework can be extended to accommodate noisy adversaries and guarantee mistake bounds that scale with the adversary’s suboptimality.
1
Introduction
The capability of Large Language Models (LLMs) to generate coherent text has sparked a renewed interest in the theoretical underpinnings of language generation. While early learning-theoretic work such as Gold and Angluin’s work on language identification in the limit [Gold, 1967, Angluin, 1980] focused on the difficult task of identifying a language or grammar from positive samples, recent work by Kleinberg and Mullainathan [2024] hinges on the observation that a successful large language model need not fully identify its language of interest, but simply understand enough to generate new, valid examples from the language. This idea has been explored through the model of language generation in the limit, first proposed by Kleinberg and Mullainathan [2024]. In this setting, a generator plays an online game against an adversary. At each step, the generator must output a new element x̂t that has not yet been outputted by the adversary, and then the adversary reveals a new element xt from a target language L∗ , known to come from some class of languages L. The generator succeeds if it eventually converges to outputting only elements from L∗ . Subsequent work by Li et al. [2024] further refined what it means to eventually converge, dividing the space of language generation requirements into three tiers, listed in order of increasing strength: language generation in the limit, non-uniform generation, and uniform generation. Existing work in all three of these settings quantifies a generator’s success through the time-of-last-mistake, i.e. the timestep after which the generator always outputs from the target language L∗ . While this metric ∗ Authors listed in alphabetical order.
1
guarantees eventual consistency, it is blind to the cost of learning incurred along the way. A generator could theoretically hallucinate invalid outputs for a million steps before converging, or could generate perfectly for a long time before making a single mistake after a million steps. In both cases, the “time of last mistake” might be identical, yet the practical utility of these two generators is vastly different. The following example shows that this latter case is indeed possible: Example 1 (Separation between time-of-last mistake and number of mistakes.). Consider a language class composed of two languages L = {L1 , L2 }, where |L1 ∩ L2 | = n < ∞. Consider the adversary that enumerates the elements falling in L1 ∩ L2 for the first n timesteps. At timestep tn+1 , there are no unseen elements remaining in the intersection, and thus the generator is forced to output an element in L1 \ L2 or L2 \ L1 . In either case, the adversary can force a mistake by observing the generator’s choice, and then enumerating elements from the other language. Thus, the adversary can force the learner’s time of last mistake to be as large as n + 1. In contrast, if the generator also enumerates L1 ∩ L2 while there are still unseen elements in the intersection, the generator is guaranteed to only make a single mistake at time t = n + 1 when it must play the first point outside of the intersection. Clearly the total number of mistakes is at most the time of the last mistake (since the generator outputs at most one element per time step), but Example 1 shows that the total number of mistakes can be arbitrarily lower: in the example, the time of the last mistake can be arbitrarily high depending on the choice of language class, but the number of mistakes is always bounded by 1. The fact that these two performance metrics operate in different ways raises a fundamental set of questions analogous to the study of mistake bounds in online classification [Littlestone, 1988]: Q1. Are there upper bounds on the total number of mistakes a generator makes for general language classes that are dramatically better than the trivial upper bound inherited from the time of the last mistake? Q2. Does minimizing the total number of mistakes a generator makes require sacrificing optimal guarantees on the time when it makes its last mistake? We investigate this question by studying the interplay between the two metrics of last-mistake-time and total mistakes. While bounding mistakes is valuable on its own, an ideal generator would provide a dual guarantee: minimizing the total volume of errors while also ensuring that the generator converges to the true language as quickly as possible.
1.1
Our Contributions
In this work, we introduce the framework of Mistake-Bounded Language Generation. We demonstrate that while the total number of mistakes is bounded by the time-of-last-mistake, it can be arbitrarily smaller. We provide algorithms that minimize this new metric and prove fundamental trade-offs between minimizing errors and minimizing convergence time. Our primary contributions are: 1. A General Recipe for Mistake-Bounded Generation via Learning from Demonstrations: We prove bounds on the total number of mistakes for language generation by first establishing a formal connection between language generation and the setting of Learning from Correct Demonstrations (LfD) [Joshi et al., 2025]. Leveraging this reduction, we adapt their techniques to provide mistake bounds in the language generation setting. Crucially, while the original LfD technique is restricted to finite classes, we extend the analysis to handle countably infinite language streams through the use of a growth function and non-uniform prior over languages. 2. Optimal Bounds for Finite Classes: For finite language classes, we prove an upper bound of min{log2 |L|, Cdim(L)} on the total mistakes. This directly addresses (Q1) above for the finite class case: While the closure dimension has been shown to tightly govern the optimal time-of-last-mistake for finite classes, our bound shows that we can do dramatically better in terms of total mistakes when log |L| is much smaller than Cdim(L). Furthermore, in response to (Q2) as posed above, we present a hybrid algorithm that simultaneously achieves this mistake bound and the optimal time-of-last-mistake, proving that one need not sacrifice convergence speed to minimize errors in the finite class setting. 2
3. Non-Uniform Bounds and Trade-offs: In Section 6, we apply our general recipe to infinite language classes L = {L1 , L2 , . . . }, deriving a non-uniform mistake bound of O(log i) for the i-th language. This provides a positive answer to (Q1) for the non-uniform setting, but reveals a more nuanced answer to (Q2) than the finite case: here, minimizing mistakes does require sacrificing bounds on the time-of-last-mistake. We formalize this via a fundamental trade-off (Theorem 6.4), proving that any algorithm achieving the nonuniform convergence time guarantees of [Charikar and Pabbaraju, 2024] must suffer a number of mistakes linear in i, whereas our algorithm achieves a logarithmic bound by allowing for a slower convergence time. 4. Robustness to Noise: Finally, we show that our reduction to the LfD setting naturally handles adversarial noise. We give mistake bounds for finite and countably infinite language classes in Lemmas 7.1 and 7.2, respectively, and contrast these results with prior work on last-mistake-time guarantees in the presence of noise.
2
Related Work
Building on Kleinberg and Mullainathan [2024], subsequent work has advanced our understanding of language generation in the limit and investigated various extensions of the model. Li et al. [2024] introduce and study the stronger models of non-uniform and uniform generation, and give characterizations of when these stronger generation goals are possible. Charikar and Pabbaraju [2024] also give a simple algorithm for non-uniform generation that matches and in some cases improves the guarantees of Li et al. [2024], while exploring a number of other variants to the language generation model. Other follow-up works have sought to further understand which classes are and are not generatable. Charikar and Pabbaraju [2025] study the pareto-frontier of non-uniform generation guarantees, while Hanneke et al. [2025] study whether finite unions of generatable classes are guaranteed to satisfy generatability, and answer this in the negative. Anastasopoulos et al. [2026] study a variant termed safe language generation, in which a generator must output elements from the target language while avoiding a subset of harmful elements. Karbasi et al. [2025] consider the problem of auditing a generator to determine whether it is hallucinating. Arenas et al. [2025] study the problem of language generation through a computational lens, and show barriers to computationally-efficient generation in various settings. A significant line of works have considered the possibilities and impossibilities around language generation with breadth, in which a generator must not only output consistent elements, but guarantee eventual “coverage” of the target language according to various definitions Kalavasis et al. [2024, 2025], Charikar and Pabbaraju [2024], Peale et al. [2025], Kleinberg and Wei [2025a,b]. Finally, a last variant that has received significant study is language generation in the presence of noisy adversaries. We overview these works in Section 7.
3
Mistake-Bounded Language Generation
We begin by overviewing the learning task of language generation in the limit, introduced by Kleinberg and Mullainathan [2024]. We will focus on the settings of uniform and non-uniform language generation by Li et al. [2024]. We then define our new notion of mistake-bounded generation, and how it fits into this existing framework. Given a countably infinite universe X , a language generation in the limit problem is defined with respect to a (potentially infinite) language class L, where each language L ∈ L specifies a particular infinite subset of the universe X . When L is a countably infinite class, we assume that it is provided to us in the form of an infinite stream of languages L1 , L2 , ..... The learning task of language generation in the limit is formulated as an online game between a generation algorithm and an adversary. At each timestep t, the generator outputs an element x̂t ∈ X , and then the adversary reveals an element xt ∈ X (See Remark 1 for a note on order-of-play). At each timestep, the generator must operate under the constraint that x̂t cannot be an element that has been previously outputted by the adversary, e.g. x̂t ̸∈ {x1 , ..., xt−1 }. We make the following assumptions about the adversary. First, we assume that the adversary’s outputs realize some language L∗ ∈ L, i.e. there exists an L∗ ∈ L such that xt ∈ L∗ for all timesteps t ∈ N. Second, we assume that each of the adversary’s outputs are unique, i.e. xt ̸∈ {x1 , ..., xt−1 }. See Remark 1 for further discussion about this assumption.
3
At each timestep, the generator gets no information about the identity of the true language L∗ beyond the transcript of elements outputted by the adversary, x1 , ..., xt , which we will denote as x1:t . Nevertheless, the generator is judged by its ability to eventually generate elements from L∗ . The particular notion of eventually is what separates the three tiers of language generation, listed in order of strength: language generation in the limit, non-uniform generation, and uniform generation. In this paper, we focus on the latter two, and define them below. Definition 1 (Non-Uniform Language Generation). A generation algorithm G satisfies non-uniform generation for a language class L if for every L ∈ L, there exists a finite t(G, L) < ∞ such that, when given as input any stream of unique adversarial outputs x1 , x2 , ... realized by L, for all timesteps t ≥ t(G, L), the algorithm is guaranteed to generate from L, i.e. x̂t ∈ L \ {x1:t−1 }. In non-uniform generation, the generator is guaranteed to start generating elements consistent with the true language at some finite timestep. However, the particular timestep where this is guaranteed to happen can be different for each language. This means that it’s possible that even though t(G, L) is finite for each language, maxL∈L t(G, L) is infinite. Uniform generation strengthens the requirement to hold over all languages. In other words, the value of this max expression must be finite: Definition 2 (Uniform Language Generation). A generation algorithm G satisfies uniform generation for a language class L if there exists a time T ∈ N such that for adversarial outputs x1 , x2 , ... realized by a language L ∈ L, for all timesteps t ≥ T the generator is guaranteed to generate from L, i.e. x̂t ∈ L \ {x1:t−1 }. Remark 1. We note two deviations from standard generation setups, both made purely for expositional ease. First, we reverse the standard order of play so that the generator moves first. This choice does not materially affect theoretical guarantees, as any algorithm designed for one setting can be adapted to the other, shifting the total mistake bound or time-of-last-mistake by at most 1. Second, we assume the adversary outputs only unique elements. Existing definitions already measure eventual consistency times (t(G, L) and T ) against the number of unique items seen, preventing the adversary from stalling learning by indefinitely repeating elements. Our setup simply ignores steps where a duplicate is output.
3.1
A new success metric: number of mistakes
One can view the guarantees of uniform and non-uniform generation as providing a bound on the time-of-lastmistake, i.e., the last timestep t where the generator outputs an element that is not part of the true language. As illustrated in Example 1, the total number of mistakes made by the generator can be significantly smaller than the time of last mistake. In this work, we aim to minimize this cumulative error. While for finite classes we simply aim to bound the total mistakes in terms of |L|, for the countably infinite classes considered in Section 6, we require a definition that allows the mistake bound to scale with the complexity (position) of the target language in the stream: Definition 3 (Non-Uniform Mistake Bound). Given a countably infinite language class equipped with a fixed enumeration L = {L1 , L2 , ...}, a generator G and a target language Li , G’s non-uniform mistake bound with respect to Li is defined as the worst-case number of mistakes over all possible streams of unique elements from Li : Mnon-unif (G, i) :=
sup
∞ X 1 G(x1:t ) ∈ / Li .
x1 ,x2 ,···∈Li t=0
Thus, the goal for infinite language classes is to provide a finite bound on Mnon-unif (G, i) for every language Li ∈ L .
4
A General Recipe for Mistake-Bounded Generation
While prior algorithms for language generation in the limit rely on keeping track of which languages are still consistent with the adversarial stream, bounding the total number of mistakes requires a refined approach that not only keeps track of which languages are consistent, but prioritizes generating from languages on which the generator has already made many mistakes.
4
Instead, we adopt a weighted approach derived from a reduction to the "Learning from Correct Demonstrations" (LfD) framework introduced by Joshi et al. [2025]. In Appendix B.3, we show how the problem of language generation can be mapped to the LfD setting. Our core algorithmic strategy builds upon the multiplicative weights update technique proposed by Joshi et al. [2025] for the LfD setting. However, a direct application of their result is insufficient due to the fact that their result only implies mistake bound for finite language classes. The setting of language generation, particularly non-uniform generation, inherently requires handling countably infinite streams of languages. To bridge this gap, we introduce Algorithm 1, which extends the ideas of Joshi et al. [2025] to infinite language classes. This extension requires two new components not present in the original LfD setting: 1. A prior weight distribution w0 : N → R≥0 , representing our initial belief in the likelihood of each language. 2. A growth function f : N → N, which governs the “capacity” of the learner by determining how many languages are actively considered at timestep t. This growth function allows the algorithm to handle infinite streams with finite computational resources. Remark 2. While we present this algorithm in the context of language generation, this extension also yields a novel result for the original LfD setting: it provides the first mistake bounds for learning from infinite streams of reward functions (see Appendix B.3). We show that our algorithm yields the following mistake bound guarantee: Theorem 4.1. For any countably infinite language P∞ class equipped with a fixed enumeration L = {L1 , L2 , ...}, associated weights w0 : N → R≥0 such that i=1 w0 (i) ≤ W < ∞, and non-decreasing growth function f : N → N, the generations outputted by Algorithm 1 guarantee a non-uniform mistake bound of M (G, Li ) ≤ f −1 (i) + ⌊log2 (W/w0 (i))⌋ for each i ∈ N, where if there exists a t′ such that f (t′ ) ≥ i, f −1 (i) is the largest value t such that f (t) < i, or 0 if every for every t′ ∈ N f (t′ ) is at least i, and otherwise f −1 (i) = ∞. The proof (provided in Appendix A) relies on a potential function argument tracking the total weight of the system. Intuitively, every mistake made while Li is the target causes wt (i) to double. However, we also show that the actions taken by the generator ensure that the total weight of the system is bounded, thus preventing wt (i) from doubling indefinitely. In the following sections, we instantiate this recipe with different weights w0 and growth functions f to derive mistake bounds for both finite (Section 5) and infinite (Section 6) classes. Algorithm 1 Non-Uniform Mistake-Bounded Generation algorithm for a provided initial weighting of languages and growth function. Input: Universe X , class L = {L1 , L2 , . . . }, weights w0 : N → R≥0 , growth function f : N → N for t = 1, . . . , ∞ do Pf (t) Output x̂t := arg maxx∈X \x1:t−1 i=1 wt−1 (i)1[x ∈ Li ] Observe adversary’s xt Update weights for i ∈ [f (t)]: xt ∈ / Li 0 wt (i) = wt−1 (i) xt , x̂t ∈ Li 2wt−1 (i) xt ∈ Li , x̂t ∈ / Li Initialize weights for i ∈ {f (t) + 1, . . . , f (t + 1)}: ( w0 (i) wt (i) = 0 end
5
x1:t ⊆ Li otherwise
Generating from Finite Language Classes with log2 |L| mistakes
5
We begin by focusing on the special case of finite language classes. Existing results by Li et al. [2024] and Kleinberg and Mullainathan [2024] have shown that any finite language class is uniformly generatable. Moreover, they prove that the optimal time-of-last-mistake is tightly characterized by the closure dimension. Definition 4. The closure dimension of a language class L is the size of the largest finite intersection of a sub-collection of languages from L: Cdim(L) = max{
\
L : L′ ⊆ L,
L∈L′
\
L < ∞}
L∈L′
While Li et al. [2024] provide an algorithm that guarantees that the last mistake happens by time t = Cdim(L), they also show that this bound is tight: there exist adversarial streams that force the generator to make a mistake at t = Cdim(L). However, this metric does not consider the total number of mistakes made on the way to the time of last mistake.
5.1
A Hybrid Algorithm: Minimizing Mistakes and Convergence Time
We now show that by instantiating our general recipe for mistake-bounded language generation (Algorithm 1) with uniform weights, we can achieve a mistake bound that can be arbitrarily smaller than the closure dimension. Furthermore, we show that our algorithm’s decisions coincide with critical decision points in the uniform generation algorithm of Li et al. [2024], thus satisfying both optimality criteria simultaneously. Let L be a finite class of size N . We instantiate Algorithm 1 with uniform weights w0 (i) = 1 for all Li ∈ L and a static growth function that considers all languages at every point in time: f (t) = N for all t. While this algorithm alone only provides a mistake bound, we show that its actions also satisfy a critical property: whenever the intersection of all consistent languages has infinite size, it plays an unseen element from this intersection. This is exactly the property required by the uniform generation algorithm of Li et al. [2024], and thus we can show that our algorithm also enjoys a last-mistake-time guarantee of Cdim(L). This analysis yields the following dual guarantee: Theorem 5.1. For any finite class L, there exists a generation algorithm that uniformly generates from L and guarantees that for any target L∗ ∈ L and adversarial sequence consistent with L∗ : 1. The total number of mistakes is at most min{⌊log2 |L|⌋, Cdim(L)}. 2. The time of last mistake is at most Cdim(L). This result demonstrates a fundamental separation between our two metrics of total mistakes and time-oflast-mistake. It also recovers the intuition of Example 1, in which the time until the last mistake depended on the closure dimension, |L1 ∩ L2 |, but there was a strategy that preserved this time-of-last-mistake guarantee while only making log2 |L| = 1 mistake. We prove Theorem 5.1 by bringing together two algorithms with different guarantees. In particular, we consider the uniform generation algorithm proposed by Li et al. [2024] that guarantees a last-mistake-time upper-bounded by Cdim(L), but not necessarily any bound on the total number of mistakes, and the algorithm for finite language classes that we obtain via a reduction to Joshi et al. [2025], which upper-bounds the number of mistakes by log2 |L|, but gives no guarantee on the last mistake time. We show that our mistake-bounded algorithm can be viewed as a sharpened version of the uniform generation algorithm of Li et al. [2024], which coincides with the uniform generation algorithm at critical points, but makes smart decisions when there is leeway between which points to choose to still ensure the time-of-last-mistake guarantee. We are thus able to combine the guarantees of both algorithms, and guarantee that the time-of-last-mistake is bounded by Cdim(L), while simultaneously guaranteeing that the total number of mistakes is at most log2 |L|. Because the time-of-last-mistake is also an upper bound on the total number of mistakes, we can improve the total mistake bound to min{log2 |L|, Cdim(L)} when the closure dimension is small.
6
Algorithm 2 Uniform Generation Algorithm proposed by Li et al. [2024], Kleinberg and Mullainathan [2024] Input: Universe X , finite class L for t = 1, . . . , ∞ do Compute C = {L ∈ L : x1:t−1 ⊆ L}. T T If | L∈C L \ x1:t−1 | > 0, output x̂t ∈ L∈C L \ x1:t−1 . (1) Otherwise, output an arbitrary xˆt ∈ X \ x1:t−1 . end
Theorem 5.2 (Uniform Generation Guarantee). [Kleinberg and Mullainathan, 2024, Li et al., 2024, ((2.2), Lemma 2.3, resp.)] For any finite class L and adversarial sequence of unique outputs consistent with L ∈ L, the generator specified by Algorithm 2 has a last mistake time of at most Cdim(L). We highlight line (1) of Algorithm 2 as the key step necessary to obtain the last mistake time guarantee. Note that all other decisions made by the algorithm are completely arbitrary. This idea will be used to prove Theorem 5.1. In particular, we will give a mistake-bounded algorithm, and then show that it is consistent with the decisions of Algorithm 2 and thus also guarantees a last-mistake-time of Cdim(L). We are now ready to prove Theorem 5.1. Proof of Theorem 5.1. Denote L = L1 , ..., Lk , where k = |L|. We instantiate Algorithm 1 with w0 (i) = 1 for all i ∈ [k], and f (t) = k for all t ≥ 1. Thus, note that f −1 (i) = 0 for all i ∈ [k]. By Theorem 4.1, under this instantiation, the algorithm is guaranteed to make at most ⌊log2 k⌋ mistakes on any adversarial stream consistent with some L ∈ L. We now consider the time of last mistake bound. Due to the guarantees of Algorithm 2, it suffices to T show that at any timestep t such that C = {L ∈ L : x1:t−1 ⊆ L} and | L∈C L \ x1:t−1 | > 0, the x̂t output by our T mistake-bounded algorithm, Algorithm 1, with the specified weight and growth functions, satisfies x̂t ∈ L∈C L \ x1:t−1 . We note that by definition of our algorithm, for any Li ̸∈ C, we have wt−1 (i) = 0, and for all Lj ∈ C, wt−1 (j) > 0. T Thus, for any x in the set L∈C L \ x1:t−1 , the sum of the weights of its consistent languages achieves the maximum possible value, as it is the sum of all languages with non-zero weight, while any other x outside of the intersection must have strictly less total weight, because it is not included in one of the languages with non-zero weight. T We conclude that whenever L∈C L \ x1:t−1 > 0, the x̂t output by Algorithm 1 defined as x̂t = arg maxx∈X \x1:t−1
k X
wt−1 (i)1[x ∈ Li ]
i=1
T is guaranteed to satisfy x̂t ∈ L∈C L \ x1:t−1 . This means that the outputs of Algorithm 1 are consistent with the decisions of Algorithm 2, and so we conclude that the algorithm not only provides a mistake bound, but also guarantees that the time of last mistake is at most Cdim(L). Because the number of mistakes can be at most the time of last mistake, this further strengthens the mistake bound to min{⌊log2 k⌋, Cdim(L)}.
5.2
Lower Bounds
We note that while our algorithm’s last mistake bound has been shown to be tight for every class, the mistake bound is not necessarily optimal in a per-class sense. However, the following lower bound demonstrates that this is the best we can hope to achieve from a bound that depends solely on the cardinality of L. We prove this via a lower bound construction based on Littlestone trees (see Figure 1). Lemma 5.3 (Lower Bound). For any N ∈ N, there exists a finite language class L of size N such that no generation algorithm can guarantee fewer than ⌊log2 N ⌋ mistakes on every adversarial stream consistent with an L ∈ L.
7
Adversarial Strategy for Lemma 5.3 (n = 8, m = 3)
s = {}
x̂1 ∈ L0...
Adv. plays x1 ∈ L1...
0
Mistake 1
1
00
Adv. plays x2 ∈ L10...
x̂2 ∈ L11...
01
11
10
x̂3 ∈ L100
L000
L001
L010
L011
L100
Mistake 2
Adv. plays x3 ∈ L101
L101
L110
L111
Mistake 3
Figure 1: Visualizing the proof of Lemma 5.3. The tree represents the hierarchy of languages in L. At each internal node s, the generator is forced to output a prediction consistent with exactly one branch, corresponding to halving the number of consistent languages (red dashed arrow). The adversary observes this and outputs an element that forces the true language to lie in the opposite branch (blue solid arrow), guaranteeing a mistake. This process repeats for m = ⌊log2 |L|⌋ steps. Proof of Lemma 5.3. Our goal is to show that for any n > 0, there exists a language class L of size n such that every generator will make at least log2 n mistakes against an adversarial stream from a language L ∈ L. Let m ∈ Z≥0 be the largest m such that 2m ≤ n. Note that by definition, m = ⌊log2 n⌋. We construct a collection of 2m languages Lm = {Lv }v∈{0,1}m where each language is identified with a bit string v ∈ {0, 1}m . If 2m < n, we additionally pad the language collection with dummy languages L2m +1 , ..., Ln that are disjoint from all the languages in Lm to ensure that the constructed collection has size exactly n. These will not be used in the construction of the hard adversarial stream. Pm We now define the contents of Lm as follows. Fix a subset of X , B, of size i=1 2i = 2m+1 − 2. We label Sm each point with a bitstring of length between 1 and m: B := i=1 {xp : p ∈ {0, 1}i }. A point xp ∈ B lies in Lv ∈ Lm if and only if p is a prefix of v. In order to ensure each language has infinite support, we pad each Lv with an infinite subset of X , disjoint from all other languages. We now describe how an adversary can construct an adversarial stream that forces at least m mistakes by the generator. The adversary keeps track of a bitstring s = {}, which initially begins as empty. The adversary loops the following process for each time t = 1, ....: 1. Observe the generator’s output x̂t . 2. If t = m + 1, BREAK from the loop, and enumerate all remaining elements of Ls . 3. If the generator outputs xv ∈ B or x ∈ Lv \ B such that s is a prefix of v, observe the bit immediately proceeding s: v[|s|] (0-indexed), and append the complement of that bit to s. Otherwise, append an arbitrary bit to s.
8
4. Output xs ∈ B. It remains to show that the adversary’s stream is valid, i.e. it consists of all unique elements and is consistent with a language in Lm , and that the generator makes m mistakes. The adversary’s stream is valid First, we consider the final bitstring s of length m that the adversary constructs before hitting the break at time m + 1. At this point, xs ∈ B is consistent with exactly one language, Lv where v = s, as it is the only string of length m that contains s as a prefix. Moreover, we are guaranteed that all xt for t ≤ m satisfied xt ∈ Lv , because the bitstring s at that time was a prefix of the final s by construction, and all were unique, because s was a different length at each step. By definition, all of the adversary’s outputs after time t = m are also unique and consistent. Therefore, we conclude that the adversarial stream is valid, and moreover is actually a valid enumeration of Lv . The generator makes m mistakes. We can show that every x̂t for t ≤ m is a mistake. In particular, at the beginning of timestep t, the set of potential languages that are consistent with the adversarial stream so far are exactly all of the languages Lv where s is a prefix of v. By construction, there are 2m−t+1 such languages. The adversary’s xt is defined to be xs||0 or xs||1 , where seeing either of these points reduces the set of consistent languages by half to 2m−t , and moreover these two consistent sets are totally disjoint. If in the check in step 3, the generator outputs xv ∈ B or x ∈ Lv \ B such that s is a prefix of v, this means that its output element can only be consistent with languages in one of these two disjoint sets. By playing xs||¬v[|s|] , the adversary reveals the true language to be in the other set of consistent languages, and thus the generator has made a mistake. If the generator’s point does not satisfy the first condition, it means the generated element is not consistent with any of the 2m−t−1 languages still consistent with the adversary’s stream, and thus is also automatically a mistake regardless of what the adversary outputs. Thus, we conclude that in every step from t = 1 to t = m, the generator’s move does not lie in the target language Lv , and thus the generator makes m = ⌊log2 n⌋ mistakes.
6
Mistake-Bounded Non-Uniform Generation
We now turn to the general setting of countably infinite language classes L = {L1 , L2 , . . . }. Here, we cannot hope for a uniform bound on mistakes across the entire class. Instead, we seek a non-uniform guarantee that depends on the index i of the target language Li . Existing work by Li et al. [2024] and Charikar and Pabbaraju [2024] focuses on minimizing the time of last mistake. For example, the Greedy algorithm of Charikar and Pabbaraju [2024] guarantees convergence in terms of the non-uniform complexity of Li , m(Li ), a structural parameter representing the complexity of Li ’s intersections with preceding languages. Definition 5 (Non-Uniform Complexity). Given an infinite stream of languages L = L1 , L2 , ..., the non-uniform complexity of Li is defined as size of the largest finite subcollection of (L1 , ..., Li ) that contains Li : \ \ m(Li ) := ′ max {| L ∩ Li | : | L ∩ Li | < ∞}. L ⊆{L1 ,...,Li−1 }
L∈L′
L∈L′
In this section, we present two contrasting results. First, we show that if one prioritizes minimizing mistakes, we can achieve a mistake bound of O(log2 i), i.e. with only logarithmic dependence on the index. However, we then prove that this comes at a cost: no algorithm can simultaneously achieve this logarithmic mistake bound and the convergence time guaranteed by Charikar and Pabbaraju [2024].
6.1
Minimizing Mistakes without Convergence
To minimize the total number of mistakes, we revisit our General Recipe (Algorithm 1). In the finite case, we used a uniform prior. For infinite streams, we must adopt a prior that decays sufficiently fast to ensure finite capacity, yet slowly enough to not penalize later languages too heavily. We instantiate Algorithm 1 with P 1 polynomially decaying weights w0 (i) = i12 (noting that < ∞). and a growth function that doubles the 2 i number of languages considered at each step, f (t) = 2t . Under this instantiation, our algorithm yields the following guarantee:
9
Theorem 6.1. Let L = {L1 , L2 , ...} be a countably infinite class of languages under a fixed enumeration. For any language Li ∈ L, the instantiation of Algorithm 1 described above guarantees a non-uniform mistake bound of: Mnon-unif (G, i) ≤ 3 log2 i + log2 (π 2 /6) = O(log2 i). The proof follows immediately from an appropriate instantiation of Theorem 4.1. w0 (i) = 1/i2 Proof of Theorem 6.1. To prove the theorem, we instantiate Theorem 4.1 with the weight Pfunction ∞ t 2 and growth function f (t) = 2 . By standard results due to Euler [1740], we have that i=1 1/i = π 2 /6, and thus can set W = π 2 /6. Under this definition of f , f −1 (i), i.e. the largest t such that f (t) < i, is upper bounded by log2 (i). Thus, for this particular instantiation of weight functions and growth function, we can guarantee that Algorithm 1 guarantees a non-uniform mistake bound of m(G, Li ) ≤ f −1 (i) + ⌊log2 W/w0 (i)⌋ ≤ ⌊log2 i⌋ + log2 π 2 i2 /6 = log2 π 2 /6 + 3 log2 i = O(log2 i).
6.2
Simultaneously Bounding Mistakes and Convergence
While the strategy above guarantees low error, it does not prioritize when those errors occur. In particular, by prioritizing bounding mistakes on languages late in the stream, it may be slow to converge on early languages. We next present an algorithm that can non-uniformly generate from L while simultaneously bounding the total number of mistakes. However, in order to balance these two goals, we must weaken our mistake bound to only guaranteeing a mistake bound that is linear in the index of the target language. To obtain this guarantee we analyze a modification of the greedy non-uniform generation algorithm by Charikar and Pabbaraju [2024], termed Modified-Greedy. This algorithm prioritizes maintaining consistency with the earliest consistent languages. Lemma 6.2. There exists a non-uniform generation algorithm (Modified-Greedy) with a time-of-last-mistake guarantee of max{i − 1, m(Li ) + 1} and a non-uniform mistake bound of: Mnon-unif (G, i) ≤ min{2(i − 1), max{i − 1, m(Li ) + 1}}. Note that the mistake bound here is linear in i (2(i − 1)), which is exponentially worse than the O(log i) bound in Theorem 6.1. We refer to the algorithm we will use to obtain our guarantees as Modified-Greedy (Algorithm 3). The algorithm as we describe it differs from the original definition provided by Charikar and Pabbaraju [2024], with the change highlighted in red. However, while the modification means that the actions taken by the two algorithms will be different, the modified algorithm still satisfies the last-mistake-bound promised by Charikar and Pabbaraju [2024]. For completeness, we re-prove the last-mistake-time bound for the modified algorithm in Lemma 6.3. Algorithm 3 Modified-Greedy (c.f. Algorithm in Theorem 6 of Charikar and Pabbaraju [2024]) Input: Universe X , infinite stream L = L1 , L2 , ... for t = 1, . . . , ∞ do Initialize It = X \ x1:t−1 . for i = 1, ..., t do if x1:t−1 ⊆ Li and |Li ∩ It | > 0 then It ← It ∩ Li end end Output x̂t ∈ It . end
10
Lemma 6.3. For any infinite stream L = L1 , L2 , ..., Modified-Greedy(Algorithm 3) guarantees a last mistake time t(Li ) ≤ max{i − 1, m(Li ) + 1} for any adversarial stream consistent with Li ∈ L. Proof. Consider any t ≥ max{i, m(Li ) + 2}. This means that during step t, Modified-Greedy considers Li as one of the languages to possibly intersect with It . We are also guaranteed that x1:t−1 ⊆ Li because the adversary is consistent with Li . Consider the point at which Li is considered by the algorithm during step t. By definition, there is some T T J ⊆ [i − 1] such that x1:t−1 ⊆ Lj for each j ∈ J, and It = j∈J Lj \ x1:t−1 . Thus, x1:t−1 ⊆ j∈J Lj ∩ Li . If |It ∩ Li | > 0, the algorithm is guaranteed to play a x̂t ∈ Li , and thus does not make a mistake. We claim that it cannot be the case that |It ∩ Li | = 0. This is because this would imply that \ t−1≤ Lj ∩ Li ≤ m(Li ), j∈J
but this is a contradiction, because we assumed that t ≥ m(Li ) + 2. Thus, we conclude that Modified-Greedy will not make a mistake for all t ≥ max{i, m(Li ) + 2}, and thus the last mistake time is at most max{i − 1, m(Li ) + 1}. We are now ready to prove Lemma 6.2, which further bounds the number of mistakes made by ModifiedGreedy to show that it satisfies both a time-of-last-mistake bound and a total mistake bound. Proof of Lemma 6.2. Our proof proceeds by showing that every mistake incurred by Modified-Greedy on a language Li is accompanied by eliminating some language in the prefix L1 , ..., Li−1 . Because there are only i − 1 such languages, the number of mistakes on Li is bounded by 2(i − 1), where the double factor comes because we don’t consider Li until step i, and so could make mistakes during the i − 1 steps before that. At any step t ≥ i, we have two cases. Either x̂t ∈ Li , in which we can’t make a mistake, or x̂t ̸∈ Li , in which case the algorithm makes a mistake when the true language is Li . if x̂t ̸∈ Li , this means that at the point T in the algorithm during step t when It ∩ Li was considered, we had |It ∩ Li | = 0. Note that by definition, It = j∈J Lj \ x1:t−1 for some J ⊆ [i − 1] satisfying x1:t−1 ⊆ Lj for each j ∈ J. Thus, because xt ∈ Li , we have xt ̸∈ It , which implies that there exists some j < i such that x1:t−1 ⊆ Lj , but xt ̸∈ Lj . This implies that Lj becomes inconsistent at step t, and is no longer considered after t. Because there are only i − 1 languages before i, this means that the algorithm can make at most i − 1 mistakes after starting to consider Li , and thus can make at most 2(i − 1) mistakes. Finally, the last-mistake-time of max{i − 1, m(Li ) + 1} follows from Lemma 6.3, and because the total number of mistakes is upper-bounded by the last-mistake time, we can refine the total number of mistakes to min{2(i − 1), max{i − 1, m(Li ) + 1}}.
6.3
Tradeoff Between Last-Mistake-Time and Total Mistakes
This raises a natural question: is there a generation strategy that achieves our optimal mistake bound of O(log2 i) while also preserving Charikar and Pabbaraju [2024]’s last-mistake-time guarantee? We answer in the negative. We prove a fundamental barrier: to achieve the optimal convergence time, an algorithm must be willing to make mistakes on later languages in order to prioritize converging on languages appearing earlier in the stream. Conversely, to achieve logarithmic mistakes, an algorithm must start to prioritize later languages over early languages when they start to accumulate many mistakes, potentially delaying convergence time. Theorem 6.4. There exists an infinite language class equipped with a fixed enumeration L = {L1 , L2 , ...} such that any algorithm that guarantees a last-mistake time of t(Li ) ≤ O(max{i, m(Li )}) on all i ∈ N must suffer a number of mistakes that grows linearly with the language index. Specifically, for every i ≥ 2, Mnon-unif (G, i) ≥ i − 1.
11
The key intuition for the proof is as follows: we construct a sequence of languages sharing nested, rapidly growing finite prefixes. By sequentially enumerating these shared elements, the adversary forces the generator into a recurring dilemma at each prefix boundary. At the kth boundary, the unseen points available to the generator are either points solely in the language Lk , or a point shared by all proceeding languages Lj for j ≥ k, but outside of Lk . If the generator predicts a point outside of Lk , the adversary halts and declares that language the target. This forces a late mistake that violates the time-of-last-mistake bound for Lk . On the other hand, if the generator safely plays from Lk at each boundary, it means that by the time it gets to the ith boundary, it has incurred a mistake on Li at every boundary leading up to i, resulting in a linear number mistakes if the adversary halts and declares Li the target. Proof of Theorem 6.4. We construct our hard language stream on the countably infinite X = N × N, and thus refer to elements x ∈ X as pairs (i, j) ∈ N × N. Fix an arbitrarily large n ∈ N. We define language Li as follows for any i ≥ 1: [ Li = {(i, j) : j ∈ N} ∪ {(k, j) : j ∈ [nk ]} k∈[i−1]
Note that this is a valid language class, because each language has infinite support, and for any particular language Li , i−1 [ X k m(Li ) = | {(k, j) : j ∈ [n ]}| = nj j=1
k∈[i−1]
With m(L1 ) = 0. Similarly note that \ | Lj | = m(Li ) + ni = ω(m(Li )). j≥i
Given this language class, and any index i∗ ≥ 2, we describe an adversary strategy that either results in a time-of-last-mistake equal to m(Li ) + ni = ω(m(Li )) for some language i, or forces the number of mistakes on i∗ to be at least i∗ − 2. We have the adversary first enumerate all (1, j) for each j ∈ [n], then (2, j) for j ∈ [n2 ], (3, j) for each j ∈ [n3 ], etc. Let ti be the timestep at which the adversary would output xt = (i, 1) for each i ∈ N. Note that before seeing (i, 1), all of the adversary’s outputs thus far are consistent with Lj for all j ≥ i − 1. At each such timestep, starting at t2 , the adversary observes x̂ti , and proceeds as follows: 1. if x̂ti ̸∈ Li−1 , the adversary stops its enumeration, and instead enumerates all of the remaining elements of Li−1 . 2. Otherwise, if i = i∗ , the adversary stops and enumerates all remaining elements of Li∗ . Note that we are guaranteed to trigger one of steps 1 or 2 at some point during the game, as i∗ is finite. If Step 1 executes, this implies a contradiction to the last-mistake-time bound for language Li−1 , as all of the adversary’s outputs thus far and in the future are consistent with Li−1 , and the generator makes a mistake on Li−1 at time i−1 X ti = 1 + nj = m(Li−1 ) + ni−1 + 1 = ω(m(Li−1 )). j=1
Note that by construction, at timestep ti , we have that for any j ≥ i, Lj ∩ Li−1 \ x1:ti −1 = ∅, and thus if the generator plays x̂ti ∈ Li−1 , we must have x̂ti ̸∈ Lj for all j ≥ i, and thus this counts as a mistake if any such j ends up being the target language. If step 1 never executes, this means that the generator plays from Li−1 at each ti for i = 2, ...., i∗ , and thus makes at least i∗ − 1 mistakes on Li∗ . Thus, in either case the generator is forced to either contradict the last-mistake-time-bound of m(Li ) for some i ≤ i∗ , or make a linear number of mistakes on i∗ .
12
7
Mistake-Bounded Noisy Generation
The algorithms presented in Sections 5 and 6 rely on eliminating candidate languages as soon as they become inconsistent with the adversary’s outputs. While this approach works well in a setting where we assume the adversary is perfectly consistent with a target language, it’s also natural to explore what guarantees are possible against noisy adversaries, who may not be perfectly consistent with the target language. This imperfect setting has been studied in the context of last-mistake-time guarantees by a number of works. Raman and Raman [2025] first proposed a noisy setting where the adversary may insert noise at an unknown but finite number of steps. More recently, Bai et al. [2025] further explore the limits of generating in the presence of a finite amount of noise, while Mehrotra et al. [2025] show a surprising result that any countable class can be generated in the limit in the presence of potentially infinite but vanishing noise. In this section, we show that noise-dependent mistake bounds for the noisy setting can be derived by leveraging results from the learning from demonstrations setting. The key idea behind these results is to relax the weight updates to downweight languages when the adversary makes a mistake, rather than setting the weight to 0 and removing them from consideration. Lemma 7.1 (Noisy Mistake Bound for Finite Classes). Given a finite language class L and γ ∈ (0, 3/4], given an adversarial stream x1 , x2 , ..., not necessarily consistent with any L ∈ L, denote the number of mistakes the stream has made on L at time t as t X ML (x1:t ) = 1[xi ̸∈ L]. i=1
Similarly, denote the learner’s mistakes up to time t as ML (x̂1:t ). Then, there exists an algorithm that guarantees for any L, ML (x̂1:t ) ≤ (1 + 2γ)ML (x1:t ) + log2 |L|/γ. This noisy guarantee follows from the results of Joshi et al. [2025] on learning from demonstrations. In Appendix B.2, we show its derivation. If we instantiate this result with γ = 1/2 and assume our adversary is guaranteed to only have a finite amount of noise, then this result guarantees that our generator will only make a finite number of mistakes, no matter the amount of noise. In particular, its mistakes are bounded by 2(M + log2 |L|), where M is the amount of noise inserted by the adversary. While the results of Joshi et al. [2025] do not extend to infinite streams of reward functions, we provide an extension of their result (Theorem B.5) that allows us to derive non-uniform mistake bounds for infinite streams of languages. Proper instantiation of the theorem’s parameters gives the following guarantee for language generation in the presence of noisy adversaries (see Appendix B.2 for details): Lemma 7.2 (Noisy Mistake Bound for Infinite Streams). Suppose we are given an infinite stream of languages L = L1 , L2 , ... and γ ∈ (0, 3/4]. Then, there exists a generation algorithm such that for every adversarial stream x1 , x2 , ..., not necessarily consistent with any Li ∈ L and i, T ∈ N, T X t=1
1[x̂t ̸∈ Li ] ≤ (1 + 2γ)
T X
1[xt ̸∈ Li ] + (1 + 2/γ) log2 i.
t=⌊log2 i⌋
As in the finite case, we note that this result implies that when the adversary’s stream only has a finite amount of noise, the generator is also guaranteed to make at most a finite number of mistakes.
7.1
Comparison to existing time-of-last-mistake bounds
The guarantee of Lemma 7.1 echoes that of Raman and Raman [2025], who show that whenever the adversary only adds a finite amount of noise, the time-of-last-mistake can be bounded for any finite language class. Similarly, Lemma 7.2 guarantees in cases where the adversary makes a finite amount of mistakes, we can guarantee a non-uniform but finite number of mistakes for any countable class. This can be compared to the results of Mehrotra et al. [2025], who show that any countable language can be generated in the limit in the presence of a finite amount of noise. We leave as a key open question whether the time-of-last-mistake bounds given by Raman and Raman [2025] and Mehrotra et al. [2025] can be achieved simultaneously with the mistake bounds guaranteed in Lemmas 7.1 and 7.2, respectively.
13
Interestingly, while Mehrotra et al. [2025] are able to guarantee a finite number of mistakes (upper-bounded by the finite last-mistake-time) in the presence of infinite but vanishing noise, our mistake bounds do not necessarily guarantee a finite number of mistakes in such a case, just that the rate of mistakes made by the learner is no worse than that of the adversary. We leave developing improved algorithms with a bounded number of mistakes in the o(1)-noise case, along with further analysis of the interaction between time-of-last-mistake and number of mistakes, as an open question for future work.
8
Open Directions
Our introduction of mistake bounds as an alternative metric of success in language generation raises several key questions. We note three of particular interest. (1) Our bounds for finite classes rely on cardinality (log2 |L|). In online classification, the Littlestone dimension characterizes learnability independent of class size [Littlestone, 1988]. Does there exist an analogous combinatorial dimension d(L) for language generation that characterizes the optimal mistake bound more tightly than cardinality or closure dimension? (2) Theorem 6.4 identifies a conflict between minimizing mistakes (O(log i)) and minimizing time-of-last-mistake (O(m(Li ))). What is the full Pareto frontier of simultaneous mistake and convergence guarantees? (3) Finally, in the noisy setting, it remains an open problem whether our mistake bounds can be achieved simultaneously with bounded time-of-last-mistake guarantees.
Acknowledgments JK is supported in part by the Simons Foundation Collaboration on the Theory of Algorithmic Fairness and a grant from the MacArthur Foundation. CP is supported by the Simons Foundation Collaboration on the Theory of Algorithmic Fairness and the Apple Scholars in AI/ML PhD fellowship. OR is supported by the Simons Foundation Collaboration on the Theory of Algorithmic Fairness, and the Simons Foundation investigators award 17351.
References Antonios Anastasopoulos, Giuseppe Ateniese, and Evgenios M Kornaropoulos. Safe language generation in the limit. arXiv preprint arXiv:2601.08648, 2026. Dana Angluin. Inductive inference of formal languages from positive data. Information and control, 45(2): 117–135, 1980. Marcelo Arenas, Pablo Barceló, Luis Cofré, and Alexander Kozachinskiy. Language generation: Complexity barriers and implications for learning. arXiv preprint arXiv:2511.05759, 2025. Yannan Bai, Debmalya Panigrahi, and Ian Zhang. Language generation in the limit: Noise, loss, and feedback. arXiv preprint arXiv:2507.15319, 2025. Moses Charikar and Chirag Pabbaraju. Exploring facets of language generation in the limit. arXiv preprint arXiv:2411.15364, 2024. Moses Charikar and Chirag Pabbaraju. Pareto-optimal non-uniform language generation. arXiv preprint arXiv:2510.02795, 2025. Leonhard Euler. De summis serierum reciprocarum. Commentarii academiae scientiarum Petropolitanae, pages 123–134, 1740. E Mark Gold. Language identification in the limit. Information and control, 10(5):447–474, 1967. Steve Hanneke, Amin Karbasi, Anay Mehrotra, and Grigoris Velegkas. On union-closedness of language generation. arXiv preprint arXiv:2506.18642, 2025. Nirmit Joshi, Gene Li, Siddharth Bhandari, Shiva Prasad Kasiviswanathan, Cong Ma, and Nathan Srebro. Learning to answer from correct demonstrations. arXiv preprint arXiv:2510.15464, 2025. 14
Alkis Kalavasis, Anay Mehrotra, and Grigoris Velegkas. Characterizations of language generation with breadth. arXiv preprint arXiv:2412.18530, page 3, 2024. 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, pages 1732–1743, 2025. Amin Karbasi, Omar Montasser, John Sous, and Grigoris Velegkas. (im) possibility of automated hallucination detection in large language models. arXiv preprint arXiv:2504.17004, 2025. Jon Kleinberg and Sendhil Mullainathan. Language generation in the limit. Advances in Neural Information Processing Systems, 37:66058–66079, 2024. Jon Kleinberg and Fan Wei. Density measures for language generation. arXiv preprint arXiv:2504.14370, 2025a. Jon Kleinberg and Fan Wei. Language generation and identification from partial enumeration: Tight density bounds and topological characterizations. arXiv preprint arXiv:2511.05295, 2025b. Jiaxun Li, Vinod Raman, and Ambuj Tewari. Generation through the lens of learning theory. arXiv preprint arXiv:2410.13714, 2024. Nick Littlestone. Learning quickly when irrelevant attributes abound: A new linear-threshold algorithm. Machine learning, 2(4):285–318, 1988. Anay Mehrotra, Grigoris Velegkas, Xifan Yu, and Felix Zhou. Language generation with infinite contamination. arXiv preprint arXiv:2511.07417, 2025. Charlotte Peale, Vinod Raman, and Omer Reingold. Representative language generation. arXiv preprint arXiv:2505.21819, 2025. Ananth Raman and Vinod Raman. Generation from noisy examples. arXiv preprint arXiv:2501.04179, 2025.
A
Proofs from Section 4
In this section, we prove Theorem 4.1, which shows that our general algorithm (Algorithm 1) guarantees a mistake bound that depends on the choice of initial weights w0 and growth function f . We restate the theorem here for readability: Theorem 4.1. For any countably infinite language P∞ class equipped with a fixed enumeration L = {L1 , L2 , ...}, associated weights w0 : N → R≥0 such that i=1 w0 (i) ≤ W < ∞, and non-decreasing growth function f : N → N, the generations outputted by Algorithm 1 guarantee a non-uniform mistake bound of M (G, Li ) ≤ f −1 (i) + ⌊log2 (W/w0 (i))⌋ for each i ∈ N, where if there exists a t′ such that f (t′ ) ≥ i, f −1 (i) is the largest value t such that f (t) < i, or 0 if every for every t′ ∈ N f (t′ ) is at least i, and otherwise f −1 (i) = ∞. Our proof relies on the following lemma, which establishes a key property about how the weights in Algorithm 1 evolve: Pf (t+1) Lemma A.1. Define Wt := i=1 wt (i). Then, for any step t ≥ 1, f (t+1)
X
Wt ≤ Wt−1 +
w0 (i).
i=f (t)+1
Proof. We re-express Wt by decomposing the weights: Wt =
≤
f (t) X
f (t+1)
wt (i) +
X
i=1
i=f (t)+1
f (t) X
f (t+1)
i=1
wt (i) +
X
wt (i)
w0 (i)
(Definition of weight initialization)
i=f (t)+1
15
Pf (t) Pf (t) Thus, it suffices to prove that i=1 wt (i) ≤ Wt−1 = i=1 wt−1 (i). Let It = {1 ≤ i ≤ f (t) : wt (i) ̸= 0}. Using this set, we re-express our sum as f (t) X
wt (i) =
i=1
X
wt (i)
i∈It
X
=2 X
wt−1 (i)
(Definition of weight update)
i∈It ,x̂t ∈Li
i∈It ,x̂t ̸∈Li
=
X
wt−1 (i) + X
wt−1 (i) +
wt−1 (i)
i∈It ,x̂t ̸∈Li
i∈It
Let It−1 = {i ≤ f (t) : wt−1 (i) ̸= 0}. Note that It ⊆ It−1 . Because all weights are non-negative, we get an upper bound by replacing It with It−1 in the above expression: X
X
X
wt−1 (i) +
wt−1 (i)
i∈It−1 ,x̂t ̸∈Li
i∈It
X
=
wt−1 (i)
i∈It ,x̂t ̸∈Li
i∈It
≤
X
wt−1 (i) +
X
wt−1 (i) +
i∈It−1 ,xt ∈Li
X
= Wt−1 +
wt−1 (i)
i∈It−1 ,x̂t ̸∈Li
X
wt−1 (i) −
i∈It−1 ,xt ∈Li
wt−1 (i)
i∈It−1 ,x̂t ∈Li
By the definition of Algorithm 1, x̂t is picked according to the rule x̂t = arg maxx∈X \x1:t−1
f (t) X
wt−1 (i)1[x ∈ Li ] = arg maxx∈X \x1:t−1
i=1
X
wt−1 (i).
i∈It−1 ,x∈Li
And by assumption, the adversary’s output xt comes from the set X \ x1:t−1 . Thus, we are guaranteed that Pf (t) P i∈It−1 ,xt ∈Li wt−1 (i) − i=1 wt (i) is upper-bounded by Wt−1 , i∈It−1 ,x̂t ∈Li wt−1 (i) ≤ 0 and can conclude that completing the proof. P
We now apply this lemma to prove Theorem 4.1. Proof of Theorem 4.1. We first note that unrolling Lemma A.1 gives a constant upper bound on any Wt : f (t+1)
Wt ≤ Wt−1 +
X
f (t+1)
w0 (i) ≤
X
≤
i=1
i=f (t)+1
X
w0 (i) ≤ W.
i=1
For a particular true language Li , the first step where Li is considered in the argmax by the algorithm is at f −1 (i) + 1. Up until this point, the algorithm could have made at most f −1 (i) mistakes. We now focus on how many additional mistakes the algorithm can make after first introducing Li . Suppose that at a timestep T , we have that T X 1[x̂t ̸∈ Li = M, t=f −1 (i)+1
i.e. the algorithm has made M mistakes after first introducing Li . By definition of our update rule, for each of these timesteps, we had xt ∈ Li because it is the true language, and x̂t ̸∈ Li . Thus, the initial weight of Li has doubled M times, and we have wT (i) = 2M w0 (i) ≤ WT ≤ W. Where we get an upper bound of W from Lemma A.1. Solving for M , we conclude that M ≤ ⌊log2 W/w0 (i)⌋. Because this holds for any T , we conclude that the algorithm makes at most ⌊log2 W/w0 (i)⌋ additional mistakes after the introduction of Li , and thus makes at most f −1 (i) + ⌊log2 W/w0 (i)⌋ mistakes in total. 16
B
Mistake Bounds via Learning from Demonstrations
Recent work by Joshi et al. [2025] studies the setting of Learning from Demonstrations (LfD). In this section, we discuss how the problem of mistake bounded language generation can be reduced to this setting, allowing us to use the techniques of Joshi et al. [2025] to derive mistake bounds. The online setting of learning from correct demonstrations can be thought of as a contextual bandit problem. Let X be a set of contexts, and Y be a set of actions. A reward function r : X × Y → {0, 1} specifies a binary reward for each context/action pair. The online interaction between the learner and adversary proceeds as follows for each round t = 1, 2, 3, ..., T : 1. The learner receives context xt ∈ X from the adversary. 2. The learner outputs an action ŷt ∈ Y. 3. The learner receives a demonstration yt ∈ Y from the adversary. The learner receives no other feedback. In the setting of learning from an optimal demonstrator, or what can be thought of as the “realizable” setting of the problem, the learner has access to a collection of reward functions R. The adversary is assumed to be optimal, in that there exists some true reward function r∗ ∈ R such that for all timesteps t, r∗ (xt , yt ) = 1. We assume that all reward functions and contexts have at least one action that results in non-zero reward. Crucially, this true reward r∗ is unknown to the learner and the learner never receives feedback about the reward values of its output actions. Nevertheless, the learner’s performance is evaluated with respect to this true reward. We say that the learner makes a mistake at timestep t if r∗ (xt , ŷt ) = 0. Typical online learning strategies typically rely on feedback at every timestep in order to update a policy toward more successful outputs. The lack of such feedback in this online demonstration setup thus makes it seem difficult, and surprising that a learner could hope to bound its mistakes. However, this is the main result of Joshi et al. [2025], who show that for finite reward classes R, there exists an algorithm that guarantees a learner makes no more than log2 |R| mistakes on any R: Theorem B.1 (Joshi et al. [2025], Theorem 4). There exists an online algorithm such that given any online sequence ((xt , yt ))t∈N such that there exists r∗ ∈ R with r∗ (xt , yt ) = 1 for all t, the algorithm makes at most log2 |R| mistakes, e.g. X (1 − r∗ (xt , ŷt )) ≤ log2 |R|. t∈N
B.1
Connecting Mistake-Bounded Language Generation to Learning from Demonstrations
In this section, we describe how guarantees for learning from demonstrations can be translated to mistake bounds for language generation. At first glance, one might assume that language generation is a special case of learning from demonstrations where there is only a single context, and each reward function is an indicator of a particular language. However, language generation’s requirement that the generator output unseen elements means that this is not quite the case, as a learner in the single context setting could succeed by continuously outputting the adversary’s initial output. To draw a true comparison, we must carefully construct contexts and reward functions based on a language class to ensure a learner can only receive high reward by outputting new elements. We describe the full reduction in the theorem below. We present the reduction in the most general terms possible, i.e. for potentially non-uniform mistake bounds dependent on the position of the reward function in the stream and an imperfect adversary, as well as in terms of the timestep T . For the remainder of this section, we denote the universe of elements used in language generation as U , with elements u ∈ U , to differentiate from the context space in LfD. Lemma B.2. Suppose we have access to a learning from demonstrations algorithm such that for any choice of contexts X , label set Y, and reward class R = r1 , r2 , ..., presented as a (potentially infinite) stream of functions, the algorithm guarantees that for any adversarial stream (x1 , y1 ), (x2 , y2 ), ..., the following mistake bound is satisfied for each ri ∈ R and T ∈ N: T T X X (1 − ri (xt , ŷt )) ≤ M (i, T, (1 − ri (xt , yt ))). t=1
t=1
17
Then, for any language class L = L1 , L2 , ..., we can use this algorithm to construct a generator whose outputs are guaranteed to satisfy for any Li ∈ L and T ∈ N, T X
1[ût ̸∈ Li \ u1:t−1 ] ≤ M (i, T,
T X
t=1
1[ut ̸∈ Li \ u1:t−1 ]).
t=1
Joshi et al. [2025]’s result for finite classes and perfect demonstrators can be interpreted in this setting as guaranteeing M (i, T, 0) ≤ log2 |R| for all i ∈ [|R|] and T ∈ N, and thus bounds the number of mistakes in the language setting by M (i, T, 0) ≤ log2 |L| as well. In the setting of sub-optimal demonstrators, where the demonstrator may not always give a demonstration with high reward, Joshi et al. [2025] show that when the reward class is finite, the sub-optimality of the learner’s reward with respect to ri can be upper-bounded in terms of the class size and adversary’s suboptimality, thus guaranteeing T T X X M (i, T, (1 − ri (xt , yt ))) ≤ (1 + 2γ) (1 − ri (xt , yt )) + log2 |R|/γ t=1
t=1
for any choice of γ ∈ (0, 1). This is the guarantee we leverage to provide mistake-bound guarantees for noisy adversaries in Section 7. The results of Joshi et al. [2025] only apply to settings with finite reward classes, where we can hope for a uniform guarantee over all possible reward functions. However, the setting of non-uniform language generation requires mistake bounds that can be guaranteed non-uniformly over a countably infinite stream of languages. While our reduction still applies to this case, there are no existing results that provide LfD guarantees for an infinite stream of rewards. In Section B.3, we give a new algorithm for the LfD setting that can give guarantees for an infinite stream of reward functions, allowing us to derive mistake bounds in the non-uniform language generation setting. We now present the proof of Lemma B.2. Proof of Lemma B.2. Given a language class L = L1 , L2 , ... for a universe U and a general algoithm for LfD, we describe how to leverage the LfD algorithm to generate with bounded mistakes. We first define the context space X and label space Y for the algorithm. We let Y = U, and X = {xu1:n : n ≥ 0, u1 , ..., un ∈ U}, e.g. a unique context for each finite string of elements from U. We refer to elements in X as xs , where s is some finite string of elements {u1 , ..., un }. For a language Li , we define a corresponding reward function ri as follows: ri (xs , y) = 1[y ∈ Li \ s]. Are reward function class of interest is thus R = r1 , r2 , ..., where each ri is identified with Li ∈ L. We now describe how to use a learner for the above problem to generate with bounded mistakes. At the beginning of each step t, the elements that have been shown thus far by the adversary are some u1 , ..., ut−1 . To leverage the LfD algorithm, we act as the adversary and show the learner the context xu1:t−1 . The learner outputs some ŷt ∈ U, and we generate exactly this element in the language generation setting. We then see the adversary-generated element ut , and make this the adversarial demonstration yt = ut in the LfD algorithm. Note that by definition, the noise of our language generation adversary on a particular language coincides with the sub-optimality of the demonstrator on the corresponding reward function, i.e. for any Li ∈ L and T ∈ N, T X
1[ut ̸∈ Li \ u1:t−1 ] =
t=1
T X
(1 − ri (xu1:t−1 , yt ).
t=1
Similarly, the mistakes of our generator on Li are equal to the sub-optimality of the learner on ri : T X
1[ût ̸∈ Li \ u1:t−1 ] =
t=1
T X t=1
18
(1 − ri (xu1:t−1 , ŷt ).
Thus, we conclude that if the LfD algorithm guarantees that at a particular step T that for any i, the learner’s actions satisfy the guarantee T T X X (1 − ri (xt , ŷt )) ≤ M (i, T, (1 − ri (xt , yt ))), t=1
t=1
then the outputs of our constructed generator must also satisfy T X
1[ût ̸∈ Li \ u1:t−1 ] ≤ M (i, T,
t=1
B.2
T X
1[ut ̸∈ Li \ u1:t−1 ]).
t=1
Learning from Sub-Optimal Demonstrators and Noisy Adversaries
In this section, we describe how to derive our mistake bounds for noisy adversaries from Lemmas 7.1 and 7.2. Both results can be derived by leveraging the reduction outlined in Lemma B.2 along with an appropriate result from the LfD setting. The finite case immediately follows from an existing result of Joshi et al. [2025], while Lemma 7.2 follows from proper instantiation of Theorem B.5. B.2.1
Deriving Lemma 7.1
Joshi et al. [2025] give the following result for learning from potentially sub-optimal demonstrations for a finite class of reward functions. Theorem B.3 (Theorem 4, Joshi et al. [2025]). There exists an algorithm such that for any finite R such that maxy r(x, y) = 1 for all r ∈ R and x ∈ X , and any online sequence (xt , yt ), after the end of T rounds, for any 0 < γ ≤ 3/4, T X
T X (1 − r(xt , ŷt )) ≤ (1 + 2γ)( (1 − r(xt , yt )) + log2 |R|/γ.
t=1
t=1
Combining this result with the reduction in Lemma B.2 immediately gives the mistake bound for noisy adversaries stated in Lemma 7.1. B.2.2
Proof of Lemma 7.2
Lemma 7.2 (Noisy Mistake Bound for Infinite Streams). Suppose we are given an infinite stream of languages L = L1 , L2 , ... and γ ∈ (0, 3/4]. Then, there exists a generation algorithm such that for every adversarial stream x1 , x2 , ..., not necessarily consistent with any Li ∈ L and i, T ∈ N, T X t=1
1[x̂t ̸∈ Li ] ≤ (1 + 2γ)
T X
1[xt ̸∈ Li ] + (1 + 2/γ) log2 i.
t=⌊log2 i⌋
Proof of Lemma 7.2. We instantiate Algorithm 4 with polynomially decreasing weights w0 (i) = 1/i2 and exponential growth function f (t) = 2t . Note that this implies f −1 (i) = ⌊log2 i⌋. Plugging this in to the guarantee of Theorem B.5, we derive the following guarantee for general binary rewards. Note that because all languages have infinite support, we can assume that supy∈Y ri (x, y) = 1 for all i ∈ N and x ∈ X . Using the same reasoning as in Theorem 6.1, this simplifies to T X log2 π 2 /6 (1 − ri (xt , ŷt )) ≤ + (1 + 2γ) γ t=1
T X
(1 − ri (xt , yt )) + (1 + 2/γ) log2 i
t=⌊log2 i⌋
Substituting this into our reduction (Lemma B.2), we conclude that we can construct a generator with the following guarantee for every T and i:
19
T X
1[x̂t ̸∈ Li ] ≤ (1 + 2γ)
t=1
T X
1[xt ̸∈ Li ] + (1 + 2/γ) log2 i,
t=⌊log2 i⌋
Thus matching the promised guarantee.
B.3
Learning from Demonstrations with Infinite Reward Functions
While we can directly leverage the results of Joshi et al. [2025] to derive mistake bounds for finite language classes via our reduction in Lemma B.2, the problem of language generation is particularly concerned with settings in which we must learn to generate well from a countably infinite stream of languages. In this section, we extend the results of Joshi et al. [2025] and give an algorithm that provides non-uniform guarantees for an infinite stream of reward functions, R = r1 , r2 , . . . . Algorithm 4 Learning from Arbitrary Demonstrators with an Infinite Stream of Reward Functions. Input: Context space X , label space Y, infinite stream of reward functions R = {r1 , r2 , . . . } (with r : X × Y → [0, 1]), weights w0 : N → R≥0 , growth function f : N → N, parameter γ ∈ (0, 3/4] ∪ {1} for t = 1, 2, . . . , ∞ do Observe xt Pf (t) Output ŷt := arg maxy∈Y i=1 wt−1 (i)ri (xt , y) Observe adversary’s yt // Update weights for i ∈ [f (t)] if γ ∈ (0, 3/4] then wt (i) ← wt−1 (i)(1 + γ)λi (xt ,ŷt ) (1 − γ)λi (xt ,yt ) where λi (x, y) := supy′ ∈Y ri (x, y ′ ) − ri (x, y) else if γ = 1then if ri (xt , yt ) = 0 0 wt (i) ← wt−1 (i) if ri (xt , yt ) = ri (xt , ŷt ) = 1 2wt−1 (i) if ri (xt , yt ) = 1, ri (xt , ŷt ) = 0 end // Initialize weights for i ∈ {f (t) + 1, . . . , f (t + 1)} if γ ∈ (0, 3/4] then wt (i) = w0 (i) else if γ = ( 1 then w0 (i) if r(xj , yj ) = 1 for all j ∈ [t] wt (i) = 0 otherwise end end It will be helpful to define the following notation. For any i ∈ N and T ∈ N, denote
T M̂i,alg :=
T X t=1
ri (xt , ŷt ),
T Mi,opt :=
T X
sup ri (xt , y),
t=1 y∈Y
′
Ri (T : T ) =
T X
sup ri (xt , y) − ri (xt , yt ) .
t=T ′
y∈Y
Note that in the binary rewards case, if we assume that every context has at least one high-reward label, T Mi,opt is always equal to T . We present the following two results about Algorithm 4, one for the optimal demonstrator and binary reward case, and the other for sub-optimal demonstrators. Theorem B.4. For any infinite stream R = r1 , r2 , ... of binary reward functions, and any online sequence (xt , yt ) satisfying ri (xt , yt ) = 1 for some i ∈ N and all t ∈ N, initial weight function w0 : N → R≥0 satisfying 20
P∞
i=1 w0 (i) ≤ W < ∞, non-decreasing growth function f : N → N, after the end of T rounds, Algorithm 4 with input γ = 1 guarantees that for any ri such that ri (xt , yt ) = 1 for all t ∈ [T ], ∞ X
(1 − ri (xt , ŷt )) ≤ log2 (W/w0 (i)) + f −1 (i).
t=1
Theorem B.5. For anyP infinite stream R = r1 , r2 , ..., any online sequence (xt , yt ), initial weight function ∞ w0 : N → R≥0 satisfying i=1 w0 (i) ≤ W < ∞, non-decreasing growth function f : N → N, and γ ∈ (0, 3/4], after the end of T rounds, Algorithm 4 guarantees that T T Mi,opt − M̂i,alg ≤ log2 (W/w0 (i))/γ + (1 + 2γ)Ri (f −1 (i) + 1 : T ) + f −1 (i).
The proof of Theorem B.4 follows a similar potential argument to that of Theorem 4.1. We begin by bounding the growth of the total weight using the following lemma: Pf (t+1) Lemma B.6. Define Wt := i=1 wt (i). Then, for any step t ≥ 1, f (t+1)
X
Wt ≤ Wt−1 +
w0 (i).
i=f (t)+1
Proof. We re-express Wt by decomposing the weights: Wt =
f (t) X
f (t+1)
wt (i) +
i=1
X
wt (i)
i=f (t)+1
f (t)
≤
X f (t+1)
wt (i) +
i=1
X
w0 (i)
(Definition of weight initialization)
i=f (t)+1
Pf (t) Pf (t) Thus, it suffices to prove that i=1 wt (i) ≤ Wt−1 = i=1 wt−1 (i). Pf (t) We go about this by showing that i=1 wt (i) − Wt−1 ≤ 0: f (t) X
(wt (i) − wt−1 (i))
i=1
=
f (t) X
wt−1 (i)(1 + γ)λi (xt ,ŷt ) (1 − γ)λi (xt ,yt ) − wt−1 (i)
i=1 f (t)
≤
X
(wt−1 (i)(1 + γλi (xt , ŷt ))(1 − γλi (xt , yt )) − wt−1 (i))
i=1
where the upper bound follows from the fact that (1 + γ)u ≤ 1 + γu and (1 − γ)u ≤ 1 − γu for any u ∈ [0, 1] and γ ∈ [0, 1]. Note that because the range of rewards is [0, 1], λi (x, y) ∈ [0, 1] as well. Simplifying the equation, we can equivalently rewrite as
γ
f (t) X
wt−1 (i) (λi (xt , ŷt ) − λi (xt , yt )) − γ 2
i=1
=γ
f (t) X
wt−1 (i)λi (xt , ŷt )λi (xt , yt ))
i=1
f (t) X
wt−1 (i) (ri (xt , yt ) − ri (xt , ŷt )) − γ 2
i=1
f (t) X
wt−1 (i)λi (xt , ŷt )λi (xt , yt ))
i=1
By definition of our choice of ŷt , the first term is upper bounded by 0, and because all weights and γ values are non-negative, the second term is also upper-bounded by 0, and we conclude that the difference is at most 0, proving the lemma. 21
We now proceed to prove Theorem B.5. Proof of Theorem B.5. We first note that unrolling Lemma B.6 gives a constant upper bound on any Wt : f (t+1)
X
Wt ≤ Wt−1 +
f (t+1)
w0 (i) ≤
X
X
≤
i=1
i=f (t)+1
w0 (i) ≤ W.
i=1
For a particular reward function ri , the first step where ri is considered by the algorithm is at f −1 (i) + 1. We focus on how much additional regret the algorithm can incur after first introducing ri . At any timestep T > f −1 (i), suppose the algorithm has accumulated R̂i (T ) regret compared to the rewardmaximizing labels for ri since initially being considered by the algorithm at t = f −1 (i) + 1. Similarly denote Ri (T ) as the regret suffered by the demonstrator after timestep f −1 (i). By definition of our algorithm, the weight on ri is equal to wT (i) = w0 (i)(1 + γ)R̂i (T ) (1 − γ)Ri (f
−1
(i)+1:T )
≤ WT ≤ W.
Where we get an upper bound of W from Lemma B.6. Solving for R̂i (T ), we conclude that 1 −1 R̂i (T ) ≤ log2 (W/w0 (i))/ log2 (1 + γ) + Ri (f (i) + 1 : T ) log2 ( )/ log2 (1 + γ) . 1−γ 1 2 (1/(1−γ)) ≤ 1/γ and loglog ≤ 1 + 2γ, and thus we conclude that Noting that for γ ∈ (0, 3/4], we have log (1+γ) (1+γ) 2
2
R̂i (T ) ≤ log2 (W/w0 (i))/γ + (1 + 2γ)Ri (f −1 (i) + 1 : T ). Thus we have bounded the regret after ri is first considered. We can bound the regret before ri is first considered as f −1 (i) because the rewards line in [0, 1], and thus conclude a total bound on the regret of T T Mi,opt − M̂i,alg ≤ log2 (W/w0 (i))/γ + (1 + 2γ)Ri (f −1 (i) + 1 : T ) + f −1 (i).
We now prove the optimal demonstrator case for binary rewards: Proof of Theorem B.4. We first note that unrolling Lemma B.6 gives a constant upper bound on any Wt : f (t+1)
f (t+1)
Wt ≤ Wt−1 +
X
w0 (i) ≤
X
≤
i=1
i=f (t)+1
X
w0 (i) ≤ W.
i=1
For a particular reward function ri , the first step where ri is considered by the algorithm is at f −1 (i) + 1. We focus on how much additional regret the algorithm can incur after first introducing ri . At any timestep T > f −1 (i), suppose there have been M steps where the algorithm outputted a ŷt with 0 reward on ri since initially being considered by the algorithm at t = f −1 (i) + 1. By definition of our algorithm, the weight on ri is equal to wT (i) = w0 (i)2M ≤ WT ≤ W. Where we get an upper bound of W from Lemma B.6. Solving for M , we conclude that M ≤ log2 (W/w0 (i)). Thus we have bounded the number of mistakes after ri is first considered. We can bound the number of mistakes before ri is first considered as f −1 (i), and thus conclude a total bound on the number of mistakes of T X
(1 − ri (xt , ŷt )) ≤ log2 (W/w0 (i)) + f −1 (i).
t=1
We conclude that this bound holds for all such T , as the right-hand-side has no dependence on T .
22