Pith. sign in

REVIEW 3 major objections 3 minor 40 references

Hallucination Rates in Language Generation

T0 review · 3 major / 3 minor · reviewed 2026-07-31 · deepseek-v4-flash

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

Pith's one-line read Allowing a generator to hallucinate infinitely often, even at zero rate, strictly enlarges the generatable languages, and every permissible hallucination rate defines a strictly more powerful class — a hierarchy that extends to breadth and

desk verdict Solid rate-hierarchy results with a real gap in the breadth-interpolation theorem; worth refereeing but Theorem 1.7 needs repair. read the letter →

arxiv 2607.23361 v1 pith:WQBWR5W4 submitted 2026-07-25 cs.DS cs.CLcs.LG

Debmalya Panigrahi , Fan Wei , Ian Zhang This is my paper
classification cs.DScs.CLcs.LG MSC 68Q3268Q45
keywords languagegenerationinthelimithallucinationratebreadthasymptoticdensitylearnabilityfrompositiveexampleshierarchyseparationno-repetitionformallanguages
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

This paper studies a formal model in which an algorithm must keep generating novel strings from an unknown target language while an adversarial presenter feeds it example strings one at a time. The original model demands that after some point every output be a correct unseen string; this paper relaxes that to allow infinitely many wrong outputs as long as their asymptotic frequency is at most a rate β, possibly zero. Its central claim is that even β=0 (infinitely many errors on a zero-measure set of time steps) makes generation strictly more powerful than finitely many errors, and that every larger β admits strictly more collections than any smaller β. The same strict hierarchy is shown for breadth — the fraction of the target language eventually covered — and for algorithms that are forbidden to repeat outputs. If correct, the rate of hallucination is not a mere failure tolerance but a parameter that organizes the whole space of generatable language collections.

What carries the argument

The central construction is a family of infinite rooted trees whose nodes carry disjoint pools of strings. A target language is the union of pools along an infinite ray from the root; once the algorithm sees a string from a node, the entire 'safe' sub-pool B_v of that node is guaranteed to be in the target, giving it a run of correct outputs. By sizing node pools so that the safe part leaves p_i errors over q_i time steps at depth i, with p_i/q_i converging to β, the authors force the optimal error rate to be exactly β. Breadth is engineered by a fixed labeling of the universe into high- and zero-density sets, plus an interpolation lemma that mixes a zero-breadth gadget with a half-breadth g

What would settle it

Trace the interleaving construction behind the every-breadth claim on a small concrete case: pick α=1/2, take one language from each gadget, and compute the fraction of strings contributed by the second language in the first several interleaving blocks. If those fractions do not converge to 1, or if another language pair gives a materially different limit, the density-interpolation lemma fails for that instance and the claimed two-parameter hierarchy is not established. A simpler check for Theorem 1.1: run the finite-error adversary strategy against the binary-tree collection and test whether

Watch

Extended reading notes

Core claim

The paper's central discovery is that infinite hallucinations at a fixed asymptotic rate generate a strict hierarchy of power. Theorem 1.1 exhibits an uncountable collection of languages that is generatable with zero-rate hallucination but not with finite error; Theorem 1.2 shows that for every β∈(0,1] there is a collection generatable at rate β but at no smaller rate. Theorem 1.5 refines this to a two-parameter hierarchy: for every breadth α∈[0,1/2] and rate β∈(0,1] there is a collection that is β-generatable with lower density α yet cannot be generated with any smaller rate (even at zero breadth) nor with any larger breadth (even with hallucination rate 1). Theorems 1.6 and 1.7 transfer bo

Load-bearing premise

The 'every breadth' separation relies on arranging the two universes into blocks so that every possible target language contains the same limiting fraction of each block; the proof assumes this uniformity holds for all language pairs rather than proving it.

Editorial extensions

If this is right

  • Zero-measure hallucination is a genuine power increase: an algorithm may use infinitely many rare errors to generate targets that no finite-error algorithm can handle.
  • The hallucination rate acts as a complexity parameter: collections sorted by the smallest β at which they are generatable form a strict linear hierarchy, and no smaller-rate algorithm can absorb the workload of a larger-rate one.
  • Breadth does not collapse this hierarchy: for every target coverage fraction up to 1/2 and every rate, there is a collection that is exactly at that tradeoff point, with both parameters independently tight.
  • Banning repeated outputs does not smooth the picture away: the same strict rate and breadth hierarchies hold when the algorithm must emit distinct strings, so the results reflect content rather than time-step bookkeeping.
  • Some collections are unlearnable in a strong sense: there exists a collection for which, against any algorithm, an adversary can force zero correct strings, so no error rate below 1 suffices.

