On Language Generation in the Limit with Bounded Memory

Jon Kleinberg; Anay Mehrotra; Amin Saberi; Grigoris Velegkas

cs.DSMay 28, 2026

On Language Generation in the Limit with Bounded Memory

Authors: Jon Kleinberg, Anay Mehrotra, Amin Saberi, Grigoris Velegkas

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.

Explore similar work

Jun 24, 2026cs.DS

Space-Efficient Language Generation in the Limit

We initiate a resource-aware theory of \textit{language generation in the limit} under the minimal constraint of space efficiency. In our framework, a learner observes an adversarial positive stream from a target language

K

and must eventually output a hallucination-free hypothesis language

L \subseteq K

while omitting at most

Δ

strings of

K

. We focus on

\mathcal{C}_{s,k}

, the collection of languages recognized by DFAs with at most

s

states over an alphabet of size

k

, as the natural hypothesis class for memory-bounded learners. In the exponential-space regime, we prove that a learner can exactly identify the target

K

. Under a stricter memory budget, we characterize the strongest possible generation guarantees. In particular, we present a streaming algorithm using

\mathrm{poly}(s,k)

space that converges to a hypothesis with generation gap

Δ= O(k^{2s-2})

. Moreover, the learned hypothesis captures every string in

K

of length at least

2s-1

. We complement this result with a near-matching lower bound through a reduction from a standard communication complexity problem. Specifically, achieving generation gap

Δ\le k^{(1-\varepsilon)s}

requires

k^{Ω(\varepsilon s)}

memory. Together, these results reveal a sharp transition between polynomial-space generation and exponential-space exact identification.

Nicolas Flammarion, Chirag Pabbaraju, Hristo Papazov +2

Context-Free Grammars Generating Fundamental Limits Optimal Sample Complexity Detecting Hallucinations

Ask PDF

May 11, 2026cs.LG

Mistake-Bounded Language Generation

We investigate the learning task of language generation in the limit, but shift focus from the traditional time-of-last-mistake metric of a generator's success to a new notion of "mistake-bounded generation." While existing results for language generation in the limit focus on guaranteeing eventual consistency, they are blind to the cumulative error incurred during the learning process. We address this by shifting the goal to minimizing the total number of invalid elements output by a generation algorithm. We establish a formal reduction to the Learning from Correct Demonstrations framework of Joshi et al. (2025), enabling a general recipe for deriving mistake bounds via weighted update rules. For finite classes, we provide an algorithm that simultaneously achieves an optimal last-mistake time of

\mathsf{Cdim}(L)

and a mistake bound of

\lfloor \log_2 |L| \rfloor

, whereas for the non-uniform setting of countably infinite streams of languages, we prove a fundamental trade-off: achieving logarithmic mistakes

O(\log i)

necessarily precludes convergence guarantees established in prior work. Finally, we show that our framework can be extended to accommodate noisy adversaries and guarantee mistake bounds that scale with the adversary's suboptimality.

Jon Kleinberg, Charlotte Peale, Omer Reingold

Optimization Convergence Analysis

Ask PDF

Jun 8, 2026cs.CL

Generating in the Limit with Infinitely Many Hallucinations

The classic paradigm of language identification in the limit models learning as a game between an adversary, who reveals strings from an unknown target language, and a learner tasked with identifying that language. The recently introduced framework of language generation in the limit shifted the objective to better reflect modern language modeling, requiring the learner to produce valid, unseen strings from the target language. Related work highlighted a fundamental tension: a broad coverage of the target often comes at the cost of validity. We introduce a new notion of precision and recast this problem as the classic recall-precision trade-off. We analyze generation in the limit under varying constraints on enumeration, novelty, and validity, aimed at reflecting settings closer to those encountered by large language models. A key contribution is our analysis of learners that are not eventually valid: we allow infinitely many mistakes, provided their frequency tends to zero so that precision remains one. We show that this relaxation can strictly increase recall when the adversary permanently withholds a large portion of the target language. We also study a continuous relaxation of the novelty constraint that requires only a fixed fraction of outputs to be novel. Taken together, our results move toward a more realistic model of language generation where occasional errors and repetitions are unavoidable, but their rates are controlled.

Irene Strauss, Alexandra Butoi, Ryan Cotterell

Fundamental Limits Generating Infinite Time Hallucination Problem

Ask PDF