Density Measures for Language Generation

• URL: http://arxiv.org/abs/2504.14370v1
• Date: Sat, 19 Apr 2025 18:08:18 GMT
• Title: Density Measures for Language Generation
• Authors: Jon Kleinberg, Fan Wei,
• Abstract summary: We study the trade-off between validity and breadth of language generation algorithms.<n>Existing algorithms for language generation in the limit produce output sets that can have zero density in the true language.<n>We show, however, that we provide an algorithm for language generation in the limit whose outputs have strictly positive density in $K$.
• Score: 2.2872032473279065
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The recent successes of large language models (LLMs) have led to a surge of theoretical research into language generation. A recent line of work proposes an abstract view, called language generation in the limit, where generation is seen as a game between an adversary and an algorithm: the adversary generates strings from an unknown language $K$, chosen from a countable collection of candidate languages, and after seeing a finite set of these strings, the algorithm must generate new strings from $K$ that it has not seen before. This formalism highlights a key tension: the trade-off between validity (the algorithm should only produce strings from the language) and breadth (it should be able to produce many strings from the language). This trade-off is central in applied language generation as well, where it appears as a balance between hallucination (generating invalid utterances) and mode collapse (generating only a restricted set of outputs). Despite its importance, this trade-off has been challenging to study quantitatively. We develop ways to quantify this trade-off by formalizing breadth using measures of density. Existing algorithms for language generation in the limit produce output sets that can have zero density in the true language, and this important failure of breadth might seem unavoidable. We show, however, that such a failure is not necessary: we provide an algorithm for language generation in the limit whose outputs have strictly positive density in $K$. We also study the internal representations built by these algorithms, specifically the sequence of hypothesized candidate languages they consider, and show that achieving the strongest form of breadth may require oscillating indefinitely between high- and low-density representations. Our analysis introduces a novel topology on language families, with notions of convergence and limit points playing a key role.

Related papers

• Exploring Facets of Language Generation in the Limit [10.18252143035175]
  We show that every countable language collection has a generator which has the stronger property of non-uniform generation in the limit.<n>We formalize the tension between validity and breadth in the generation algorithm of [KM24] by introducing a definition of exhaustive generation.<n>We also provide a precise characterization of the language collections for which exhaustive generation is possible.
  arXiv  Detail & Related papers  (2024-11-22T22:13:40Z)
• On the Limits of Language Generation: Trade-Offs Between Hallucination and Mode Collapse [16.30681257128492]
  Given samples from an unknown language, a language model should produce valid strings not seen in training. Otherwise, outputting invalid strings constitutes "hallucination," and failing to capture the full range leads to "mode collapse" We investigate this within a statistical language generation setting building on Gold and Angluin.
  arXiv  Detail & Related papers  (2024-11-14T18:06:55Z)
• Training Neural Networks as Recognizers of Formal Languages [87.06906286950438]
  We train and evaluate neural networks directly as binary classifiers of strings.<n>We provide results on a variety of languages across the Chomsky hierarchy for three neural architectures.<n>Our contributions will facilitate theoretically sound empirical testing of language recognition claims in future work.
  arXiv  Detail & Related papers  (2024-11-11T16:33:25Z)
• Language Generation in the Limit [0.7787343335258782]
  We show that there is an agent that is able to generate in the limit for every countable list of candidate languages. This contrasts dramatically with negative results due to Gold and Angluin in a well-studied model of language learning.
  arXiv  Detail & Related papers  (2024-04-10T05:53:25Z)
• Unlocking Anticipatory Text Generation: A Constrained Approach for Large Language Models Decoding [75.06872859716049]
  Large Language Models (LLMs) have demonstrated a powerful ability for text generation. undesired behaviors such as toxicity or hallucinations can manifest. We propose formalizing text generation as a future-constrained generation problem.
  arXiv  Detail & Related papers  (2023-12-11T06:35:33Z)
• Typical Decoding for Natural Language Generation [76.69397802617064]
  We study why high-probability texts can be dull or repetitive. We show that typical sampling offers competitive performance in terms of quality.
  arXiv  Detail & Related papers  (2022-02-01T18:58:45Z)
• Towards Language Modelling in the Speech Domain Using Sub-word Linguistic Units [56.52704348773307]
  We propose a novel LSTM-based generative speech LM based on linguistic units including syllables and phonemes. With a limited dataset, orders of magnitude smaller than that required by contemporary generative models, our model closely approximates babbling speech. We show the effect of training with auxiliary text LMs, multitask learning objectives, and auxiliary articulatory features.
  arXiv  Detail & Related papers  (2021-10-31T22:48:30Z)
• Generating texts under constraint through discriminator-guided MCTS [1.3750624267664153]
  We formalize constrained generation as a tree exploration process guided by a discriminator. Using a discriminator to guide this generation, rather than fine-tuning the LM, allows to apply the constraint more finely and dynamically. We show that our methods achieves state-of-the-art results in constrained generation, without having to tune the language model.
  arXiv  Detail & Related papers  (2021-09-28T09:29:15Z)
• Provable Limitations of Acquiring Meaning from Ungrounded Form: What will Future Language Models Understand? [87.20342701232869]
  We investigate the abilities of ungrounded systems to acquire meaning. We study whether assertions enable a system to emulate representations preserving semantic relations like equivalence. We find that assertions enable semantic emulation if all expressions in the language are referentially transparent. However, if the language uses non-transparent patterns like variable binding, we show that emulation can become an uncomputable problem.
  arXiv  Detail & Related papers  (2021-04-22T01:00:17Z)
• Paraphrase Generation as Zero-Shot Multilingual Translation: Disentangling Semantic Similarity from Lexical and Syntactic Diversity [11.564158965143418]
  We introduce a simple paraphrase generation algorithm which discourages the production of n-grams that are present in the input. Our approach enables paraphrase generation in many languages from a single multilingual NMT model.
  arXiv  Detail & Related papers  (2020-08-11T18:05:34Z)
• Limits of Detecting Text Generated by Large-Scale Language Models [65.46403462928319]
  Some consider large-scale language models that can generate long and coherent pieces of text as dangerous, since they may be used in misinformation campaigns. Here we formulate large-scale language model output detection as a hypothesis testing problem to classify text as genuine or generated.
  arXiv  Detail & Related papers  (2020-02-09T19:53:23Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.