# Space-Efficient Language Generation in the Limit

arXiv: https://arxiv.org/abs/2606.25777 · HTML: https://mlsanity.com/paper/2606.25777/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 34 references that are in the map.
- First posted on arXiv 24 Jun 2026.

## Builds on (most cited first, 14 of 14)

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [The Illusion of State in State-Space Models](https://mlsanity.com/paper/2404.08819/) (2024)
- [Language Generation in the Limit](https://mlsanity.com/paper/2404.06757/) (2024)
- [Transformers Can Represent n-gram Language Models](https://mlsanity.com/paper/2404.14994/) (2024)
- [Generation through the lens of learning theory](https://mlsanity.com/paper/2410.13714/) (2024)
- [Exploring Facets of Language Generation in the Limit](https://mlsanity.com/paper/2411.15364/) (2024)
- [Density Measures for Language Generation](https://mlsanity.com/paper/2504.14370/) (2025)
- [Generation from Noisy Examples](https://mlsanity.com/paper/2501.04179/) (2025)
- [Representative Language Generation](https://mlsanity.com/paper/2505.21819/) (2025)
- [On Union-Closedness of Language Generation](https://mlsanity.com/paper/2506.18642/) (2025)
- [Pareto-optimal Non-uniform Language Generation](https://mlsanity.com/paper/2510.02795/) (2025)
- [Learning Algorithms in the Limit](https://mlsanity.com/paper/2506.15543/) (2025)
- [A Characterization of List Language Identification in the Limit](https://mlsanity.com/paper/2511.04103/) (2025)
- [Recurrent Neural Language Models as Probabilistic Finite-state Automata](https://mlsanity.com/paper/2310.05161/) (2023)

## Built on by (most cited first, 1 of 1)

- [Hallucination Rates in Language Generation](https://mlsanity.com/paper/2607.23361/) (2026)

## Abstract (arXiv)

We initiate a resource-aware theory of textitlanguage 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 Delta strings of K. We focus on Cs,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 poly(s,k) space that converges to a hypothesis with generation gap Delta = O(k2s-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 Delta ≤ k(1-varepsilon)s requires kOmega(varepsilon s) memory. Together, these results reveal a sharp transition between polynomial-space generation and exponential-space exact identification.