
Language Generation in the Limit
Jon Kleinberg of Cornell University presents a theoretical framework for language generation, delivered as part of the Institute for Advanced Study's Computer Science/Discrete Mathematics Seminar. He poses the problem in its barest form: given finitely many samples from an unknown language drawn from a possibly infinite set of candidate languages, produce new valid strings not seen in training. Modeling this as an adversarial process in which an enemy enumerates strings of the unknown target language, Kleinberg shows that nontrivial generation guarantees are still achievable. He contrasts this with the negative results of Gold and Angluin on language identification from samples, arguing that generating from a language is a fundamentally different and more tractable problem than identifying it. The talk presents joint work with Sendhil Mullainathan and Fan Wei, building a formal bridge between classical language learning theory and the practical behavior of modern large language models.