acceptodds
Under review as a conference paper at ICLR 2027

Non-Uniform Language Identification in the Limit

Abstract

We study language identification in the limit and ask when the number of examples needed for identification can be bounded independently of their order of presentation. The learner must identify every target in the limit and must be correct whenever it has observed at least a target-dependent number of distinct positive examples. In learning theory, allowing the bound to depend on the target is known as a non-uniform guarantee. We characterize which countable collections admit non-uniform identification through a variant of Angluin's condition, and give a corresponding characterization of the stronger requirement of uniform identification. We extend these characterizations to variants studied in classical and recent work, asking whether more flexible outputs and additional information can overcome the obstacles to non-uniform identification. These variants permit a list of at most languages containing the target, finitely many disagreements with the target, or provide the learner with certain auxiliary information about the target language, as allowed by Charikar, Kleinberg, and Pabbaraju (2026). Even with these relaxations, non-uniform identification can fail for collections that admit identification in the limit without an order-independent bound. However, suitably chosen binary labels attached to every prefix of an example suffice for non-uniform identification of every countable collection of infinite languages.

Primary area:
learning theory
Keywords:
language identification in the limit, non-uniform learning, language generation in the limit, learning theory

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_tgH2OpenReview ↗
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
  1. 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.
  2. 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
  1. 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.
  2. 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
  1. The paper has no empirical experiments to back its theory, and the lack of real demonstrations weakens its contributions.
  2. The proposed characterizations’ limitations are undiscussed, including whether assumptions like finite pairwise intersections fail on real language data.
1 comment
AuthorsOpenReview ↗

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 kk-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\{L_n\}_{n\geq 1} with Ln={a,a2,…,an}∪{bncj:j≥0}L_n=\{a,a^2,\dots,a^n\}\cup\{b^nc^j: j\geq 0\}, which are non-uniformly identifiable although the number of examples needed grows with nn. Our variants also show how to overcome the barrier above. For collections of infinite languages, lists of kk guesses suffice exactly when no k+1k+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.

Reviewer_feEDOpenReview ↗
Rating
3(+2)
Confidence
2(−2)
Informativeness
2
Presentation
3(+1)
Soundness
3(+2)
Read review
Paper summary

The paper studies language identification in the limit and asks when the number of examples needed for identification can be bounded independently of their order of presentation. It characterizes which countable collections admit non-uniform identification through a variant of Angluin’s condition, and similarly characterizes uniform identification. It also shows that coloring each prefix of each example with one of just two colors, by a rule that does not depend on the collection, makes every countable collection of infinite languages non-uniformly identifiable.

Critical strengths
  • I liked the flow of the paper. The introduction takes its time, and I found the context useful.
  • The paper explores the problem in considerable depth. It looks at several natural variations and explains which obstacles remain and which can be overcome. The discussion of prior work is also thorough.
Critical weaknesses

n/a

Questions for authors

This setting seems closely connected to PAC learning. Beyond the parallels already discussed, can classical or more recent PAC results be adapted here, perhaps through a reduction? Could they give useful sample bounds or another way to understand your results?

3 comments
AuthorsOpenReview ↗

Response to Reviewer feED

Thank you for taking the time to review our paper. We were quite confused about several points in your review and felt the review did not correspond to our paper, and would appreciate some clarification.

For instance, your paper summary mentions that “This paper studies learning from ambiguous label sets when predictions may also be lists. It introduces a structural dimension and establishes sample complexity bounds, including a separation between exact and ambiguous supervision;” our paper does not discuss ambiguous labels, and there’s no mention of ambiguous supervision. Moreover, you write that “For a fixed prediction width, the upper and lower bounds match in their dependence on accuracy, up to log factors.” Could you clarify which result you are referring to here? None of our results contain any log factors, and we are not sure what you mean by dependence on accuracy.

Perhaps you have in mind our results on predicting lists of languages (kk-list identification). Although this is one aspect of our work, our main research question is broader and mostly concerned with non-uniform identification in the limit. We first characterize when non-uniform identification is possible in the standard setting, and then ask what changes under natural variants (one of which is kk-list identification).

“Why is this problem important, and what real-world scenarios fit your setting?”

Language identification in the limit is a classic model of a basic question in machine learning: after seeing examples from an unknown source, can a learner identify the source? In this model, the examples are strings and the source is a language. World models from deep learning face a similar task: they observe many examples of how the world works and learn a representation of the world that generated them. As such, our results can be seen at a high level as a framework for better understanding these world models.

