Characterizing the Effect of Noise in Language Generation in the Limit

Aaron Li; Ian Zhang

REVIEW 1 major objections 4 minor 2 cited by

Characterizing the Effect of Noise in Language Generation in the Limit

T0 review · 1 major / 4 minor · reviewed 2026-08-03 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read For language generation in the limit, a single noisy example is the only threshold: any finite number of noise strings behaves the same as one, and one noisy string strictly shrinks what can be generated.

desk verdict New and correct modulo a patchable gap in Lemma 3.2; the noise-collapse and separation results answer open questions from RR25. read the letter →

arxiv 2601.21237 v2 pith:PQYSFVNM submitted 2026-01-29 cs.DS cs.CLcs.LG

Aaron Li , Ian Zhang This is my paper

classification cs.DScs.CLcs.LG MSC 68Q3268Q45

keywords languagegenerationinthelimitnoisyexamplesuniformnon-uniformnoiselevelclosuredimensiongeneratabilitythresholdformallanguages

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper studies a formal model of language generation in the limit, where an algorithm sees a stream of example strings and must eventually output correct unseen strings from an unknown target language, even if the stream contains extraneous 'noise' strings. It proves a threshold effect: allowing just one noisy string strictly reduces the set of collections that can be generated, but once one noisy string is allowed, any larger finite noise budget is equivalent. This holds for both uniform and non-uniform generation, so the graded list of noise levels collapses to a binary distinction—noiseless versus any finite noise. The authors use this to give a complete characterization of uniform and non-uniform noise-dependent generatability in terms of a noisy closure dimension, answering open questions about whether non-uniform generation is robust to a single corruption. The upshot is that the first corrupted example is qualitatively the entire threat.

What carries the argument

The noisy closure dimension NC_i(C) measures the size of the largest finite set of strings S that is consistent with at least one language from C when up to i noise strings are allowed (C(S,i) ≠ ∅) and whose closure ⟨S⟩_{C,i}—the intersection of all such consistent languages—is finite. The proof pivots on Lemma 3.2, which states that NC_{i-1}(C) ≥ √NC_i(C); this square-root relation lets the authors propagate finiteness of NC_1 upward to every higher noise level. Uniform generatability with noise level i is shown to be equivalent to NC_i(C) < ∞, so the square-root bound collapses all positive noise levels. Non-uniform generatability is then characterized by decomposing C into a countable cha

What would settle it

Find a collection C with NC_1(C) finite but NC_i(C) infinite for some i ≥ 2 (in other words, a collection that is uniformly generatable with one noisy string but not with two). The paper's theorems declare this impossible, so exhibiting one would refute the central equivalence.

Watch

Extended reading notes

Core claim

Noise is a sharp threshold: a collection is generatable with any finite noise level i ≥ 1 exactly when it is generatable with one noisy string (Theorem 2.14), and one noisy string already strictly hurts—some collections are uniformly generatable without noise but fail at non-uniform generation with a single corrupt example (Theorem 2.15). Uniform noise-dependent generatability is therefore equivalent to the noisy closure dimension NC_1(C) being finite (Theorem 2.16); non-uniform noise-dependent generatability is equivalent to C being a countable increasing union of subcollections with finite NC_1 (Theorem 2.17). This provides the first characterization of non-uniform noise-dependent generata

Load-bearing premise

The proof that all positive noise levels coincide rests on Lemma 3.2's inequality NC_{i-1}(C) ≥ √NC_i(C), and the written argument leaves the case where a set has no consistent language at the lower noise level unaddressed.

Editorial extensions

If this is right

Any algorithm that succeeds with one noisy string also succeeds, with no modification, under any finite noise budget—the noise levels i ≥ 1 are all the same.
A learner cannot ever be 'slightly robust' to noise: the transition from zero to one corrupted example is the only point at which generatability is lost, so noisy training data is an all-or-nothing affair at this level of abstraction.
Uniform noise-dependent generation has a simple certificate: check whether NC_1(C) is finite; no need to examine every noise level separately.
Non-uniform noise-dependent generation, previously open, is exactly the class of collections that can be written as an increasing countable union of subcollections each with finite NC_1.
Because the first noise string is what matters, the infinite strict hierarchy observed for plain generation in the limit does not survive under uniform or non-uniform requirements—the hierarchy collapses at level 1.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

