Space-Efficient Language Generation in the Limit

• URL: http://arxiv.org/abs/2606.25777v1
• Date: Wed, 24 Jun 2026 12:55:34 GMT
• Title: Space-Efficient Language Generation in the Limit
• Abstract summary: We propose a resource-aware theory of textit generation in the limit under the minimal constraint of space efficiency.<n>We focus on $mathcalC_s,k$, the collection of languages recognized by DFAs with at most $s$ states over an alphabet of size $k$.<n>Under a stricter memory budget, we characterize the strongest possible generation guarantees.
• Score: 34.38365460078856
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• An Optimal Agnostic PAC Algorithm [15.361702135159845]
  We write $L$ for the binary risk and $L*=min_hin HL(h)$, we construct a learner achieving the statistically optimal risk bound.<n>This settles the agnostic sample complexity of PAC learning up to universal constants at every fixed $L*$.
  arXiv  Detail & Related papers  (2026-08-06T17:57:25Z)
• On the Price of Privacy for Language Identification and Generation [39.91890433860882]
  We study the cost of privacy in language learning by studying differentially private (DP) language identification and generation.<n>Our results show that the cost of privacy in language learning is surprisingly mild: absent entirely under approximate DP, and exactly a $min1,varepsilon$ factor in the exponent under pure DP.
  arXiv  Detail & Related papers  (2026-04-08T16:04:16Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  We establish new exponential in dimension lower bounds for the Maximum Halfspace Discrepancy problem.<n>Both are fundamental problems in computational geometry and machine learning in their exact and approximate forms.
  arXiv  Detail & Related papers  (2026-03-19T15:53:41Z)
• Language Generation and Identification From Partial Enumeration: Tight Density Bounds and Topological Characterizations [1.6203023551115867]
  We study the framework of emphlanguage generation in the limit, where an adversary enumerates strings from an unknown language.<n>We show that generation in the limit remains achievable, and if $C$ has lower density $alpha$ in $K$, the algorithm's output achieves density at least $alpha/2$.<n>We characterize when identification in the limit is possible -- when hypotheses $M_t$ eventually satisfy $C subseteq M subseteq K$.
  arXiv  Detail & Related papers  (2025-11-07T14:56:04Z)
• Actively Learning Halfspaces without Synthetic Data [34.777547976926456]
  We design efficient algorithms for learning halfspaces without point synthesis.<n>As a corollary, we obtain an optimal $O(d + log n)$ query deterministic learner for axis-aligned halfspaces.<n>Our algorithm solves the more general problem of learning a Boolean function $f$ over $n$ elements which is monotone under at least one of $D$ provided orderings.
  arXiv  Detail & Related papers  (2025-09-25T07:39:25Z)
• Guessing Efficiently for Constrained Subspace Approximation [49.83981776254246]
  We introduce a general framework for constrained subspace approximation.<n>We show it provides new algorithms for partition-constrained subspace approximation with applications to $k$-means clustering, and projected non-negative matrix factorization.
  arXiv  Detail & Related papers  (2025-04-29T15:56:48Z)
• On Optimal Learning Under Targeted Data Poisoning [48.907813854832206]
  In this work we aim to characterize the smallest achievable error $epsilon=epsilon(eta)$ by the learner in the presence of such an adversary. Remarkably, we show that the upper bound can be attained by a deterministic learner.
  arXiv  Detail & Related papers  (2022-10-06T06:49:48Z)
• Matrix hypercontractivity, streaming algorithms and LDCs: the large alphabet case [3.729242965449096]
  We consider streaming algorithms for approximating the value of Unique Games on a hypergraph with $t$-size hyperedges. We show that every streaming algorithm in the adversarial model achieving an $(r-varepsilon)$-approximation of this value requires $Omega(n1-2/t)$ quantum space.
  arXiv  Detail & Related papers  (2021-09-06T16:56:19Z)
• Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
  We study the problem of PAC learning halfspaces on $mathbbRd$ with Massart noise under Gaussian marginals. Our results qualitatively characterize the complexity of learning halfspaces in the Massart model.
  arXiv  Detail & Related papers  (2021-08-19T16:16:48Z)
• Learning a Latent Simplex in Input-Sparsity Time [58.30321592603066]
  We consider the problem of learning a latent $k$-vertex simplex $KsubsetmathbbRdtimes n$, given access to $AinmathbbRdtimes n$. We show that the dependence on $k$ in the running time is unnecessary given a natural assumption about the mass of the top $k$ singular values of $A$.
  arXiv  Detail & Related papers  (2021-05-17T16:40:48Z)
• RNNs can generate bounded hierarchical languages with optimal memory [113.73133308478612]
  We show that RNNs can efficiently generate bounded hierarchical languages that reflect the scaffolding of natural language syntax. We introduce Dyck-($k$,$m$), the language of well-nested brackets (of $k$ types) and $m$-bounded nesting depth. We prove that an RNN with $O(m log k)$ hidden units suffices, an exponential reduction in memory, by an explicit construction.
  arXiv  Detail & Related papers  (2020-10-15T04:42:29Z)

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.