arXiv:2605.30324cs.DScs.AI2026-05被引 1

研究有限记忆下语言生成的极限能力,发现无记忆生成仍可行但效率受限。

On Language Generation in the Limit with Bounded Memory

  • 无记忆生成在枚举限制下可覆盖任意可数语言集合
  • 滑动窗口无法提升最坏情况下的生成密度,但自适应存储能改善
  • 增量识别需放松要求才可对任意有限集合实现

我们研究在有限记忆约束下的语言生成极限问题。学习者逐个观察未知目标语言的样本,最终必须仅输出新的有效句子。以往工作假设可访问全部历史,但实际算法只能保留有限过去信息。经典学习理论表明记忆限制会显著影响可学习性,本文将其扩展至语言生成。首先分析无记忆生成器:在温和枚举限制下,任意可数无限语言集合均可生成;否则精确刻画了无记忆生成的可行性条件。针对有限集合,刻画了无记忆生成器能达到的最优最小最大密度——对给定大小集合的最坏情形保障。该组合界依赖Sperner定理与对称链分解。进一步证明,仅存储最近W个样本的滑动窗口无法提升此最坏密度,而允许自适应存储b≥1个过去样本则可改善生成密度。最后重访极限识别问题,聚焦增量版本,即学习者仅保留上一次猜测。尽管对三个语言的集合精确识别失败,但只要放宽为收敛到目标的“近似”版本,对任意有限集合皆可实现。结果表明:生成对任意可数集合仍可行,而密度与识别仅对有限集合有保障,且随着集合规模增大,保证强度下降。

原文摘要 · Abstract (English)

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.

语言生成记忆约束学习理论形式语言

Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。