acceptodds
Under review as a conference paper at ICLR 2027

On the Sample Complexity of Language Generation in the Limit with Noise, Prompts, and Feedback

Abstract

Language generation in the limit is a learning paradigm in which a learner observes an infinite stream of strings from an unknown target language, chosen from a countable collection, and must eventually produce strings not yet seen. This task is always tractable, i.e., for any countable collection, there exists a learner that eventually succeeds. A natural follow-up question is: how many examples does the learner need before it can do so? Previous work established upper and lower bounds for regular, locally threshold testable (LTT), and context-free languages. However, the sample complexity has not been studied under the extensions of the framework that model noisy input, conditioning on a prefix, and feedback. In this paper, we analyze the sample complexity of language generation in each of these settings. First, we study the sample complexity for partially-ordered (PO) languages, a class not previously analyzed in this framework, and we establish exponential upper and lower bounds. Next, we show that for context-free languages, the sample bounds remain uncomputable in every setting. Finally, we show that for regular, LTT, and PO languages, finite noise increases the sample complexity by only a linear additive term, prompting generally leaves the bounds unchanged, and finite feedback can sometimes reduce them exponentially.

Primary area:
learning theory
Keywords:
language generation in the limit, language generation, noisy generation, generation with feedback, prompted generation

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_zyFDOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper considers the sample complexity of language generation in the limit for finite collections. The results of Arenas et al establish that sample complexities can be very large (doubly exponential) even for regular languages. This paper consider the subclass of partially-ordered languages and achieves better bounds that are only single exponential. It also considers extensions to prompted generation and to noise.

Critical strengths

Given the negative results of Arenas et al, it is important find classes of language where better bounds can be obtained.

Prompted generation captures an important issue for language generation in the limit, and this paper makes progress on building techniques for analyzing it.

Critical weaknesses

The paper needs to do a better job of motivating the class of partially-ordered languages, given that the main positive result on sample complexity occurs here.

Questions for authors

Can you give a stronger motivation for why partially-ordered languages are a natural family of languages to study in this context?

Can you relate the approach you're taking to the mistake-bound approach in Jimenez, Héctor, Alexander Kozachinskiy, and Vicente Opazo. "Polynomial-Time Mistake-Bounded Language Generation." arXiv preprint arXiv:2606.16077 (2026). and in Kleinberg, Jon, Charlotte Peale, and Omer Reingold. "Mistake-bounded language generation." arXiv preprint arXiv:2605.10809 (2026).

2 comments

Can you give a stronger motivation for why partially-ordered languages are a natural family of languages to study in this context?

Arenas et al. (2026) give an exponential lower bound for non-erasing pattern languages. Since this class is identifiable in the limit, one might expect it to have favorable properties for generation in the limit as well. They show that this is not the case, and that the sample complexity is determined only by the size of the largest finite intersection. They leave open under which structural conditions generation can be done efficiently. The partial order on the automaton states is a step in this direction: it reduces the bound from double exponential for general regular languages to single exponential, with an exponent that is linear in each of the number of states and the size of the collection, considerably smaller than for LTT languages. The bound is still exponential, so this does not make generation efficient in general, but it shows which structure of regular languages helps improve the double-exponential bound.

Can you relate the approach you're taking to the mistake-bound approach in Jimenez, Héctor, Alexander Kozachinskiy, and Vicente Opazo. "Polynomial-Time Mistake-Bounded Language Generation." arXiv preprint arXiv:2606.16077 (2026). and in Kleinberg, Jon, Charlotte Peale, and Omer Reingold. "Mistake-bounded language generation." arXiv preprint arXiv:2605.10809 (2026).

Thank you for these pointers! This recent line of work studies a different but complementary question: it analyzes the total number of mistakes a learner makes instead of when it makes the last mistake. Kleinberg et al. (2026) show that, for any finite collection, there is a learner whose total number of mistakes is at most the minimum of the logarithm of the size of the collection and its closure dimension. In contrast, our results show after how many distinct examples, depending on the language class, the learner can be always correct. Together, these results say that the learner can make mistakes rarely, but it may need many examples before it never makes mistakes again. These results do not consider the learner's computation. Jimenez et al. (2026) add a polynomial-time requirement and show that, under the strong RSA assumption, some collections admit no polynomial-time learner with few mistakes. We will add a discussion of both papers to the related work section.

