Language Generation: Complexity Barriers and Implications for Learning
This work addresses the fundamental problem of understanding why language models work in practice despite theoretical complexity barriers, which is important for AI researchers and practitioners.
The paper demonstrates that for regular and context-free languages, the number of examples needed for successful language generation can be extraordinarily large or even uncomputable, revealing a gap between theoretical possibility and practical learnability.
Kleinberg and Mullainathan showed that, in principle, language generation is always possible: with sufficiently many positive examples, a learner can eventually produce sentences indistinguishable from those of a target language. However, the existence of such a guarantee does not speak to its practical feasibility. In this work, we show that even for simple and well-studied language families -- such as regular and context-free languages -- the number of examples required for successful generation can be extraordinarily large, and in some cases not bounded by any computable function. These results reveal a substantial gap between theoretical possibility and efficient learnability. They suggest that explaining the empirical success of modern language models requires a refined perspective -- one that takes into account structural properties of natural language that make effective generation possible in practice.