Reading between the lines

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

  • If the hierarchy is as rigid as claimed, a natural next step is a full two-parameter lattice for generation with repetition, no-repetition, uniform versus limsup error bounds, and noise in the example stream; the tree-and-box gadgets here are concrete templates for testing each cell.
  • The results suggest that a practical 'hallucination budget' in deployed systems is not a soft defect tolerance but a hard capability knob: tuning an allowed error rate upward should provably enlarge the set of achievable target behaviors, which could be tested in controlled curriculum-learning experiments.
  • A testable mathematical extension would ask whether the hierarchy survives under closure operations such as finite unions of collections, and whether generatability at rate β is monotone under natural transformations of the universes; the paper's constructions give extremal examples for such questions.
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.

Referee Report

3 major / 3 minor

Summary. The paper introduces a relaxation of Kleinberg–Mullainathan language generation in which the algorithm may hallucinate infinitely often, provided the limiting frequency of incorrect time-steps is at most β. It defines β-generation with and without repetition, and combines this with upper/lower breadth (density) of the generated set. The main claims are: (1) rate-0 hallucination is strictly more powerful than finite-error generation (Theorem 1.1); (2) a strict hierarchy of generatable collections indexed by β (Theorems 1.2 and 1.6); (3) an ungeneratable collection at every β<1 (Theorem 1.3); and (4) joint rate–breadth hierarchies in both the repetition and no-repetition settings (Theorems 1.5 and 1.7). The proofs are constructive, with explicit adversary strategies and no fitted parameters or circular dependencies.

Significance. If all the stated results are correct, the paper establishes a clean quantitative refinement of the KM model: infinite but measure-zero hallucination is a genuine power increase, and the allowed error rate is a nontrivial complexity parameter. The rate-only constructions (Theorems 1.1, 1.2, 1.3, 1.6) appear sound and are presented with enough detail to be checkable. The joint breadth–rate claims are the most interesting part, but two steps in Section 4.2 are not established as written, and one step in Lemma 3.10 needs correction. For these reasons the full hierarchy, especially Theorem 1.7, is not yet proven in the manuscript.

major comments (3)
  1. [§4.2, Lemma 4.5] The lower-bound proof states: 'since the algorithm is not allowed to repeat strings, the algorithm can only generate half of the nodes from the set B_{v_i}.' This is not justified and appears false. Once the adversary outputs the first string of B_{v_i}, the algorithm knows v_i and can output a fresh unrevealed string of B_{v_i} on each subsequent time-step. Over the q_i-p_i+1 steps in which B_{v_i} is enumerated, the algorithm can therefore obtain |B_{v_i}|-1 = q_i-p_i correct strings, not (q_i-p_i)/2. Then the wrong outputs in a stage of length q_i are at most p_i, giving error rate p_i/q_i → 2β-1, which for β>1/2 is strictly smaller than β. Thus the claimed lower bound β does not follow from the stated adversary strategy; in fact the construction as written appears to admit β′-generation for β′ around 2β-1. This is load-bearing for Theorem 1.7 in the β∈(1/2,1] regime.
  2. [§4.2, proof of Theorem 1.7] The interpolation argument asserts that after placing ⌊r_i 2q_j/(2q_j-p_j)⌋ strings from a box S_j into group M_i, 'in the limit, since a language L_1 contains 2q_j-p_j out of the 2q_j total strings from a box S_j, and because the sequences {q_i} and {r_i} do not grow too quickly, we have |L_1∩M_i|→r_i.' This uniformity over all L_1∈C_1 is exactly what Lemma 4.6 requires, but it is not proved. A language may omit any p_j of the 2q_j strings of S_j; if N_i strings from S_j are placed in M_i, |L_1∩M_i| can range from N_i-p_j to N_i, so the relative uncertainty is p_j/N_i. No explicit condition relating r_i to p_j (or to the boxes used at group i) is stated, and the convergence is not shown to hold uniformly over L_1. Without this uniform density statement, the conclusion that L_2 has density exactly 2α in L_1∪L_2 for every L_1,L_2 is unsupported.
  3. [§3.3, Lemma 3.10] The proof says that because the algorithm 'does not output any correct strings from A_{v_i}', it follows that f(O) does not contain any strings from Y. This implication is not valid: O is the set of all algorithm outputs, and the adversary prevents only A-strings in O∩K, not all A-strings in O. Incorrect A-outputs still have f-images in Y. The intended upper-density bound can likely be repaired by noting that Y has density 0 in N and by bounding f(O∩K) directly, but the proof as written overstates what has been shown.
