- Rating
- 2
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 2
Read review
Paper summary
This paper studies non-uniform language identification in the limit, characterizing conditions under which countable language classes admit non-uniform or uniform identification. It extends these results to variants with relaxed output requirements or auxiliary information, such as negative examples or color annotations.
Critical strengths
- The paper introduces novel theoretical characterizations for non-uniform and uniform language identification, extending prior work on uniform identification to address scenarios where the number of required examples depends on the target language.
- It provides rigorous proofs for key theorems, including conditions for non-uniform identification and uniform identification, which are critical contributions to computational learning theory.
Critical weaknesses
- The paper lacks empirical experiments to validate the theoretical results. While theoretical analysis is central to learning theory, the absence of practical demonstrations or applications limits the scope of the contribution.
- The paper does not address potential limitations of its proposed characterizations. For instance, it does not discuss how the assumptions (e.g., finite pairwise intersections) might be violated in practical scenarios involving real-world language data.
Questions for authors
- The paper has no empirical experiments to back its theory, and the lack of real demonstrations weakens its contributions.
- The proposed characterizations’ limitations are undiscussed, including whether assumptions like finite pairwise intersections fail on real language data.
Response to Reviewer tgH2
Thank you for your review and comments. We answer your questions below and hope that you will strengthen your support for our paper.
“The paper lacks empirical experiments to validate the theoretical results.”
We agree that experiments are valuable when they can test the claims of a paper. Our work takes a deliberately abstract view of learning: it asks what is possible at all, for every learner and every order in which the examples may arrive. This view is what allows exact characterizations, and it also means that experiments cannot test our claims, since an experiment runs a fixed learner on finitely many sequences. Kleinberg and Mullainathan [4] make the same point about their results on language generation: given the emphasis on guarantees against an adversary in the limit, “there is not a natural opening for demonstrating the results experimentally,” and the same holds for the work of Gold and Angluin that introduced the model.
Many previous works on language identification or generation in ICLR and similar venues likewise do not contain experimental results, such as [1], [2], [3], and [4]. We also agree that it would be helpful to include more concrete ties to real-world scenarios or practical applications. For example, our study of identification in the limit with auxiliary information (i.e., colors or negative examples) may help us better understand what types of feedback are most helpful during post-training. We point to our response to Reviewer WAye for a more detailed discussion of the connection to post-training, as well as our response to Reviewer feED for additional discussion of the connection to real-world applications such as world models. We plan to incorporate these points into the final version of our paper.
[1] Language identification in the limit with computational trace. Binghui Peng, Amin Saberi, Grigoris Velegkas. ICLR’26
[2] Language Generation with Feedback: Queries and Mistakes. Steve Hanneke, Amin Karbasi, Anay Mehrotra, Grigoris Velegkas. ICML’26
[3] Representative Language Generation. Charlotte Peale, Vinod Raman, Omer Reingold. ICML’25
[4] Language Generation in the Limit. Jon Kleinberg, Sendhil Mullainathan. NeurIPS’24
“The paper does not address potential limitations of its proposed characterizations.”
Thank you for the suggestion. We will add a discussion of the limitations of our characterizations to the revision. Our characterizations apply to every countable collection, since each is an if-and-only-if statement. In particular, they also describe what happens when a condition fails, as it does for many natural collections. For example, even the class of regular languages contains many languages with infinite intersections, and so cannot be non-uniformly identified in the limit according to our characterization. In fact, it cannot be non-uniformly identified even with k-lists, in the approximate setting, or with terminal colors. We expect similar barriers in real-world scenarios: if a model is trying to decide between two different representations that have infinite overlap, it may need to see arbitrarily many examples in the worst case before learning the correct hypothesis.
Our results also have positive implications, both for which collections can be learned and for how we might want to train models. The conditions hold, for instance, for collections of languages over disjoint vocabularies, and for collections such as {Ln}n≥1 with Ln={a,a2,…,an}∪{bncj:j≥0}, which are non-uniformly identifiable although the number of examples needed grows with n. Our variants also show how to overcome the barrier above. For collections of infinite languages, lists of k guesses suffice exactly when no k+1 languages share infinitely many strings, and finitely many errors suffice exactly when any two languages that differ on infinitely many strings share only finitely many. Moreover, our result that two trace colors make every countable collection non-uniformly identifiable indicates that training on chain-of-thought traces can be very helpful (see again the connection to post-training in our response to Reviewer WAye). Our work also formalizes some general principles useful in practice: learning is harder when hypotheses overlap more; auxiliary information on top of examples is useful if it helps distinguish between related hypotheses; some hypotheses may take much more data to learn than others. We plan to incorporate this discussion into the final version.