Non-uniform identification asks whether enough distinct examples always suffice for this task, or whether particular informative examples must appear, and uniform identification asks whether the same number of examples suffices for every target. Such guarantees are standard in learning theory (lines 61–79), but to our knowledge they have not been characterized for language identification. The variants we study either relax the task (lists of guesses, or guesses with finitely many errors) or give the learner feedback of the kind that models receive in post-training (colors and negative examples, which we discuss in our response to Reviewer WAye). The summary by Reviewer WAye gives further perspective on this motivation.

Reviewer_feEDOpenReview ↗

Re: Response to Reviewer feED

Dear PC and authors,

I did make a slight oversight when compiling the review comments, and I apologize for that. I have corrected the review comments.

best, Reviewer feED

AuthorsOpenReview ↗

Follow-up: connection to PAC learning

Thank you so much for responding to us and for updating the review. We answer your question below.

“This setting seems closely connected to PAC learning. Beyond the parallels already discussed, can classical or more recent PAC results be adapted here, perhaps through a reduction? Could they give useful sample bounds or another way to understand your results?”

PAC learning is closely connected to distributional versions of identification and generation. The connection between language identification and statistical learning has a long history (e.g., Pitt, 1989 [1]). For language generation, Kalavasis et al. (STOC 2025 [2]) derive learning rates under random sampling, addressing a statistical counterpart of our question about how much data is needed.

A particularly relevant connection between identification and the PAC model is learning from positive examples with one-sided error: the predictor accepts nothing outside the target language, while potentially missing a small probability mass within it. Classical work beginning with Natarajan (STOC 1987 [3]) and Shvaytser (1990 [4]) analyzes this problem through the VC dimension of intersections of candidate concepts.

However, these statistical sample bounds rely on random sampling, whereas our target-dependent bound on distinct examples must hold for every presentation order. Therefore, they do not directly establish our guarantees. A reduction transferring PAC sample bounds to our setting would need to bridge this gap, which could be an interesting direction for future work. We will clarify this connection and distinction in the revision.

[1] Leonard Pitt. Inductive inference, DFAs, and computational complexity. AII, 1989.

[2] Alkis Kalavasis, Anay Mehrotra, and Grigoris Velegkas. On the Limits of Language Generation: Trade-Offs Between Hallucination and Mode Collapse. STOC, 2025.

[3] B. K. Natarajan. On Learning Boolean Functions. STOC, 1987.

[4] Haim Shvaytser. A Necessary Condition for Learning From Positive Examples. Machine Learning, 1990.

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

Language identification is a classical problem and its study is an exercise in getting quantifiers and definitions right so that we can understand more clearly what we do and do not understand. This is important theoretically because the basic problem is so important practically: when can we learn from only positive examples? Does the possibility of negative examples help or hurt? What about additional commentary about each example?

This is philosophically important because understanding the limits of identifiability in effect gives us limits on language classes in terms of what is reasonable. And that's how results should be understood here --- every definition and theorem is not just a result, but something that helps us navigate what is and is not reasonable.

Within this larger framework, a tempting to work with a worst-case setting on how the examples are given to us. The advantage of worst-case is clear: it avoids having to get bogged down in probabilistic assumptions about how examples are drawn. And in a way, all negative results on worst-case are precursors to asking the question: ok then --- could distributional knowledge help here? This is, of course, a larger theme within learning theory more generally.

Anyway, within this framework, the paper asks the question about non-uniform identification. For every language, is there a bound on the number of examples needed so that a learner, having seen that number of distinct examples, can properly identify the language. Some languages can be harder and some can be easier, but every one needs such a bound. (The learner does not need to know that they have passed the bound and that their guesses are now correct. They just happen to be so.) The paper advances the understanding of this considerably, and explores variants like what happens when we have additional commentary (generally helps, but is not a cure-all) or if we can get negative examples (surprisingly at first, but then nicely obvious in hindsight, it depends on if these negative examples are charged to our example count. If they are, they give the adversary a way to delay giving us useful information by simply saying No for examples that we already knew were No).

Critical strengths

This is a well written paper that conveys its core intuitions very clearly.

It is very much written for an audience that already knows the big picture --- I included the bigger picture of why all this matters in my summary for the ACs to read, but it is not in the paper itself. Within that audience, it is accessible and states the theorems and results at precisely the right level of informality so that the insight comes through without being bogged down by details.

The sequence of problems they study are natural gaps within their framing (I want to acknowledge that I do not follow the literature in this area and I am taking their literature search claims at face value --- someone probably should run a careful AI-driven literature search to check this out more thoroughly. But that someone is not me.) and their answers strike me as getting to the right illuminating distinctions.