A testable extension would be whether the same threshold survives when the adversary's noise strings are allowed to repeat the algorithm's earlier outputs or when the universe is finite; the constructions here use an infinite universe and unique noise strings.
The separation example suggests that the only way a single noise string hurts is by forcing the algorithm to commit to a hypothesis about which revealed strings are genuine; one might connect this to a notion of 'verification dimension' distinct from the closure dimension.
For practitioners, the result is a sharp caveat: modeling noisy training data as 'just a little corruption' is qualitatively different from no corruption, but 'a lot of corruption' is no harder than 'a little,' so denoising efforts should focus on eliminating the first spurious example rather than reducing the total count.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The paper is a solid, genuinely new contribution to the language-generation-in-the-limit subfield. The results — Theorem 2.14 (noise level 1 equivalent to any finite level), Theorem 2.15 (one noisy string strictly hurts), and the NC1 characterizations in Theorems 2.16 and 2.17 — are absent from RR25 and BPZ26, and they answer two open questions. I went through the central proofs: Lemma 3.1, Lemma 4.1, and the three-case diagonalization in Theorem 2.15 are correct. The construction in Theorem 2.15 is actually elegant. No data, no fitted parameters; the argument is definition-driven.

The one real soft spot is Lemma 3.2, and the stress-test note is right. The first branch says that if |⟨S_j⟩_{C,i−1}| < ∞ for some block, then NC_{i−1}(C) ≥ k. That inference only holds when C(S_j,i−1) ≠ ∅; if the consistency set is empty, the noisy closure is empty by definition, but the empty set does not witness closure dimension. That subcase can actually happen, so the proof as written has a gap — and Theorem 3.3 uses the contrapositive of Lemma 3.2, so the gap sits on the path to the main equivalence. It is patchable: if C(S_j,i−1)=∅, then any L∈C(S,i) must satisfy |S_j\L|=i and |(S\S_j)\L|=0, so for any x∈S_j, A=(S\S_j)∪{x} has size k²−k+1 ≥ k and lies in C(A,i−1), giving finite closure. So the result survives, but the manuscript needs a repair in that branch.

The citation pattern is fine; the paper leans on RR25's Theorems 3.3/3.5 and Lemmas 3.6/3.8, which is legitimate dependency rather than circularity. Significance is contained within the subfield, but for that community it's a real step: the strict hierarchy in BPZ26 makes the level-1 collapse surprising, and the separation answers an explicit open question.

Bottom line: this deserves a serious referee, not a desk reject. With the Lemma 3.2 fix, I'd accept. I'd bring it to a reading group if you work on generation in the limit; otherwise it's a worthwhile quick read. For my own work, I'd cite it.

Referee Report

1 major / 4 minor

Summary. The paper studies uniform and non-uniform language generation in the limit under the noisy-example model of Raman and Raman. Its main results are: (i) for both uniform and non-uniform generation, any finite noise level i≥1 yields exactly the same generatable collections as noise level 1 (Theorems 2.14, 3.3, 4.2); (ii) a single noisy string strictly reduces the class of generatable collections compared with the noiseless setting, answering an open question of RR25 (Theorem 2.15); and (iii) a characterization of uniform and non-uniform noise-dependent generatability in terms of NC_1 (Theorems 2.16, 2.17). The proofs are combinatorial, based on closure operators, diagonalization, and an adversarial construction over disjoint infinite columns.

Significance. If the results hold, they give a clean threshold picture: one extraneous string already causes the worst-case shrinkage for uniform and non-uniform generation, while additional finite noise is free. This sharply contrasts with the strict noise-level hierarchy for plain generation in the limit proved by BPZ26, and it resolves two open questions from RR25, including the first characterization of non-uniform noise-dependent generatability. The paper is definition-driven and contains no fitted parameters or black-box reductions; the main structural lemmas (3.1, 4.1) and the adversary construction in Theorem 2.15 are original and, in my reading, correct. The dependence on RR25's Theorems 3.3/3.5 and Lemmas 3.6/3.8 is explicit and appropriate.

major comments (1)

