在极低内存下实现语言生成的精确理论，揭示了高效与完全准确间的分界线。
Space-Efficient Language Generation in the Limit
- 以状态数为约束的有限自动机作为假设类，研究内存受限下的语言生成。
- 仅用多项式空间即可生成几乎完整的目标语言，遗漏字符串数不超过 $O(k^{2s-2})$。
- 适用于资源受限场景的在线学习系统，如嵌入式设备上的语言模型部署。
我们启动了对空间效率约束下语言生成极限的资源感知理论研究。在该框架中，学习者从目标语言 $K$ 的对抗性正例流中观察，并需最终输出一个不含幻觉的假设语言 $L \⊆ K$，且最多遗漏 $Δ$ 个 $K$ 中的字符串。聚焦于由最多 $s$ 个状态、字母表大小为 $k$ 的确定有限自动机（DFA）识别的语言类 $\ℌ_{s,k}$，作为记忆受限学习者的自然假设类。在指数级空间条件下，学习者可精确识别目标语言 $K$。在更严格的内存预算下，我们刻画了最强的生成保证：提出一种使用 $\mathrm{poly}(s,k)$ 空间的流式算法，收敛后生成的假设语言与目标语言的生成差距 $Δ= O(k^{2s-2})$，且能覆盖所有长度至少为 $2s-1$ 的 $K$ 中字符串。通过归约至经典通信复杂性问题，我们给出紧致下界：要使 $Δ \le k^{(1-\varepsilon)s}$，必须使用 $k^{Ω(\varepsilon s)}$ 的内存。结果揭示了多项式空间生成与指数空间精确识别之间的清晰跃迁。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。