Thank you for the replies. I appreciate that partially-ordered languages result in a better bound, but I am still not convinced that they are an inherently natural family of languages for this particular problem. I will maintain my score at 3, weak acceptance.

Reviewer_7PjfOpenReview ↗
Rating
3
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies language generation under a theoretical model introduced by Kleinberg and Mullainathan. In contrast with most previous work in this area, this paper mainly investigates language generation for finite collections where the languages are given by some explicit representation such as NFAs. The paper proves multiple results for different generation settings including noise, prompting, and feedback, and for different classes of languages such as regular, LTT, and PO. For collections of PO languages, the paper shows a sample complexity bound of ∣Σ∣∣C∣(s−1)+1|\Sigma|^{|C|(s-1)+1}. They also show that a noise level of kk loses at most an additive k∣C∣k|C| compared to the base bound for any finite collection. In summary, the paper provides a set of upper bounds on the sample complexity of uniform generation, and analyzes how the bounds are affected by variations such as noise, prompting, and feedback.

Critical strengths

The paper gives a comprehensive set of upper bounds on sample complexity for many different settings of language generation. The paper is also well-written and easy to read, and the main results are clearly presented.

Critical weaknesses
  1. The motivation for studying PO and LTT languages within this framework is not clearly explained, and it is also not clear whether the results and techniques in this paper lead to insights on more general collections of languages.

  2. Although there are some lower bound results in the appendix, there is a lack of discussion about lower bounds in the main body of the paper, and the upper bound results are not systematically compared with the lower bounds. This makes it hard to interpret how strong the results in Table 1 are.

Questions for authors
  1. The paper mainly focuses on showing upper bounds on the sample complexity for different generation settings. The discussion on lower bounds is mainly in the appendix, and it is not immediately clear which of the results in Table 1 are tight. Also, some of the lower bounds (Theorems 7 and 10), only exhibit a single collection instead of an infinite family of collections that is tight for all values of Σ\Sigma, ss and ∣C∣|C|. It would be nice for the introduction to broadly clarify what the lower bounds are, and how far apart the lower and upper bounds are.

Minor comments:

  1. Does proposition 5 trivially follow from the fact that all finite collections are uniformly generatable even without feedback?

  2. Proposition 2 and the general notion of uniform generation at noise level kk seem to be related to the work of Li and Zhang [LZ26] (Theorem 2.16, Lemma 3.1). It would be good to briefly discuss this connection if the work seems relevant.

1 comment

The motivation for studying PO and LTT languages within this framework is not clearly explained, and it is also not clear whether the results and techniques in this paper lead to insights on more general collections of languages.

Arenas et al. (2026) show that finite collections of regular languages need a double-exponential number of examples, and that LTT languages need single exponential. We include LTT languages to extend their results to noise, prompts and feedback. They also give an exponential lower bound for non-erasing pattern languages. This class of languages is identifiable in the limit, so one might expect it to have favorable properties for generation as well. They show that this is not the case and that the sample complexity is determined only by the size of the largest finite intersection. They leave open under which structural conditions generation can be done efficiently. The partial order on the automaton states is a step in this direction: it reduces the bound from double exponential for general regular languages to single exponential, with an exponent linear in each of the number of states and the size of the collection, considerably smaller than for LTT languages. The bound is still exponential, but this shows which structure of regular languages helps improve the double-exponential bound. Finally, notice that our results on noise, prompting and feedback hold for any finite collections of infinite languages.

The paper mainly focuses on showing upper bounds on the sample complexity for different generation settings. The discussion on lower bounds is mainly in the appendix, and it is not immediately clear which of the results in Table 1 are tight. Also, some of the lower bounds (Theorems 7 and 10), only exhibit a single collection instead of an infinite family of collections that is tight for all values of Σ\Sigma, ss and ∣C∣|\mathcal{C}|. It would be nice for the introduction to broadly clarify what the lower bounds are, and how far apart the lower and upper bounds are.