[Section 3, Lemma 3.2] The first branch concludes NC_{i-1}(C) ≥ k from |⟨S_j⟩_{C,i-1}|<∞. This is valid only when C(S_j,i-1)≠∅. If C(S_j,i-1)=∅, Definition 2.9 gives closure ∅ (finite), but Definition 2.10 does not count S_j as a witness for NC_{i-1}; the proof never addresses this subcase, and it is compatible with the lemma's assumptions. This is load-bearing: the contrapositive powers Theorem 3.3 and hence Theorems 2.14, 2.16, 2.17. The gap is repairable: when C(S_j,i-1)=∅, every L∈C(S,i) has |S_j\L|≥i and therefore |(S\S_j)\L|=0; for x∈S_j, A=(S\S_j)∪{x} has size ≥k, C(S,i)⊆C(A,i-1), and ⟨A⟩_{C,i-1}⊆⟨S⟩_{C,i} finite, so NC_{i-1}(C)≥k still follows. The text should be revised to handle this case.

minor comments (4)

[Section 3, Lemma 3.1] The forward direction says 'when |S_t|>NC_i(C), |⟨S_t⟩|=∞'. This is literally from the definition only because the target language guarantees C(S_t,i)≠∅ in any valid play; please state this explicitly.
[Section 4, Theorem 2.15] In Algorithm 1, the sentence 'Interpreting C as a set of column indices' is misleading: C is a set of block indices, not column indices. Please clarify the notation.
[Abstract and references] The abstract contains a missing space ('calllanguage'). Also, reference [LRT25] has URL 'raman25a.html', which appears to be the wrong paper page.
[Definition 2.10] Definition 2.10 defines NC_i as the size of the largest set S with C(S,i)≠∅ and finite closure. Since Definition 2.9 assigns closure ∅ when C(S,i)=∅, the nonemptiness condition in Definition 2.10 should be emphasized in the surrounding text to avoid confusion.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the derivation is definition-driven and self-contained; the only self-citation (BPZ26) is contextual, not load-bearing. The Lemma 3.2 gap is a patchable correctness issue, not a circular step.

full rationale

The paper's central equivalence (Theorem 2.14) is not obtained by fitting or by renaming a known result; it is derived from the closure-dimension inequality Lemma 3.2. Lemma 3.1 proves, rather than merely cites, that uniform generation with noise level i is equivalent to NC_i(C)<∞; its proof is self-contained and only remarks that the technique is implicit in RR25's Theorem 3.3. Lemma 3.2 then proves NC_{i-1}(C) ≥ sqrt(NC_i(C)) by a block-partition argument: if one block has finite (i-1)-closure, the dimension bound is immediate; otherwise the proof constructs a k-element set A with ⟨A⟩_{C,i-1} ⊆ ⟨S⟩_{C,i}, transferring finiteness from the i-level closure to the (i-1)-level closure. The collapse of all levels i≥1 to level 1 in Theorem 3.3 uses the contrapositive of this inequality, and Theorem 4.2 exports the same argument to the non-uniform case through Lemma 4.1. Theorem 2.15's separation is proven by an explicit adversarial construction on column languages, not by assuming the result. The non-uniform noise-dependent characterization (Theorems 4.7/2.17) combines the proved equivalence with RR25's independent necessary and sufficient conditions, rather than assuming the target characterization. The only self-citation is BPZ26 (co-author Ian Zhang), used for context and contrast: the strict hierarchy, the no-repeat equivalence, and the noise-independent characterization. None of the paper's proofs load on BPZ26 as evidence. One correctness caveat, not circularity: in Lemma 3.2, the first case 'If |⟨S_j⟩_{C,i-1}|<∞ for some S_j, then NC_{i-1}(C)≥k' silently assumes C(S_j,i-1)≠∅, since Definition 2.10 requires nonempty consistency for a set to witness the closure dimension; the case C(S_j,i-1)=∅ is unhandled. The inequality is patchable, and the gap does not make any conclusion equivalent to its input. Hence no circularity; score 0.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

