arXiv:2608.01320cs.DScs.AI2026-08被引 1

提出统一算法框架,实现语言生成的最优覆盖率。

Dense Language Generation Made Simple: Deterministic, Randomized, and Multi-Order Algorithms

  • 设计简洁算法,实现确定性下1/2的最优输出覆盖率
  • 随机化可提升覆盖率至1-1/e,适用于固定对手
  • 支持多重要性顺序,兼顾多种评估标准无损失

语言生成极限是一种理论框架,研究生成器如何从正例流中学习产生新有效字符串。在该模型中,对手从可数语言族中选择未知语言,并以任意顺序枚举其元素,生成器需最终仅输出尚未出现的语言元素。可靠生成通过两个渐进保证定义:相对于观测数据的有效性与新颖性。为量化生成器输出广度,Kleinberg和Wei(FOCS 2025, STOC 2026)引入下密度作为输出覆盖度量。下密度是在目标语言前n个元素中,生成器在数据出现前输出的比例的渐近下界。他们证明确定性算法的最优下密度为1/2。本文提出一个简洁统一的框架,首先给出一种分析更简单的确定性算法,恢复1/2的最优保证;其次展示框架灵活性:面对非自适应对手时,随机化可将最优保证提升至1-1/e;对于任意有限个顺序集合,可同时在每个顺序下达到最优确定性与随机化保证,实现多重要性标准兼容而无需性能损失。

原文摘要 · Abstract (English)

Language generation in the limit is a theoretical framework for studying how a generator can learn to produce new valid strings from a stream of positive examples. In this model, an adversary chooses an unknown language from a countable family and enumerates its elements in an arbitrary order, while the generator must eventually output only elements of the language that have not yet appeared in the enumeration. Reliable generation is thus formalized through two eventual guarantees: validity and novelty relative to the observed data. To further quantify the breadth of the generator's outputs, Kleinberg and Wei (FOCS 2025, STOC 2026) introduced lower density as a measure of output coverage. Given an order representing the importance or relevance of possible outputs, lower density is the asymptotic lower bound, as $n$ grows, on the fraction of the first $n$ elements of the target language that the generator outputs before they appear in the data. Kleinberg and Wei showed that $1/2$ is the optimal lower-density guarantee for deterministic algorithms. We develop a simple and unified framework for obtaining optimal lower-density guarantees. We first give a deterministic algorithm that recovers the optimal guarantee of $1/2$ with a significantly simpler analysis than prior work. We then demonstrate the flexibility of our framework through two extensions. First, against an oblivious adversary, randomization raises the optimal guarantee to $1-1/e$. Second, for any finite collection of orders, the optimal deterministic and randomized guarantees can be achieved simultaneously with respect to every order, so accommodating multiple notions of importance or relevance entails no loss in the optimal guarantee.

语言生成算法优化下密度随机化

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