acceptodds
Under review as a conference paper at ICLR 2027

Non-Uniform Language Generation with Replay

Abstract

In the framework of language generation in the limit introduced by KM24, an algorithm receives example strings from an unknown target language, which is chosen from a known collection of potential languages. The goal for the algorithm is to eventually generate only strings that belong to the target and have not appeared among the examples. The stronger notion of non-uniform generation requires correct generation after a finite number of distinct examples that may depend on the target language but not on its enumeration LRT25,CP25. RVS26 introduced a replay model in which the adversary can also provide the algorithm's previous outputs as examples, even when those outputs lie outside the target language. They showed that some countable collections cannot be non-uniformly generated with replay, and left finding a characterization as an open question. In this paper, we resolve this question by giving a complete characterization of non-uniform generation with replay for arbitrary collections over a countable universe. For countable collections, we obtain a simpler characterization: generation is possible if and only if, for each language , every intersection of with finitely many other languages is either infinite or has size bounded by a constant depending only on . Beyond determining whether non-uniform generation is possible, we characterize how many distinct inputs an algorithm needs before it must generate correctly. For any assignment of a positive integer to each language , we determine an exact characterization for when there exists an algorithm that generates correctly from every target once it has received at least distinct inputs.

Primary area:
learning theory
Keywords:
Language Generation in the Limit, Language Generation

Reviews

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

This is a theory paper that studies a setting where an adversary iteratively shows a generator examples from a target language and the generator needs to respond in each round with own examples. The goal is that the generator outputs only correct examples of a target language after a specific number of distinct inputs. The authors bound the number of distinct inputs that are required for different languages and in the scenario that the adversary can repeat examples (including wrong examples from the generator). This resolves an open question from Racca et al. (2026). The authors show exactly when such a generator can exist and which sample thresholds it can achieve for each language. They also identify which guarantees become impossible with replay. The results are established through proofs.

Critical strengths

Complete characterization of a previously unresolved setting. I'm not really familiar with this topic, but I think that the authors characterize many scenarious that have been unsolved before in this field. They resolve an open question from Racca et al. (2026) by giving exact conditions for when non-uniform generation with replay is possible and which sample thresholds are achievable, and also extend in to other assumptions. So I would consider it a meaningful theoretical contribution.

Critical weaknesses

1. Unclear significance beyond the studied setting. The paper resolves an open theoretical question, but I found it difficult to understand what the results teach us about language generation more broadly. The manuscript contains only the theoretical results and proofs, but little to no motivation or implications of their findings. For example, what can we learn about training models on generated data? I think the studied setting is too narrow for a broad audience like ICLR, I would like the authors to explain more clearly why these results matter.

2. Limited examples showing how the results can be used. The examples help explain the mathematical results, but I missed an example showing how they help us understand a concrete generation problem. Such an example would make the contribution easier to assess for readers outside this research area.

Questions for authors
  1. What broader understanding of language generation follows from these results? For example, do they tell us anything about when training on generated data is harmful or safe?
  2. What can we do with these results that was not possible to infer from prior works?
  3. Can you give a concrete example where your characterization helps us understand whether generation is possible or how many examples are needed?

Thank you! This would help me assess the significance beyond resolving the formal open question.

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

This paper studies non-uniform language generation under replay. A generator knows a collection of infinite languages over a countable universe and receives strings from an unknown target language in that collection. In each round, the adversary may provide either a target string or any previous output of the generator (this is the "replay" part), including an incorrect output, and the generator is not told which. The goal is to output target strings that have not appeared among the inputs once the number of distinct inputs reaches a threshold depending only on the target. Replayed outputs count toward this threshold.

Racca, Valko, and Sanyal (2026, ICML) introduced this replay model as a learning-theoretic view of model collapse. Model collapse refers to the loss of quality and diversity in generative models trained on data that contains outputs of earlier models. Replay models a simple form of this, in which the generator's earlier outputs, including incorrect ones, return as inputs. Racca et al. showed that replay preserves uniform generation and its optimal sample complexity, but can prevent non-uniform generation even for a countable collection. They left open the problem of characterizing non-uniform generation under replay.

