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