We agree that this should be discussed in the main text, and we will include it in the revision. For regular languages, the upper and lower bounds are both double-exponential but do not match in all parameters. For LTT languages, the gap is bigger. For the two profiles of size O(n)O(n) over an alphabet of size nn, the lower bound is 2n+2k2^n+2k whereas the upper bound is nO(n5)+2kn^{O(n^5)}+2k, so there is a gap in the exponent. For PO languages, we give a single-exponential upper bound, and Theorems 7 and 10 use a single collection where it is nearly reached (19 strings vs. an upper bound of 32). This is indeed an example, not an asymptotic lower bound. We will clarify these in the revision and remove the tightness claim.

Does proposition 5 trivially follow from the fact that all finite collections are uniformly generatable even without feedback?

Yes, this is correct. A learner that asks no queries is also a learner that asks at most ff queries, therefore the feedback-augmented closure dimension is upper bounded by the standard closure dimension, which we know is finite for finite collections. We state the proposition for completeness, because we can only analyze the sample complexity for collections that are uniformly generatable in the first place.

Proposition 2 and the general notion of uniform generation at noise level kk seem to be related to the work of Li and Zhang [LZ26] (Theorem 2.16, Lemma 3.1). It would be good to briefly discuss this connection if the work seems relevant.

Thank you for this reference. It is indeed closely related, and we will include a discussion in our paper. They define related notions of uniform generation at a fixed noise level and characterize generatability using the noisy closure dimension and how it compares at various noise levels. Our results are complementary: for finite collections generatability always holds, and we bound the number of examples as a function of the noise level. Our Proposition 2 is a quantitative version of their characterization for finite collections.

Reviewer_x2qgOpenReview ↗
Rating
4
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies the sample complexity of uniform language generation from a known finite collection C\mathcal{C} of infinite languages. This is the smallest number mm such that some generator, after seeing mm distinct examples, always outputs a string from the target language that has not appeared in the input, for every target and every adversarial enumeration.

The only prior bounds on this number for concrete language classes are due to Arenas et al. (2026). They show that it is doubly exponential in ∣C∣|\mathcal{C}| for regular languages and singly exponential for locally threshold testable (LTT) languages, and that no algorithm can compute it from the grammars of context-free languages.

The authors' first result builds on these bounds and shows that, for languages recognized by partially ordered (PO) automata with at most ss states over an alphabet Σ\Sigma, ∣Σ∣∣C∣(s−1)+1|\Sigma|^{|\mathcal{C}|(s-1)+1} examples suffice. This bound is singly exponential, with a smaller exponent than the LTT bound. Their next results study three extensions of the model. The second result shows that kk noisy examples increase each upper bound by k∣C∣k|\mathcal{C}|. The third shows that prefix prompts do not change the regular and PO bounds. The fourth shows that a budget of ff membership queries decreases these bounds by replacing ∣C∣|\mathcal{C}| with ∣C∣−f|\mathcal{C}|-f. They also give lower-bound examples and discuss noncomputability of sample bounds for context-free languages in each setting.

Critical strengths

I am in favor of acceptance. The paper is clearly written, and I particularly like how the authors isolate the common argument behind the bounds of Arenas et al. (2026): bound the length of the longest string in any finite intersection, and then count the strings up to that length. This makes the extensions easy to follow. Organizing and explaining prior ideas this well is a useful contribution. (I think this kind of expository effort deserves more credit.)

The bound for partially ordered automata is a nice example of how the structure of an automaton affects sample complexity. In a partially ordered automaton, a run never returns to a state it has left. If the intersection of ∣C∣|\mathcal{C}| such languages is finite, accepting paths in the product automaton repeat no state, so every step advances at least one component, and each component advances at most s−1s-1 times. Accepted strings therefore have length at most ∣C∣(s−1)|\mathcal{C}|(s-1), whereas for general NFAs the product has s∣C∣s^{|\mathcal{C}|} states and the length bound is s∣C∣−1s^{|\mathcal{C}|}-1. This brings the sample complexity from doubly exponential down to singly exponential in ∣C∣|\mathcal{C}|.

I also like the LTT feedback example: an adversary can answer each membership query so that it eliminates at most one candidate language. This gives a concrete reason why queries need not repeatedly halve the candidate set.

Critical weaknesses