minor comments (3)
  1. [§4.2, Lemma 4.3] The definition of the set of timestamps F={F_1,F_2,...}, where F_i is 'the first time the algorithm has touched 2^i boxes,' is unclear. Please define this formally and specify how the cleanup steps at t∈F interact with the mirroring rule.
  2. [§3.1, Lemma 3.4] Equation (2) uses a ratio of sums over all v∈T_β. It may help the reader to state explicitly that ∑_v |H_t(v)| = t, since the adversary outputs exactly one string per time-step and no string lies in two D_v sets.
  3. [§3.3, Lemma 3.10] In the sentence 'the algorithm ... does not output any correct strings from A_{v_i}', the word 'correct' is misleading; the intended statement is about strings that lie in K, while incorrect A-outputs are irrelevant for density only because their images lie in the density-0 set Y.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the paper's constructions and adversarial lower bounds are self-contained derivations from the KM model; cited results are background, not load-bearing.

full rationale

I walked the main derivation chain (Theorems 1.1, 1.2, 1.5, 1.6, 1.7) and found no step where a claimed output is equivalent by construction to an input, where a fitted parameter is renamed as a prediction, or where a load-bearing claim rests on a self-citation. The collections are built explicitly from tree rays, boxes S_i, bins, and density-labeled orderings; the positive directions give algorithms and bound |W_t|/t via the same p_i/q_i sequences used in the construction, while the negative directions give adversary strategies forcing error rate at least limsup (Σ p_j)/(Σ q_j) = β. Since β is the universally quantified target rate in the theorems, choosing p_i/q_i → β is not circular: it is the standard way to prove the existence of a collection at exactly rate β. The breadth arguments similarly define f-maps into sets H/R/Y with prescribed densities and then compute the resulting output density; no density α is assumed inside the construction and then retrieved as a conclusion. Citations to [KM24], [KW25], [KW26b], and [HKMV25] supply prior background or a proof template, but none of these citations is used as the unique justification of a new theorem, and none is a self-citation that forbids alternatives. The skeptical concern about Lemma 4.6 — that the interpolation proof assumes, rather than establishes, uniform convergence of |L1∩M_i| to r_i and |L2∩M_i| to s_i — is a mathematical-rigor issue about the proof's completeness, not circularity: a gap in a construction does not mean the theorem was assumed as an input. No fitted data, no empirical prediction, and no self-referential uniqueness claim appear in the paper. Hence the honest finding is no significant circularity, score 0.

Assumptions & free parameters 2 free parameters · 5 assumptions · 0 invented entities

No new physical entities or empirical free parameters are introduced. The hand-chosen p_i, q_i, r_i, s_i sequences are universal constructions for arbitrary β and α, not fitted values. The one load-bearing unproved premise is the uniform convergence assumption in Theorem 1.7, which is a genuine gap in the proof.

free parameters (2)
  • p_i, q_i sequences = p_i/q_i -> β
    Hand-chosen construction sequences in Theorems 1.2, 1.5, 1.6, and the Section 4 gadgets. They are mathematical construction parameters, not empirical fits, but they are the mechanism by which the target rate β is engineered.
  • r_i, s_i sequences = s_i/(r_i+s_i) -> 2α
    Interpolation sequences in Theorem 1.7 used to arrange the density of L2 inside L1∪L2. Again construction parameters, not empirical constants.
assumptions (5)
  • standard math limsup/liminf and asymptotic density arithmetic follow standard real-analysis facts.
    Used throughout, e.g., Lemma 2.5 and the density arguments in Theorems 1.4 and 1.5.
  • domain assumption The adversary may adaptively choose the target language K and its enumeration after seeing the algorithm's behavior.
    This is the standard KM adversarial model, invoked in every lower-bound construction (Lemmas 3.3, 3.7, 4.2).
  • domain assumption Every language is an infinite subset of a countably infinite universe, and the adversary enumerates each of its strings exactly once.
    Explicit in Section 2; needed for the density and time-step accounting throughout.
  • standard math There exist partitions H, R, Y of N with prescribed upper/lower densities, and orderings of U compatible with them.
    Used in the breadth constructions of Theorems 1.5, 4.3, and 4.5; such partitions are constructible by standard density arguments.
  • ad hoc to paper For Theorem 1.7, the interleaving construction yields |L1∩M_i| -> r_i and |L2∩M_i| -> s_i uniformly over all L1∈C1, L2∈C2.
    This is asserted in the proof of Theorem 1.7 but not derived. If it fails, the density interpolation between the two gadgets does not hold for every language pair.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Hallucination Rates in Language Generation." pith.science (2026). https://pith.science/paper/WQBWR5W4