Pure mathematics with no free parameters or fitted constants. The load-bearing inputs are the KM24 model conventions (infinite languages, countable universe, repetition-free unique enumerations — the latter credited to BPZ26), the convention that generator algorithms are arbitrary functions (Definition 2.1), and three RR25 theorems/lemmas (Theorem 3.3, Theorem 3.5, Lemmas 3.6/3.8) used to connect noise-level-1 generatability to noise-dependent generatability. No invented entities: the noisy closure operator and dimension NC_i are defined in RR25 and reused. The main technical innovation, Lemma 3.2, is proved in the text modulo the empty-consistency edge case noted in red flags.

assumptions (6)

domain assumption Target languages are infinite subsets of a countably infinite universe U; the adversary presents a unique, repetition-free enumeration of the target language; noise strings are unique and outside the target language.
Section 2, Definitions 2.2 and 2.5. This is the KM24 framework; the repetition-free convention is credited to BPZ26. The entire paper operates inside this setup.
domain assumption Generator algorithms are arbitrary functions U* → U; computability is not required.
Definition 2.1. Load-bearing for Lemma 4.1 (the combined algorithm uses the t*(C_j) sequence) and Theorem 2.15's diagonalization, which treats G as a black-box function over all finite prefixes.
domain assumption RR25 Theorem 3.3: uniform noise-dependent generatability iff NC_i(C) < ∞ for all i ≥ 1.
Invoked in Theorem 3.5/2.16 as an external published result, not proved here. If this characterization were wrong, the NC1 characterization would be unsupported.
domain assumption RR25 Theorem 3.5: there exists a collection uniformly generatable without noise but not uniformly noise-dependently generatable.
Used in the final paragraph of Theorem 2.16's proof for the uniform separation part.
domain assumption RR25 Lemmas 3.6/3.8: sufficient and necessary conditions for non-uniform noise-dependent generatability in terms of nested countable sequences with NC_i(C_i) < ∞.
Invoked in Lemmas 4.5 and 4.6 to connect noise-level-1 generatability to noise-dependent generatability.
standard math Standard set-theoretic facts: intersections over possibly uncountable families; selection of an element from an infinite set for witness construction.
Lemmas 2.11, 3.1, and 3.2 use intersections over possibly uncountable collections and repeated selection of elements from infinite closures.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Characterizing the Effect of Noise in Language Generation in the Limit." pith.science (2026). https://pith.science/paper/PQYSFVNM

@misc{pith2026260121237,
  author       = {Pith},
  title        = {Pith review of: Characterizing the Effect of Noise in Language Generation in the Limit},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/PQYSFVNM}},
  note         = {Machine review of arXiv:2601.21237}
}

read the original abstract

Kleinberg and Mullainathan recently proposed a formal framework for studying the phenomenon of language generation, called language generation in the limit. In this model, an adversary gives an enumeration of example strings from an unknown target language, and the algorithm is tasked with correctly generating unseen strings from the target language within finite time. Refined notions of non-uniform and uniform generation were later introduced by Li, Raman, and Tewari (2025), and a noisy model was introduced by Raman and Raman (2025), which allows the adversary to insert extraneous strings. A natural question in the noisy model is to quantify the effect of noise, by studying the impact of each additional extraneous string. We show two complementary results in this setting. We first show that for both uniform and non-uniform generation, a single noisy string strictly reduces the set of collections that can be generated, thus answering an open question in Raman and Raman (2025). Then, we show for both uniform and non-uniform generation that generation with a single noisy string is equivalent to generation with any finite amount of noise, sharply contrasting with the strict hierarchy for noisy generation in the limit shown by Bai, Panigrahi, and Zhang (2026). Finally, we leverage our previous results to provide the first known characterization for non-uniform noise-dependent generatability.

Discussion (0). Sign in to comment.

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

Contrastive Identification and Generation in the Limit
cs.LG 2026-05 unverdicted novelty 8.0 of 10

Contrastive pair presentations yield exact identifiability characterizations via a geometric refinement of Angluin's condition, a new contrastive closure dimension for generation, mutual incomparability with text iden...
Hallucination Rates in Language Generation
cs.DS 2026-07 conditional novelty 6.0 of 10

Allowing infinitely many but rare hallucinations strictly enlarges the class of languages generatable in the limit, and the allowed hallucination rate orders these classes into a strict hierarchy.

Reference graph

Works this paper leans on

28 extracted references · 5 linked inside Pith · cited by 2 Pith papers

[1]

Kornaropoulos