I expect most of the following issues to be straightforward to resolve, and would appreciate details in the rebuttal, particularly for Theorem 13.

  1. In Theorem 13, how does the reduction ensure that a hard pair survives the generator's adaptive queries? Two distinct languages can be identified with one membership query, so a large finite intersection alone perhaps does not establish hardness for a positive feedback budget.
  2. Definition 14 permits a prompt-dependent threshold, whereas Example 2 only rules out a threshold shared by all prompts. For its prompt pnp_n, n+1n+1 distinct examples with that prefix suffice, and Theorem 11 makes this collection prompted uniformly generatable. Which quantifier order is intended?
  3. The PO lower bounds in Theorems 7 and 10 use a single fixed collection (two languages, three states, binary alphabet). A family that grows in ∣C∣|\mathcal{C}| and ss is needed to support the exponential lower bound and the claim that the exponent cannot be lowered. More generally, the discussion of tightness should specify which parameter dependences match. For instance, Appendix D.3 calls the LTT bound tight, but Theorem 9 gives 2n+2k2^n+2k for two profiles of size O(n)O(n) over nn symbols, whereas Corollary 5 gives nΘ(n5)+2kn^{\Theta(n^5)}+2k.

The paper would benefit from making its connections to prior arguments more explicit, particularly Raman and Raman (2025) for the additive-noise bound (their Corollary 3.4 bounds the noisy closure dimension by k∣C∣+dk|\mathcal{C}|+d, where dd is the size of the largest finite intersection) and Masopust and Krötzsch (2021) for the PO depth argument (see the proof of their Theorem 3.3).

Questions for authors

Please see weaknesses

2 comments
AuthorsOpenReview ↗

Rebuttal (part 1)

In Theorem 13, how does the reduction ensure that a hard pair survives the generator's adaptive queries? Two distinct languages can be identified with one membership query, so a large finite intersection alone perhaps does not establish hardness for a positive feedback budget.

You are right. Our proof assumed that the two languages of Arenas et al. (2026) remain consistent after the queries. We give the following construction instead for f=1f=1, which is enough to show that there is no algorithm that, given a finite collection C\mathcal{C} of infinite context-free languages represented as CFGs and a feedback budget ff, always outputs mm s.t. C\mathcal{C} is mm-generatable with at most ff queries.

Let AA and BB be the two languages of Arenas et al. (2026), whose intersection has 2t2^t strings if the Turing machine halts in tt steps. Consider four languages with strings of the form w1⋄w2⋄w3⋄w4w_1\diamond w_2\diamond w_3\diamond w_4 such that: 1) w1∈A,w2R∈B,w3=w4Rw_1\in A, w^R_2 \in B, w_3=w^R_4, 2) w1=w2R,w3∈A,w4R∈Bw_1 = w^R_2, w_3 \in A, w^R_4 \in B, 3) w1=w4R,w2=w3Rw_1 = w^R_4, w_2 = w^R_3, and 4) w1∈B,w2R∈A,w3∈B,w4R∈Aw_1 \in B, w^R_2 \in A, w_3 \in B, w^R_4 \in A, where wRw^R is reversed ww. All four languages are context-free and infinite when AA and BB are. Notice that any two of them have a finite intersection. The constraints of two languages force every block to be a string of A∩BA \cap B or the reversal of one. For instance, the intersection of 1) and 2) consists of the strings x⋄xR⋄y⋄yRx\diamond x^R\diamond y\diamond y^R with x,y∈A∩Bx, y \in A \cap B, and that of 1) and 3) of the strings x⋄xR⋄x⋄xRx\diamond x^R\diamond x\diamond x^R with x∈A∩Bx \in A \cap B. All four languages contain the 2t2^t strings x⋄xR⋄x⋄xRx\diamond x^R\diamond x\diamond x^R with x∈A∩Bx \in A \cap B. Therefore, every subcollection of at least two languages has a finite intersection with at least 2t2^t strings. Now consider a learner with one feedback query. Until it asks the query, the adversary shows only strings x⋄xR⋄x⋄xRx\diamond x^R\diamond x\diamond x^R with x∈A∩Bx \in A \cap B, which are in all four languages, so all four stay consistent. Whatever string the learner queries, either at least two of the four languages contain it or at least two do not, so the adversary can answer in a way that leaves at least two languages consistent. The adversary then enumerates their finite intersection, after which the generator has no string that is guaranteed to be in the target. The collection is therefore not mm-generatable with one feedback query for any m≤2tm \leq 2^t, and the reduction from the halting problem goes through as in Arenas et al. (2026).