@misc{pith2026260723361,
  author       = {Pith},
  title        = {Pith review of: Hallucination Rates in Language Generation},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/WQBWR5W4}},
  note         = {Machine review of arXiv:2607.23361}
}
read the original abstract

Language generation in the limit is an elegant model introduced by Kleinberg and Mullainathan [KM24] to formally study language generation by an algorithm that learns solely based on example strings. In this model, an algorithm is said to correctly generate from a language if it never makes an error after some finite time. In contrast, even sophisticated language models are known to regularly hallucinate in practice. In this paper, we initiate the study of language generation in the limit with (infinite) hallucination, i.e., the algorithm may generate incorrect strings infinitely often, but the errors occur at a limited rate (possibly even with 0-measure). We first show that hallucination, even at rate 0, makes generation in the limit strictly more powerful: there are language collections that cannot be generated with finite error but can be generated with infinite error, even when errors occur on a 0-measure set of time-steps. Furthermore, while all countable collections are generatable with finite error, we show a strict hierarchy of (uncountable) language collections characterized by the hallucination rate. This hierarchy extends to breadth, the fraction of the target language generated. While all countable collections can attain the optimal breadth of 1/2 [KW26b], we show strict separation at every breadth and hallucination rate. Finally, we study generation in the limit without repetition, where the algorithm may not repeat strings. This lets us compare the sets of correct and incorrect strings generated, rather than the fractions of correct and incorrect time-steps. Once again, we demonstrate a strict hierarchy at every hallucination rate and breadth. Taken together, these results reveal rich structure in language collections generatable in the limit with hallucination and establish hallucination rate as an important parameter in the theoretical study of language generation.

Figures

Figures reproduced from arXiv: 2607.23361 by the authors.

