Fetching the paper…

Reading the bibliography…

2024

Language Generation in the Limit

Kleinberg, Jon, Mullainathan, Sendhil

Original
PDF
Post on X

Understand

Although current large language models are complex, the most basic specifications of the underlying language generation problem itself are simple to state: given a finite set of training samples from an unknown language, produce valid new strings from the language that don't already appear in the training data.

Here we ask what we can conclude about language generation using only this specification, without further assumptions.
In particular, suppose that an adversary enumerates the strings of an unknown target language L that is known only to come from one of a possibly infinite list of candidates.
A computational agent is trying to learn to generate from this language; we say that the agent generates from L in the limit if after some finite point in the enumeration of L, the agent is able to produce new elements that come exclusively from L and that have not yet been presented by the adversary.

Language Generation in the Limit · Around

Built on

Language identification in the limit
E Mark Gold · 1967
Earlier work this paper cites.
Finding patterns common to a set of strings
Dana Angluin · 1979
Earlier work this paper cites.
Inductive inference of formal languages from positive data
Dana Angluin · 1980
Earlier work this paper cites.
Learning of context-free languages: A survey of the literature
Lillian Lee · 1996
Earlier work this paper cites.

Similar

No country for old members: User lifecycle and linguistic change in online communities
Cristian Danescu-Niculescu-Mizil, Robert West, Dan Jurafsky, Jure Leskovec, and Christopher Potts · 2013
Cited alongside, same era.
Towards principled methods for training generative adversarial networks
Martín Arjovsky and Léon Bottou · 2017
Cited alongside, same era.
Wasserstein generative adversarial networks
Martín Arjovsky, Soumith Chintala, and Léon Bottou · 2017
Cited alongside, same era.

Then

Survey of hallucination in natural language generation
Ziwei Ji, Nayeon Lee, Rita Frieske, Tiezheng Yu, Dan Su, Yan Xu, Etsuko Ishii, Ye Jin Bang, Andrea Madotto, and Pascale Fung · 2023
Later among the works it cites.
Calibrated language models must hallucinate
Adam Tauman Kalai and Santosh S Vempala · 2024
Closest in time.
Hallucination is inevitable: An innate limitation of large language models
Original
Ziwei Xu, Sanjay Jain, and Mohan Kankanhalli · 2024
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…