Antonios Anastasopoulos, Giuseppe Ateniese, and Evgenios M. Kornaropoulos. Safe language generation in the limit, January 2026. URL: https://arxiv.org/abs/2601.08648, https://arxiv.org/abs/2601.08648 arXiv:2601.08648

arXiv 2026
[2]

Language generation: Complexity barriers and implications for learning, November 2025

Marcelo Arenas, Pablo Barcel \'o , Luis Cofr \'e , and Alexander Kozachinskiy. Language generation: Complexity barriers and implications for learning, November 2025. URL: https://arxiv.org/abs/2511.05759, https://arxiv.org/abs/2511.05759 arXiv:2511.05759

arXiv 2025
[3]

Dana Angluin and Philip D. Laird. Learning from noisy examples. Mach. Learn. , 2(4):343--370, April 1988. https://doi.org/10.1007/BF00116829 doi:10.1007/BF00116829

doi:10.1007/bf00116829 1988
[4]

Finding patterns common to a set of strings

Dana Angluin. Finding patterns common to a set of strings. J. Comput. Syst. Sci. , 21(1):46--62, August 1980. https://doi.org/10.1016/0022-0000(80)90041-0 doi:10.1016/0022-0000(80)90041-0

doi:10.1016/0022-0000(80)90041-0 1980
[5]

Inductive inference of formal languages from positive data

Dana Angluin. Inductive inference of formal languages from positive data. Inf. Control. , 45(2):117--135, May 1980. https://doi.org/10.1016/S0019-9958(80)90285-5 doi:10.1016/S0019-9958(80)90285-5

doi:10.1016/s0019-9958(80)90285-5 1980
[6]

Language generation in the limit: Noise , loss, and feedback

Yannan Bai, Debmalya Panigrahi, and Ian Zhang. Language generation in the limit: Noise , loss, and feedback. In Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2026 . SIAM , January 2026. https://doi.org/10.1137/1.9781611978971.31 doi:10.1137/1.9781611978971.31

doi:10.1137/1.9781611978971.31 2026
[7]

Exploring facets of language generation in the limit

Moses Charikar and Chirag Pabbaraju. Exploring facets of language generation in the limit. In Nika Haghtalab and Ankur Moitra, editors, The Thirty Eighth Annual Conference on Learning Theory, 30-4 July 2025, Lyon, France , volume 291 of Proceedings of Machine Learning Research , pages 854--887. PMLR , June 2025. URL: https://proceedings.mlr.press/v291/cha...

2025
[8]

Pareto-optimal non-uniform language generation, October 2025

Moses Charikar and Chirag Pabbaraju. Pareto-optimal non-uniform language generation, October 2025. ALT 2026. URL: https://arxiv.org/abs/2510.02795, https://arxiv.org/abs/2510.02795 arXiv:2510.02795

arXiv 2025

Show all 28 references

[9]

Mark Gold

E. Mark Gold. Language identification in the limit. Inf. Control. , 10(5):447--474, May 1967. https://doi.org/10.1016/S0019-9958(67)91165-5 doi:10.1016/S0019-9958(67)91165-5

1967 doi
[10]

On union-closedness of language generation, June 2025

Steve Hanneke, Amin Karbasi, Anay Mehrotra, and Grigoris Velegkas. On union-closedness of language generation, June 2025. NeurIPS 2025. URL: https://arxiv.org/abs/2506.18642, https://arxiv.org/abs/2506.18642 arXiv:2506.18642

2025 arXiv
[11]

Tsang, and Masashi Sugiyama

