arXiv:2605.10809cs.LGcs.DS2026-05被引 4

提出新框架,让语言生成模型在学习中尽量少犯错。

Mistake-Bounded Language Generation

  • 用累计错误数替代传统收敛时间,衡量生成质量
  • 有限语言类下实现最优最后犯错时间与对数级错误数
  • 适用于有噪声干扰的场景,错误数随干扰程度增长

我们研究语言生成在极限学习下的任务,将关注点从传统的最终一致时间转向新的“犯错次数有限生成”概念。现有方法只保证最终正确,却忽略学习过程中的累积错误。本文通过最小化生成算法输出的无效元素总数来改进这一问题。建立了与 Joshi 等人(2025)提出的「从正确示范中学习」框架的正式归约,提供了一般性方法:通过加权更新规则推导犯错边界。对于有限语言类,设计出一个算法,同时实现最优的最后犯错时间 $\mathsf{Cdim}(L)$ 与犯错上限 $\lfloor \log_2 |L| \rfloor$;在可数无限语言流的非均匀设定下,证明了根本性权衡:达到 $O(\log i)$ 的对数级错误数,必然无法保证先前工作中的收敛性。最后,我们扩展框架以应对噪声对抗者,确保犯错界限随对抗者次优性线性增长。

原文摘要 · Abstract (English)

We investigate the learning task of language generation in the limit, but shift focus from the traditional time-of-last-mistake metric of a generator's success to a new notion of "mistake-bounded generation." While existing results for language generation in the limit focus on guaranteeing eventual consistency, they are blind to the cumulative error incurred during the learning process. We address this by shifting the goal to minimizing the total number of invalid elements output by a generation algorithm. We establish a formal reduction to the Learning from Correct Demonstrations framework of Joshi et al. (2025), enabling a general recipe for deriving mistake bounds via weighted update rules. For finite classes, we provide an algorithm that simultaneously achieves an optimal last-mistake time of $\mathsf{Cdim}(L)$ and a mistake bound of $\lfloor \log_2 |L| \rfloor$, whereas for the non-uniform setting of countably infinite streams of languages, we prove a fundamental trade-off: achieving logarithmic mistakes $O(\log i)$ necessarily precludes convergence guarantees established in prior work. Finally, we show that our framework can be extended to accommodate noisy adversaries and guarantee mistake bounds that scale with the adversary's suboptimality.

语言生成学习理论犯错控制

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