- 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
- 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?
- What can we do with these results that was not possible to infer from prior works?
- 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.