Figure 1
Figure 1. The first three layers of the rooted binary tree used in the proof of [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗
Figure 2
Figure 2. A partial view of the rooted tree from the proof of [PITH_FULL_IMAGE:figures/full_fig_p012_2.png] view at source ↗

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

40 extracted references · 1 canonical work pages

  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, January 2026

    Marcelo Arenas, Pablo Barcel \'o , Luis Cofr \'e , and Alexander Kozachinskiy. Language generation: Complexity barriers and implications for learning, January 2026. To appear in ICML 2026. URL: https://arxiv.org/abs/2511.05759, https://arxiv.org/abs/2511.05759 arXiv:2511.05759

    arXiv 2026

  3. [3]

    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

  4. [4]

    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

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

  5. [5]

    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 Kasper Green Larsen and Barna Saha, editors, Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2026, Vancouver, BC, Canada, January 11-14, 2026 , pages 794--816. SIAM , January 2026. https://doi.org/10.1137/1.9781611...

    doi:10.1137/1.9781611978971.31 2026

  6. [6]

    Globally consistent coloring schemes for language identification, July 2026

    Moses Charikar, Jon Kleinberg, and Chirag Pabbaraju. Globally consistent coloring schemes for language identification, July 2026. URL: https://arxiv.org/abs/2607.11606, https://arxiv.org/abs/2607.11606 arXiv:2607.11606

    arXiv 2026

  7. [7]

    Kleinberg, and Chirag Pabbaraju

    Moses Charikar, Jon M. Kleinberg, and Chirag Pabbaraju. Language identification with succinct machine-independent traces. In Steve Hanneke and Tor Lattimore, editors, The Thirty Ninth Annual Conference on Learning Theory, June 29 - July 3, 2026, San Diego, California, USA , volume 336 of Proceedings of Machine Learning Research , pages 1054--1074. PMLR , ...

    2026

  8. [8]

    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

Show all 40 references
  1. [9]

    Pareto-optimal non-uniform language generation, October 2025

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

    2025

  2. [10]

    A characterization of list language identification in the limit

    Moses Charikar, Chirag Pabbaraju, and Ambuj Tewari. A characterization of list language identification in the limit. In Steve Hanneke and Tor Lattimore, editors, The Thirty Ninth Annual Conference on Learning Theory, June 29 - July 3, 2026, San Diego, California, USA , volume ...

    2026

  3. [11]

    Detecting hallucinations in large language models using semantic entropy

    Sebastian Farquhar, Jannik Kossen, Lorenz Kuhn, and Yarin Gal. Detecting hallucinations in large language models using semantic entropy. Nat. , 630(8017):625--630, June 2024. URL: https://doi.org/10.1038/s41586-024-07421-0, https://doi.org/10.1038/S41586-024-07421-0 doi:10.103...

    2024 doi

  4. [12]

    Space-efficient language generation in the limit

    Nicolas Flammarion, Chirag Pabbaraju, Hristo Papazov, Miltiadis Stouras, and Ola Svensson. Space-efficient language generation in the limit. In Steve Hanneke and Tor Lattimore, editors, The Thirty Ninth Annual Conference on Learning Theory, June 29 - July 3, 2026, San Diego, C...

    2026

  5. [13]

    A theory of time-sensitive language generation: Sparse hallucination beats mode collapse, May 2026

    Atul Ganju, Travis McVoy, Shaddin Dughmi, and Shang-Hua Teng. A theory of time-sensitive language generation: Sparse hallucination beats mode collapse, May 2026. URL: https://arxiv.org/abs/2605.11302, https://arxiv.org/abs/2605.11302 arXiv:2605.11302

    2026 arXiv

  6. [14]

    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

  7. [15]

    On union-closedness of language generation

    Steve Hanneke, Amin Karbasi, Anay Mehrotra, and Grigoris Velegkas. On union-closedness of language generation. In Danielle Belgrave, Cheng Zhang, Laura N. Montoya, Hsuan - Tien Lin, Razvan Pascanu, Piotr Koniusz, Marzyeh Ghassemi, Nancy Chen, Iv \' a n Vladimir Meza Ru \' z, a...

    2025

  8. [16]

    Agnostic language identification and generation, January 2026

    Mikael M ller H gsgaard and Chirag Pabbaraju. Agnostic language identification and generation, January 2026. URL: https://arxiv.org/abs/2601.23258, https://arxiv.org/abs/2601.23258 arXiv:2601.23258

    2026 arXiv

  9. [17]

    A survey on hallucination in large language models: Principles , taxonomy, challenges, and open questions

    Lei Huang, Weijiang Yu, Weitao Ma, Weihong Zhong, Zhangyin Feng, Haotian Wang, Qianglong Chen, Weihua Peng, Xiaocheng Feng, Bing Qin, and Ting Liu. A survey on hallucination in large language models: Principles , taxonomy, challenges, and open questions. ACM Trans. Inf. Syst. ...

    2025 doi

  10. [18]

    Polynomial-time mistake-bounded language generation, June 2026

    H \'e ctor Jimenez, Alexander Kozachinskiy, and Vicente Opazo. Polynomial-time mistake-bounded language generation, June 2026. URL: https://arxiv.org/abs/2606.16077, https://arxiv.org/abs/2606.16077 arXiv:2606.16077

    2026

  11. [19]

    Kleinberg and Sendhil Mullainathan

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

    2024

  12. [20]

    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. To appear in ALT 2026. URL: https://arxiv.org/abs/2412.18530, https://arxiv.org/abs/2412.18530 arXiv:2412.18530

    2025 arXiv

  13. [21]

    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

  14. [22]

    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

  15. [23]

    Mistake-bounded language generation, May 2026

    Jon Kleinberg, Charlotte Peale, and Omer Reingold. Mistake-bounded language generation, May 2026. URL: https://arxiv.org/abs/2605.10809, https://arxiv.org/abs/2605.10809 arXiv:2605.10809

    2026 arXiv

  16. [24]

    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

  17. [25]

    Kleinberg and Fan Wei

    Jon M. Kleinberg and Fan Wei. Density measures for language generation. In 66th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2025, Sydney, Australia, December 14-17, 2025 , pages 620--658. IEEE , December 2025. https://doi.org/10.1109/FOCS63196.2025.00034 doi...

    2025

  18. [26]

    Banach density of generated languages: Dichotomies in topology and dimension, April 2026

    Jon Kleinberg and Fan Wei. Banach density of generated languages: Dichotomies in topology and dimension, April 2026. URL: https://arxiv.org/abs/2604.02385, https://arxiv.org/abs/2604.02385 arXiv:2604.02385

    2026 arXiv

  19. [27]

    Kleinberg and Fan Wei

    Jon M. Kleinberg and Fan Wei. Language generation and identification from partial enumeration: Tight density bounds and topological characterizations. In Aditya Bhaskara and Artur Czumaj, editors, Proceedings of the 58th Annual ACM Symposium on Theory of Computing, STOC 2026, ...

    2026

  20. [28]

    Contrastive identification and generation in the limit, May 2026

    Xiaoyu Li, Andi Han, Jiaojiao Jiang, and Junbin Gao. Contrastive identification and generation in the limit, May 2026. URL: https://arxiv.org/abs/2605.06211, https://arxiv.org/abs/2605.06211 arXiv:2605.06211

    2026 arXiv

  21. [29]

    On the price of privacy for language identification and generation, April 2026

    Xiaoyu Li, Andi Han, Jiaojiao Jiang, and Junbin Gao. On the price of privacy for language identification and generation, April 2026. URL: https://arxiv.org/abs/2604.07238, https://arxiv.org/abs/2604.07238 arXiv:2604.07238

    2026 arXiv

  22. [30]

    Flood and harvest: The provable necessity of trivia for generating valuable mathematics via the lens of language generation in the limit, June 2026

    Xiaoyu Li, Andi Han, Dai Shi, Zheng Gao, Jiaojiao Jiang, and Junbin Gao. Flood and harvest: The provable necessity of trivia for generating valuable mathematics via the lens of language generation in the limit, June 2026. URL: https://arxiv.org/abs/2606.14688, https://arxiv.or...

    2026

  23. [31]

    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

  24. [32]

    On generation in metric spaces, February 2026

    Jiaxun Li, Vinod Raman, and Ambuj Tewari. On generation in metric spaces, February 2026. URL: https://arxiv.org/abs/2602.07710, https://arxiv.org/abs/2602.07710 arXiv:2602.07710

    2026

  25. [33]

    Characterizing the effect of noise in language generation in the limit, June 2026

    Aaron Li and Ian Zhang. Characterizing the effect of noise in language generation in the limit, June 2026. To appear in ICML 2026. URL: https://arxiv.org/abs/2601.21237, https://arxiv.org/abs/2601.21237 arXiv:2601.21237

    2026 arXiv

  26. [34]

    Differentially private language generation and identification in the limit

    Anay Mehrotra, Grigoris Velegkas, Xifan Yu, and Felix Zhou. Differentially private language generation and identification in the limit. In Steve Hanneke and Tor Lattimore, editors, The Thirty Ninth Annual Conference on Learning Theory, June 29 - July 3, 2026, San Diego, Califo...

    2026

  27. [35]

    Language generation with infinite contamination

    Anay Mehrotra, Grigoris Velegkas, Xifan Yu, and Felix Zhou. Language generation with infinite contamination. In Steve Hanneke and Tor Lattimore, editors, The Thirty Ninth Annual Conference on Learning Theory, June 29 - July 3, 2026, San Diego, California, USA , volume 336 of P...

    2026

  28. [36]

    Learning algorithms in the limit

    Hristo Papazov and Nicolas Flammarion. Learning algorithms 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 4486--451...

    2025

  29. [37]

    Representative language generation

    Charlotte Peale, Vinod Raman, and Omer Reingold. Representative language generation. In Aarti Singh, Maryam Fazel, Daniel Hsu, Simon Lacoste - Julien, Felix Berkenkamp, Tegan Maharaj, Kiri Wagstaff, and Jerry Zhu, editors, Forty-second International Conference on Machine Learn...

    2025

  30. [38]

    Language identification in the limit with computational trace

    Binghui Peng, Amin Saberi, and Grigoris Velegkas. Language identification in the limit with computational trace. In The Fourteenth International Conference on Learning Representations , April 2026. URL: https://openreview.net/forum?id=1OAGf7ntSE

    2026

  31. [39]

    Generation from noisy examples

    Ananth Raman and Vinod Raman. Generation from noisy examples. In Aarti Singh, Maryam Fazel, Daniel Hsu, Simon Lacoste - Julien, Felix Berkenkamp, Tegan Maharaj, Kiri Wagstaff, and Jerry Zhu, editors, Forty-second International Conference on Machine Learning, ICML 2025, Vancouv...

    2025

  32. [40]

    Language generation with replay: A learning-theoretic view of model collapse, March 2026

    Giorgio Racca, Michal Valko, and Amartya Sanyal. Language generation with replay: A learning-theoretic view of model collapse, March 2026. To appear in ICML 2026. URL: https://arxiv.org/abs/2603.11784, https://arxiv.org/abs/2603.11784 arXiv:2603.11784

    2026 arXiv

Pith tools

Reviewed July 31, 2026 · model on record in the stance chip above.