Bo Han, Quanming Yao, Xingrui Yu, Gang Niu, Miao Xu, Weihua Hu, Ivor W. Tsang, and Masashi Sugiyama. Co-teaching: Robust training of deep neural networks with extremely noisy labels. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicol \` o Cesa - Bianchi,...

2018
[12]

Kearns and Ming Li

Michael J. Kearns and Ming Li. Learning in the presence of malicious errors. SIAM J. Comput. , 22(4):807--837, August 1993. https://doi.org/10.1137/0222052 doi:10.1137/0222052

1993 doi
[13]

Kleinberg and Sendhil Mullainathan

Jon M. Kleinberg and Sendhil Mullainathan. Language generation in the limit. In Amir Globersons, Lester Mackey, Danielle Belgrave, Angela Fan, Ulrich Paquet, Jakub M. Tomczak, and Cheng Zhang, editors, Advances in Neural Information Processing Systems 38: Annual Conference on ...

2024
[14]

On characterizations for language generation: Interplay of hallucinations, breadth, and stability, July 2025

Alkis Kalavasis, Anay Mehrotra, and Grigoris Velegkas. On characterizations for language generation: Interplay of hallucinations, breadth, and stability, July 2025. ALT 2026. URL: https://arxiv.org/abs/2412.18530, https://arxiv.org/abs/2412.18530 arXiv:2412.18530

2025 arXiv
[15]

On the limits of language generation: Trade-offs between hallucination and mode-collapse

Alkis Kalavasis, Anay Mehrotra, and Grigoris Velegkas. On the limits of language generation: Trade-offs between hallucination and mode-collapse. In Michal Kouck \' y and Nikhil Bansal, editors, Proceedings of the 57th Annual ACM Symposium on Theory of Computing, STOC 2025, Pra...

2025
[16]

Vempala, and Edwin Zhang

Adam Tauman Kalai, Ofir Nachum, Santosh S. Vempala, and Edwin Zhang. Why language models hallucinate, September 2025. URL: https://arxiv.org/abs/2509.04664, https://arxiv.org/abs/2509.04664 arXiv:2509.04664

2025 arXiv
[17]

Adam Tauman Kalai and Santosh S. Vempala. Calibrated language models must hallucinate. In Bojan Mohar, Igor Shinkar, and Ryan O'Donnell, editors, Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24-28, 2024 , pages 160...

2024
[18]

Density measures for language generation, April 2025

Jon Kleinberg and Fan Wei. Density measures for language generation, April 2025. FOCS 2025. URL: https://arxiv.org/abs/2504.14370, https://arxiv.org/abs/2504.14370 arXiv:2504.14370

2025 arXiv
[19]

Language generation and identification from partial enumeration: Tight density bounds and topological characterizations, November 2025

Jon Kleinberg and Fan Wei. Language generation and identification from partial enumeration: Tight density bounds and topological characterizations, November 2025. URL: https://arxiv.org/abs/2511.05295, https://arxiv.org/abs/2511.05295 arXiv:2511.05295

2025
[20]

Hopkins, David Bau, Fernanda B

Kenneth Li, Aspen K. Hopkins, David Bau, Fernanda B. Vi \' e gas, Hanspeter Pfister, and Martin Wattenberg. Emergent world representations: Exploring a sequence model trained on a synthetic task. In The Eleventh International Conference on Learning Representations, ICLR 2023, ...

2023
[21]

Generation through the lens of learning theory

Jiaxun Li, Vinod Raman, and Ambuj Tewari. Generation through the lens of learning theory. In Nika Haghtalab and Ankur Moitra, editors, The Thirty Eighth Annual Conference on Learning Theory, 30-4 July 2025, Lyon, France , volume 291 of Proceedings of Machine Learning Research ...

2025
[22]

Junnan Li, Richard Socher, and Steven C. H. Hoi. DivideMix : Learning with noisy labels as semi-supervised learning. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020 . OpenReview.net, April 2020. URL: https://open...

2020
[23]

Language generation with infinite contamination, November 2025

Anay Mehrotra, Grigoris Velegkas, Xifan Yu, and Felix Zhou. Language generation with infinite contamination, November 2025. URL: https://arxiv.org/abs/2511.07417, https://arxiv.org/abs/2511.07417 arXiv:2511.07417

2025
[24]

Dhillon, Pradeep Ravikumar, and Ambuj Tewari

Nagarajan Natarajan, Inderjit S. Dhillon, Pradeep Ravikumar, and Ambuj Tewari. Learning with noisy labels. In Christopher J. C. Burges, L \' e on Bottou, Zoubin Ghahramani, and Kilian Q. Weinberger, editors, Advances in Neural Information Processing Systems 26: 27th Annual Con...

2013
[25]

Representative language generation

Charlotte Peale, Vinod Raman, and Omer Reingold. Representative language generation. In Forty-second International Conference on Machine Learning, ICML 2025, Vancouver, BC, Canada, July 13-19, 2025 . OpenReview.net, July 2025. URL: https://openreview.net/forum?id=BiXwdXZxs7

2025
[26]

Generation from noisy examples

Ananth Raman and Vinod Raman. Generation from noisy examples. In Forty-second International Conference on Machine Learning, ICML 2025, Vancouver, BC, Canada, July 13-19, 2025 . OpenReview.net, July 2025. URL: https://openreview.net/forum?id=ouaiJlE1hJ

2025
[27]

Learning to reweight examples for robust deep learning

Mengye Ren, Wenyuan Zeng, Bin Yang, and Raquel Urtasun. Learning to reweight examples for robust deep learning. In Jennifer G. Dy and Andreas Krause, editors, Proceedings of the 35th International Conference on Machine Learning, ICML 2018, Stockholmsm \" a ssan, Stockholm, Swe...

2018
[28]

Chen, Ashesh Rambachan, Jon M

Keyon Vafa, Justin Y. Chen, Ashesh Rambachan, Jon M. Kleinberg, and Sendhil Mullainathan. Evaluating the world model implicit in a generative model. In Amir Globersons, Lester Mackey, Danielle Belgrave, Angela Fan, Ulrich Paquet, Jakub M. Tomczak, and Cheng Zhang, editors, Adv...

2024

Pith tools

Reviewed August 3, 2026 · model on record in the stance chip above.

[1] [1]

Kornaropoulos

Antonios Anastasopoulos, Giuseppe Ateniese, and Evgenios M. Kornaropoulos. Safe language generation in the limit, January 2026. URL: https://arxiv.org/abs/2601.08648, https://arxiv.org/abs/2601.08648 arXiv:2601.08648

arXiv 2026

[2] [2]

Language generation: Complexity barriers and implications for learning, November 2025

Marcelo Arenas, Pablo Barcel \'o , Luis Cofr \'e , and Alexander Kozachinskiy. Language generation: Complexity barriers and implications for learning, November 2025. URL: https://arxiv.org/abs/2511.05759, https://arxiv.org/abs/2511.05759 arXiv:2511.05759

arXiv 2025

[3] [3]

Dana Angluin and Philip D. Laird. Learning from noisy examples. Mach. Learn. , 2(4):343--370, April 1988. https://doi.org/10.1007/BF00116829 doi:10.1007/BF00116829

doi:10.1007/bf00116829 1988

[4] [4]

Finding patterns common to a set of strings

Dana Angluin. Finding patterns common to a set of strings. J. Comput. Syst. Sci. , 21(1):46--62, August 1980. https://doi.org/10.1016/0022-0000(80)90041-0 doi:10.1016/0022-0000(80)90041-0

doi:10.1016/0022-0000(80)90041-0 1980

[5] [5]

Inductive inference of formal languages from positive data

Dana Angluin. Inductive inference of formal languages from positive data. Inf. Control. , 45(2):117--135, May 1980. https://doi.org/10.1016/S0019-9958(80)90285-5 doi:10.1016/S0019-9958(80)90285-5

doi:10.1016/s0019-9958(80)90285-5 1980

[6] [6]

Language generation in the limit: Noise , loss, and feedback

Yannan Bai, Debmalya Panigrahi, and Ian Zhang. Language generation in the limit: Noise , loss, and feedback. In Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2026 . SIAM , January 2026. https://doi.org/10.1137/1.9781611978971.31 doi:10.1137/1.9781611978971.31

doi:10.1137/1.9781611978971.31 2026

[7] [7]

Exploring facets of language generation in the limit

Moses Charikar and Chirag Pabbaraju. Exploring facets of language generation in the limit. In Nika Haghtalab and Ankur Moitra, editors, The Thirty Eighth Annual Conference on Learning Theory, 30-4 July 2025, Lyon, France , volume 291 of Proceedings of Machine Learning Research , pages 854--887. PMLR , June 2025. URL: https://proceedings.mlr.press/v291/cha...

2025

[8] [8]

Pareto-optimal non-uniform language generation, October 2025

Moses Charikar and Chirag Pabbaraju. Pareto-optimal non-uniform language generation, October 2025. ALT 2026. URL: https://arxiv.org/abs/2510.02795, https://arxiv.org/abs/2510.02795 arXiv:2510.02795

arXiv 2025