Critical weaknesses

It is perhaps a failing of overbroad venues like ICLR, but within that context, I wonder if the paper wouldn't be more accessible for a broader audience if the larger philosophical frame were recapitulated. But I am reviewing the paper as though this was a special issue of a journal on learning theory dedicated to identifiability of languages. Since that is how the paper is written, and when a conference's call for papers lists "learning theory" --- authors deserve to be treated with respect.

To me, the biggest weakness is pedagogical. The paper would be considerably stronger for students if it had an explicit series of counterexamples and a table that showed how these counterexamples separate out the different senses that they've identified. There are some examples there, and it is my appreciation for them that makes me want this.

Because in a sense, the paper is at its strongest and most insightful when it shows how something that seems useful doesn't need to be as useful at it might seem if the definition allows the adversary the flexibility to neuter the usefulness.

Questions for authors
  1. I would have loved to see how things change if the adversary was replaced by having to specify a distribution that had some set of constraints on it --- no constraints; have to put mass on everything; have to stay within blah of a specified mass on all strings restricted to valid strings. Or whatever the authors feel is the most illuminating comparison that shows how much work the adversary has to do here instead of letting dice do it.

  2. Please expand on the modeling connection to post-training.

1 comment
AuthorsOpenReview ↗

Response to Reviewer WAye

Thank you for your thoughtful comments! We appreciate your positive feedback and your detailed account of the bigger picture in the paper summary.

“I wonder if the paper wouldn’t be more accessible for a broader audience if the larger philosophical frame were recapitulated.”

Thank you for the suggestion! We agree that the paper should develop this frame further for the broad ICLR audience, and we will incorporate a discussion in the updated version of our paper along the lines of your summary. We also plan to incorporate more concrete ties to real-world scenarios, for example the connection to post-training that we expand on later in this response.

“The paper would be considerably stronger for students if it had an explicit series of counterexamples and a table that showed how these counterexamples separate out the different senses that they’ve identified.”

Certainly. One counterexample we present is in our Technical Overview on line 215, in which we exhibit a collection demonstrating why non-uniform identification is harder than standard identification and why Angluin’s condition is not enough. Another example in Proposition 3.6 on line 364 shows why kk-list identification with stability is harder than without stability. We agree that further examples for our other results and variants would aid in understanding. We plan to incorporate your suggestion to use a series of counterexamples to demonstrate our characterizations and separate the senses in which identification in the limit may or may not be achieved.

“Please expand on the modeling connection to post-training.”

Our variants with auxiliary information (i.e., colors or negative examples) capture forms of feedback that language models receive during post-training. Since a coloring can be chosen to be as informative as possible, our results on colors (Theorem 3.8) describe the most that feedback of a given form can achieve. For example, colors can be thought of as an abstraction of chains of thought. Indeed, this was the original motivation of trace colorings, with a sequence of colors representing a sequence of internal steps a model went through to arrive at an answer. From this perspective, studying what can be learned (non-uniformly) with trace colorings, which we show includes every countable collection, helps us understand how much post-training with chains of thought can help. A similar idea can be applied to model other forms of feedback, for example human preference data, scores from a reward model, feedback from the environment (e.g., compiler errors, feedback from a game), etc. These can also be modeled at a high level with terminal colors or trace colors. Similarly, negative examples can model RLHF, in which models are given pairs of both “good” and “bad” examples. In practice, models can learn much more using this (which is supported by the positive result for standard identification with negative examples), but our result for non-uniform identification with negative examples suggests that the choice of examples matters: it does not help to see arbitrary or useless negative examples. We will expand on this connection in the revised version.

“I would have loved to see how things change if the adversary was replaced by having to specify a distribution that had some set of constraints on it.”

That is a great question. If the adversary had to specify a distribution but had no constraints on the distribution, then, using techniques from [1], we expect this to be equivalent to a worst-case adversary. In other words, even though specifying a distribution is in general much more restricted than a worst-case adversary model since it cannot adapt to actions taken by the learner, we expect our characterizations to remain the same if arbitrary distributions are allowed. On the other hand, understanding what happens with more restricted distributions is a very interesting question. However, it is still open even for language generation, so it is out of scope for our work but would be a very natural direction for future work. We will include a discussion of this in the revised version.

[1] On the Limits of Language Generation: Trade-Offs Between Hallucination and Mode Collapse. Alkis Kalavasis, Anay Mehrotra, Grigoris Velegkas. STOC’25

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.