Abstract
Specifying all desirable properties of a language model is challenging, butcertain requirements seem essential. Given samples from an unknown language,the trained model should produce valid strings not seen in training and beexpressive enough to capture the language's full richness. Otherwise,outputting invalid strings constitutes "hallucination," and failing to capturethe full range leads to "mode collapse." We ask if a language model can meetboth requirements. We investigate this within a statistical language generation setting buildingon Gold and Angluin. Here, the model receives random samples from adistribution over an unknown language K, which belongs to a possibly infinitecollection of languages. The goal is to generate unseen strings from K. We saythe model generates from K with consistency and breadth if, as training sizeincreases, its output converges to all unseen strings in K. Kleinberg and Mullainathan [KM24] asked if consistency and breadth inlanguage generation are possible. We answer this negatively: for a large classof language models, including next-token prediction models, this is impossiblefor most collections of candidate languages. This contrasts with [KM24]'sresult, showing consistent generation without breadth is possible for anycountable collection of languages. Our finding highlights that generation withbreadth fundamentally differs from generation without breadth. As a byproduct, we establish near-tight bounds on the number of samplesneeded for generation with or without breadth. Finally, our results offer hope: consistent generation with breadth isachievable for any countable collection of languages when negative examples(strings outside K) are available alongside positive ones. This suggests thatpost-training feedback, which encodes negative examples, can be crucial inreducing hallucinations while limiting mode collapse.