We will update the theorem statement and its proof accordingly.

Definition 14 permits a prompt-dependent threshold, whereas Example 2 only rules out a threshold shared by all prompts. For its prompt , distinct examples with that prefix suffice, and Theorem 11 makes this collection prompted uniformly generatable. Which quantifier order is intended?

Thank you for spotting these inconsistencies. We meant a threshold shared by all prompts: there exists a generator and an mm such that, for every prompt pp, generation succeeds after the learner sees mm distinct examples continuing pp. Definition 14 and Theorem 11 were stated wrongly using a threshold that depends on the prompt. With a new definition 14 that quantifies mm before pp, Example 2 becomes correct.

The PO lower bounds in Theorems 7 and 10 use a single fixed collection (two languages, three states, binary alphabet). A family that grows in ∣C∣|\mathcal{C}| and ss is needed to support the exponential lower bound and the claim that the exponent cannot be lowered. More generally, the discussion of tightness should specify which parameter dependences match. For instance, Appendix D.3 calls the LTT bound tight, but Theorem 9 gives 2n+2k2^n+2k for two profiles of size O(n)O(n) over nn symbols, whereas Corollary 5 gives nΘ(n5)+2kn^{\Theta(n^5)}+2k.

This is correct. For PO languages, what we show is a single-exponential upper bound and an example where it is nearly reached (19 strings in the intersection vs. an upper bound of 32). This is indeed not an asymptotic lower bound. For the other classes we show something stronger, with lower bounds given by infinite families: for regular languages, the upper and lower bounds are both double exponential, and for LTT languages both are single exponential, although the exponents differ. In the revision we will frame the PO result as an upper bound with a near-matching example.

(continued in next comment)

AuthorsOpenReview ↗

Rebuttal (Part 2)

(continued from last comment)

The paper would benefit from making its connections to prior arguments more explicit, particularly Raman and Raman (2025) for the additive-noise bound (their Corollary 3.4 bounds the noisy closure dimension by k∣C∣+dk|\mathcal{C}|+d, where dd is the size of the largest finite intersection) and Masopust and Krötzsch (2021) for the PO depth argument (see the proof of their Theorem 3.3).

Proposition 2 does indeed follow easily from the proof of Corollary 3.4 of Raman and Raman. In our paper we simply state it in the form we need. Similarly with the depth argument of Masopust and Krotzsch. We will make sure these connections are clear in the updated version.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of updates

Dear reviewers,

Thank you very much for carefully reading our paper and for your detailed feedback and suggestions. We have uploaded a revision that addresses the points discussed. Specifically, we made the following changes:

  • We updated the theorem statement and the proof for context-free languages with feedback to include the construction detailed in our response to reviewer x2qg.
  • We fixed the inconsistencies between Definition 14, Example 2 and Theorem 11 for prompted generation.
  • We added a discussion of the gaps between the upper and lower bounds. Since our initial responses, we also extended the PO example to an asymptotic family. For every s≥2s\geq2, there are two infinite languages over a binary alphabet, each recognized by a PONFA with ss states, whose intersection contains (2ss)−1=Θ(4s/s)\binom{2s}{s}-1=\Theta(4^s/\sqrt{s}) strings. This gives an exponential lower bound in ss, matching our upper bound within a factor of Θ(s)\Theta(\sqrt{s}) for these parameters. We also extended the noisy lower bound using this family.
  • We now give more details about why we study PO languages.
  • We made more explicit the connections to past work, especially Corollary 3.4 of Raman and Raman (2025), the depth argument of Masopust and Krötzsch (2021) and the fixed noise setting of Li and Zhang (2026).
  • Our Related work section now discusses the recent papers studying mistake-bounded generation. We also included a short connection between this line of work and ours in the conclusion.

Since the submission deadline, we have carefully revised our draft so you might notice some other minor differences. The only difference worth mentioning is the following. We noticed an inconsistency between our definition of size of a profile and that of Arenas et al. (2026), which now results in an upper bound for prompted generation for LTT languages that includes a constant factor in the exponent instead of a dependency on the size of the prompt.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.