A Theory of Time-Sensitive Language Generation: Sparse Hallucination Beats Mode Collapse
2026
Read A Theory of Time-Sensitive Language Generation: Sparse Hallucination Beats Mode Collapse (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-11302.txt.
Introduction
Ganju and three colleagues study language generation under a global preference ordering on strings, adding timeliness to the usual demand for breadth. A string counts only if produced before a deadline set by its rank, so higher-ranked strings must come earlier. They prove no generator can be timely in the strong sense for eventually consistent cases. Under the mildest relaxation, a hallucination rate that vanishes over time, they achieve optimal density for any superlinear deadline, and show linear deadlines remain impossible.
Catalog record
| YEAR | 2026 |
|---|---|
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 100459 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.11302
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A Theory of Time-Sensitive Language Generation: Sparse Hallucination Beats Mode Collapse Abstract 1 Introduction Generative language models are a key building block of modern AI systems, enabling a multitude of downstream applications such as general-purpose dialog, creative writing, mathematical reasoning, and code synthesis [ 7 , 19 , 23 ] . Alongside this undeniable practical impact, a growing body of theoretical work seeks to understand the principles and trade-offs governing language generation. An increasingly influential approach, often referred to as language generation in the limit , was spurred by the seminal work of Kleinberg and Mullainathan [ 16 ] , building on classical work concerned with language identification by Gold [ 10 ] and Angluin [ 1 ] . This approach is characterized by its minimal assumptions, abstracting away many of the details of practical implementations and environments. At a high level, language generation is modeled as a game played over time between the generator and an adversary: At the outset the adversary chooses a target language from some countable collection of permissible languages, then the adversary and generator take turns generating strings. The adversary always generates a string from the target language, and the generator’s goal is to eventually do the same. By focusing on the “bare-bones” essentials of language generation and pursuing guarantees only in the limit over time, this approach enables theoretical analysis of what is possible in principle , including identifying and quantifying the intrinsic tension between various design desiderata. Much of the recent literature has focused on the tension between two desiderata: avoiding hallucination by the generator, often formalized through notions such as consistency , and achieving breadth in the generator’s outputs over the target language. We introduce a third concern in this paper which we call timeliness , and study its interplay with hallucination and breadth. Timeliness postulates that “more plausible” or “simpler” outputs should be generated preferentially, which we take to mean earlier in the language generation game. Plausibility can represent any of the myriad forms of inductive bias employed in machine learning: preference for short programs in coding tasks, simpler or human-checkable proofs in mathematical reasoning tasks (judged, perhaps, by a trained reward model), or distributional plausibility in dialog or creative writing tasks [ 9 , 22 , 26 ] . We measure timeliness with respect to a deadline function, mapping a string’s position in the plausibility order to a time in the game by which it must be generated, lest the generator forego the associated credit. In addition to being compelling in its own right, timeliness shares technical and conceptual connections with recent notions of breadth introduced by Kleinberg and Wei [ 17 ] . As background, there are several natural ways of modeling breadth, most of which lead to strong negative results—See [ 13 , 14 ] for examples. This paints the theory into a corner by suggesting the inevitability of mode collapse —the eventual deterioration of the generator to a tiny sliver of the target language. While mode collapse is a very real concern in practice [ 2 , 3 ] , such a stark prediction is perhaps increasingly out of step with empirical reality [ 27 ] . A key conceptual insight came with the work of [ 17 ] , who measure breadth with respect to a preference ordering on strings. In particular, a generator achieves breadth in the target language if, when strings in the language are sorted in order of preference, its outputs are dense in every sufficiently long prefix of the language. This approach to modeling breadth with respect to an inductive-bias on strings enabled remarkable progress in [ 17 , 18 ] , culminating in an algorithm achieving both consistency and optimal breadth in the limit. Timeliness can best be understood as a strengthening of the breadth requirements of [ 17 , 18 ] : in each prefix of the target language, a generated string only “counts” towards density if it is generated before its deadline. Our technical work starts with the realization that the algorithms of [ 17 , 18 ] , and in fact any eventually consistent generator, can not achieve timely generation. This impossibility holds for any deadline function, and any nontrivial guarantee on the prefix-density of timely outputs. In other words, consistent generators inevitably suffer mode collapse under a deadline . This motivates relaxing consistency: by permitting hallucinations at a rate tending to zero over time, we recover timely generation in the limit for any superlinear deadline function, and provide essentially-matching impossibility results. Next, we present the relevant technical preliminaries before formally stating our results. We defer more thorough discussion of related work to Appendix A . 1.1 Technical Preliminaries Basic Notation. We often make use of countably infinite sets which are ordered (i.e. enumerated) by a surjective map from the natural numbers. We denote such an ordered set as S=(s_{1},s_{2},\ldots) , where s_{i} denotes the i th element of the enumeration. We also use S_{i}=(s_{1},\ldots,s_{i})=s_{1:i} to denote the first i elements of the enumeration of S , and often refer to it as the prefix of S of size i . Alternatively, we sometimes do not fix the ordering of a countably infinite set K , and instead consider the space of all enumerations which we denote by \mathcal{E}(K) . Note that our notion of enumeration here can allow repetition, though in some cases we restrict attention to bijective enumerations. The Language Generation Game. As in [ 16 , 17 ] , we represent language generation as a game between an adversary and a generator. Both players have access to a countably infinite collection of languages \mathcal{L}=(L^{1},L^{2},\ldots) , defined over a countably infinite universe U=(u_{1},u_{2},\ldots) of “strings.” Note that both \mathcal{L} and U are equipped with a bijective enumeration order, which is fixed and known. In the case of U , we think of the order (u_{1},u_{2},\ldots) as encoding a preference (or inductive bias) on strings. This order on U induces a preference order on the strings in each language L\in\mathcal{L} by restriction—i.e, strings in L are also enumerated by a total order which is consistent with the order on U . The adversary first selects a target language K\in\mathcal{L} and an enumeration E=(e_{1},e_{2},\ldots) , where E\in\mathcal{E}(K) . The generator \mathcal{A}=\{\mathcal{A}_{t}:U^{t}\to U\}_{t=1}^{\infty} observes E sequentially. At time t , the generator outputs o_{t}=\mathcal{A}_{t}(e_{1:t})\in U that has not previously been observed or output. Let \mathcal{A}(E)=(o_{1},o_{2},\ldots) denote the output sequence of the generator. We allow \mathcal{A} to be randomized, in which case each \mathcal{A}_{t}(e_{1:t}) is a random variable, where expectations are over the internal randomness of the algorithm. Hallucination and Consistency. We say the generator hallucinates at time t if o_{t}\not\in K . We say it is eventually consistent if it is guaranteed to eventually stops hallucinating; i.e., there exists some finite time T (perhaps depending on \mathcal{L} , K , and E ) such that for all t\geq T the output o_{t}\in K . The celebrated result of [ 16 ] exhibits an eventually consistent generator for every language collection \mathcal{L} . Our impossibility results will necessitate relaxing consistency by allowing hallucinations that vanish over time. We define the hallucination rate of \mathcal{A} at step t , as a