The authors give three main results:

  1. Their first result characterizes generatability for arbitrary collections over a countable universe using finite enlargements of the languages (Theorem 3.2).
  2. Their second result characterizes which prescribed thresholds can be achieved simultaneously (Theorem 4.1). Thresholds d(L)d(L) are achievable if and only if every subfamily with finite intersection and bounded thresholds has fewer common strings than its smallest threshold. Without replay, the corresponding condition uses the largest threshold (Appendix A), so the two results identify exactly which thresholds replay makes impossible.
  3. Their third result shows that, for countable collections, generation is possible if and only if, for each target, every intersection with finitely many other languages is either infinite or has size bounded by a constant depending only on that target (Corollary 5.1). This condition remains necessary for uncountable collections but is no longer sufficient (Proposition 5.2).
Critical strengths

I think the paper gives a clean answer to the question left open by Racca et al. The results characterize both when generation is possible and which language-dependent thresholds can be achieved simultaneously. I especially like the countable characterization, since it is stated directly in terms of intersections of the original languages and recovers the impossibility example of Racca et al. as a special case. The comparison with generation without replay is also informative. The two-language example in Appendix A shows concretely how replay lets the adversary use the smallest threshold in a subfamily to force correct outputs for every language in it.

The proofs use natural closure and diagonalization arguments. For example, the algorithms start as in the uniform replay algorithm of Racca et al., outputting the first input until it is safe to generate, and then retain this initial sample of genuine target strings. Retaining the sample allows the main algorithms to use the increasing distinct-input count without letting later replayed errors rule out the true target. This is a simple way to handle the contamination caused by replay.

The paper is well written and the mathematical exposition is easy to follow. The proofs appear correct.

Critical weaknesses

My main reservation concerns the broader relevance of the model. The paper addresses a fairly specific question within language generation in the limit. This framework abstracts away the distributions over strings and the training procedures of language models, so the implications of the characterizations for actual language-model behavior are indirect. Racca et al. motivate replay through model collapse and relate their results to practices such as data cleaning, watermarking, and output filtering. This paper does not discuss this motivation. More discussion of which insights might carry over to learning from generated data would be helpful. For instance, the authors could explain what the gap between the threshold conditions with and without replay suggests in that setting.

Questions for authors

Please see weaknesses

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

The paper studies language generation in the limit under a replay model. It builds upon recent work by Racca, Valko, and Sanyal (2026), which show that some countable collections cannot be non-uniformly generated with replay. This submission provides: 1. A characterization of non-uniform generation under replay for arbitrary collections over a countable universe via enlarged set intersections (KE(S)K_E(S)). 2. A characterization of achievable threshold profiles (d(L)d(L)), determining how many distinct inputs are required before correct generation is guaranteed. 3. Extensions to noisy generation (combining replay with a known finite noise level bb) and almost-sure derandomization.

Critical strengths
  1. Tries to answer the open question posed by Racca, Valko, and Sanyal (2026) by providing a characterization of non-uniform generation with replay.

  2. The paper is clearly written, cleanly structured, and covers multiple extensions (noise levels, threshold profiles, and almost-sure derandomization).

  3. The proofs and structural progression from deterministic replay to noisy replay and randomization are logically sound.

Critical weaknesses

While the paper solves an open question in theoretical learning theory, it faces severe scrutiny at generalist machine learning conferences like ICLR (even for the learning theory topic). 1.The paper assumes “no computability or running-time restriction on the algorithm: it may be any function from finite input sequences to output strings”. At ICLR, results that rely on uncomputable functions or arbitrary non-effective settheoretic constructions often struggle unless they offer clear computational counterparts or algorithmic insights. This is purely mathematical logic/combinatorics rather than machine learning, as real-world language models and algorithms must operate under finite compute, polynomial time, and finite parameter spaces.

  1. The paper's motivation touches upon "model collapse" via replay (citing Racca et al., 2026). However, the model abstracts away all probabilistic, statistical, and continuous aspects of modern generative models. Language generation in this framework treats languages as crisp infinite sets of strings and adversaries as combinatorial selectors. Exact string replay, crisp set membership, and countable universes bear little resemblance to neural autoregressive generation over continuous token logits.

  2. The main characterization theorems rely on structural conditions such as the existence of finite sets EHE_H such that DE(L)<∞D_E(L) < \infty, or capacity bounds cb(F)<min⁡L∈Fd(L)c_b(\mathcal{F}) < \min_{L\in\mathcal{F}} d(L). For arbitrary or uncountable collections, verifying whether these conditions hold can be exceptionally opaque. If the characterization theorem is so abstract that it cannot be easily checked for natural, interesting classes of languages beyond pathological counterexamples, its utility as a foundational tool is severely diminished.

Based on the above reasons, this paper is more suitable for other theoretical venues other than ICLR (including the learning theory topic).

Questions for authors

See weaknesses.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.