On Language Generation in the Limit with Bounded Memory

• URL: http://arxiv.org/abs/2605.30324v1
• Date: Thu, 28 May 2026 17:57:03 GMT
• Title: On Language Generation in the Limit with Bounded Memory
• Abstract summary: We study language generation in the limit under bounded memory.<n>In this task, a learner observes examples from an unknown target language one at a time and must eventually output only new valid examples.
• Score: 17.70989972580602
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study language generation in the limit under bounded memory. In this task, a learner observes examples from an unknown target language one at a time and must eventually output only new valid examples. Prior work assumes access to the entire history, a strong assumption since realistic algorithms retain limited past information. Classical work in learning theory shows memory constraints dramatically alter learnability; we extend this to language generation. First, we study memoryless generators. Under a mild enumeration restriction, every countable collection of infinite languages remains generable without memory. Without this restriction, we exactly characterize when memoryless generation is possible. For finite collections, we characterize the optimal minimax density achievable by memoryless generators -- the best density guaranteed against any collection of a given size. This combinatorial bound relies on Sperner's theorem and symmetric chain decompositions. We further show that a sliding window of the last $W$ examples does not improve this worst-case density, whereas allowing it to store $b$ adaptively chosen past examples improves the achievable density for every $b \geq 1$. Finally, we revisit identification in the limit, where the learner must converge to a single correct hypothesis for the target language. We focus on its incremental variant, where the learner remembers only its previous guess. Here, although exact identification fails on a collection of just three languages, a mild relaxation requiring convergence to an ``approximate'' version of the target is achievable for every finite collection. These results show bounded memory affects these tasks differently: generation remains achievable for every countable collection, while density and identification are confined to finite collections, with guarantees weakening as the collection grows.

Related papers

• Generating in the Limit with Infinitely Many Hallucinations [86.48063079851867]
  Recently introduced framework of language generation in the limit requires the learner to produce valid, unseen strings from the target language.<n>We introduce a new notion of precision and recast this problem as the classic recall-precision trade-off.<n>We show that this relaxation can strictly increase recall when the adversary permanently withholds a large portion of the target language.
  arXiv  Detail & Related papers  (2026-06-08T09:58:13Z)
• Mistake-Bounded Language Generation [6.034531760235531]
  We investigate the learning task of language generation in the limit.<n>We shift focus from the traditional time-of-last-mistake metric to a new notion of "mistake-bounded generation"<n>We show that our framework can be extended to accommodate noisy adversaries.
  arXiv  Detail & Related papers  (2026-05-11T16:32:01Z)
• Language Generation with Infinite Contamination [17.31852533022177]
  We study language generation in the limit, where an algorithm observes an adversarial enumeration of strings from an unknown target language $K$.<n>We show that generation with density, surprisingly, remains achievable at the same generality.<n>This suggests curriculum learning may be crucial for learning from noisy web data.
  arXiv  Detail & Related papers  (2025-11-10T18:59:39Z)
• A Characterization of List Language Identification in the Limit [31.38302438096483]
  We study the problem of language identification in the limit, where given a sequence of examples from a target language.<n>The goal of the learner is to output a sequence of guesses for the target language such that all the guesses beyond some finite time are correct.<n>We give an exact characterization of collections of languages that can be $k$-list identified in the limit.
  arXiv  Detail & Related papers  (2025-11-06T06:39:20Z)
• On Union-Closedness of Language Generation [48.36356615217017]
  We investigate language generation in the limit - a model by Kleinberg and Mullainathan and extended by Li, Raman, and Tewari.<n>Our results resolve two open questions of Li et al. by proving finite unions of generatable or non-uniformly generatable classes need not be generatable.<n>Our approach utilizes carefully constructed classes along with a novel diagonalization argument that could be of independent interest in the growing area of language generation.
  arXiv  Detail & Related papers  (2025-06-23T13:42:25Z)
• 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)
• Hierarchical Context Merging: Better Long Context Understanding for Pre-trained LLMs [61.40047491337793]
  We present Hierarchical cOntext MERging (HOMER), a new training-free scheme designed to overcome the limitations of large language models. HomeR uses a divide-and-conquer algorithm, dividing long inputs into manageable chunks. A token reduction technique precedes each merging, ensuring memory usage efficiency.
  arXiv  Detail & Related papers  (2024-04-16T06:34:08Z)
• Lift Yourself Up: Retrieval-augmented Text Generation with Self Memory [72.36736686941671]
  We propose a novel framework, selfmem, for improving retrieval-augmented generation models. Selfmem iteratively employs a retrieval-augmented generator to create an unbounded memory pool and using a memory selector to choose one output as memory for the subsequent generation round. We evaluate the effectiveness of selfmem on three distinct text generation tasks.
  arXiv  Detail & Related papers  (2023-05-03T21:40:54Z)
• A Measure-Theoretic Characterization of Tight Language Models [105.16477132329416]
  In some pathological cases, probability mass can leak'' onto the set of infinite sequences. This paper offers a measure-theoretic treatment of language modeling. We prove that many popular language model families are in fact tight, meaning that they will not leak in this sense.
  arXiv  Detail & Related papers  (2022-12-20T18:17:11Z)
• Language learnability in the limit for general metrics: a Gold-Angluin result [91.3755431537592]
  We use Niyogi's extended version of a theorem by Blum and Blum (1975) on the existence of locking data sets to prove a necessary condition for learnability in the limit of any family of languages in any given metric. When the language family is further assumed to contain all finite languages, the same condition also becomes sufficient for learnability in the limit.
  arXiv  Detail & Related papers  (2021-03-24T13:11:09Z)
• Learning Languages in the Limit from Positive Information with Finitely Many Memory Changes [0.0]
  We show that non-U-shapedness is not restrictive, while conservativeness and (strong) monotonicity are. We also give an example of a non-semantic restriction (strongly non-U-shapedness) where the two settings differ.
  arXiv  Detail & Related papers  (2020-10-09T19:59:49Z)

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.