跳转至

Generating in the Limit with Infinitely Many Hallucinations

会议: NeurIPS 2026
arXiv: 2606.28354
OpenReview: https://openreview.net/forum?id=Z78RzgzukZ
领域: 幻觉检测
关键词: 极限语言生成、幻觉控制、精确率-召回率权衡、尾部精确率、连续新颖性约束

一句话总结

本文将极限语言生成（Language Generation in the Limit）重构为精确率-召回率权衡框架，证明了当允许无限次但频率趋于零的幻觉（即放宽尾部精确率但保持全局精确率为 1）或允许固定比例的非新颖重复输出（\(\gamma < 1\)）时，能够突破现有零幻觉算法在稀疏对抗暴露下的召回率上限，甚至实现精确率与召回率同时收敛至 1。

研究背景与动机

经典极限语言识别（Gold, 1967; Angluin, 1980）要求学习器在观测无限字符串流后精确锁定目标语言 \(T\)，但这对于哪怕正则语言等常见可数语言族也是不可行的。受现代大语言模型启发，Kleinberg and Mullainathan (2024) 提出了极限语言生成范式：学习器无需识别整个语言，只需在某个有限时间步之后持续生成属于 \(T\) 且此前未见过的新字符串（即“最终有效性”，Eventual Validity）。然而，单纯满足最终有效性会导致严重的覆盖度退化——生成算法完全可以蜷缩在 \(T\) 的某个任意稀疏的无限子集上安全输出，虽规避了错误（幻觉），却漏掉了目标语言的绝大多数内容。后续研究（Charikar and Pabbaraju, 2025; Kalavasis et al., 2025）证实了覆盖度与有效性之间的根本张力；Kleinberg and Wei (2025a, 2025b) 进一步引入密度度量，证明在对抗者仅暴露密度为 \(\alpha\) 的子语言且要求严格新颖性与零最终幻觉时，生成密度的最优下界仅为 \(\alpha/2\)。

现有理论框架的核心痛点在于其假设过于严苛且脱离现代大语言模型的真实工况：一方面，“最终有效性”要求在有限步后彻底杜绝任何幻觉（仅允许有限次错误），而在对抗者永久隐瞒大部分目标语言（\(\alpha \to 0\)）时，这种零幻觉约束会将召回率死死锁在接近 0 的水平；另一方面，严格新颖性约束（完全禁止复述训练集中出现过的字符串）使对抗者可以通过抢先暴露字符串来“偷走”生成空间，而在现实文本生成（如引用原文或事实复述）中，适度重复已知样本不仅是合理的，更是提升覆盖率的关键。此外，由于目标语言 \(T\) 和生成语言 \(G\) 均为无限集合，传统的有限集精确率与召回率比值 \(\infty/\infty\) 在数学上无定义，现有文献仅定义了等价于召回率的覆盖密度，却缺乏与之对称的、能够刻画无限流中渐近错误率（幻觉率）的精确率度量。

本文的切入角度是利用有限逼近序列（穷举，Exhaustions）在无限语言上严格定义基于成员资格的全局精确率、覆盖召回率与“尾部精确率”（Tail Precision），将最终有效性等价刻画为尾部精确率在有限时间内稳定至 1，进而探究放宽尾部精确率与新颖性约束后的理论边界。核心 idea：允许生成器在稀疏调度的探索轮次中犯无限次幻觉错误（只要幻觉发生率渐近趋于 0 以维持全局精确率为 1），并引入连续参数 \(\gamma \in [0, 1]\) 控制新颖输出比例，通过将安全生成例程（适配 \(k\)-批量对抗的 Pods 算法）与遍历 \(\Sigma^*\) 的稀疏探索或重复轮次交替运行，在不牺牲渐近精确率的前提下大幅突破召回率瓶颈。

方法详解

整体框架

本文构建了一套針對无限语言的近似学习度量与极限生成算法体系。给定可数无限语言族 \(\mathcal{T}\) 中的未知目标语言 \(T \subseteq \Sigma^*\)，对抗者按时间步 \(n=1,2,\dots\) 逐步暴露子语言 \(A \subseteq T\) 的有限逼近序列（穷举 \(\boldsymbol{A} = \{A_n\}_{n=0}^\infty\)，其相对于目标枚举 \(\boldsymbol{T}\) 的下召回率 \(\widehat{\rho}_*(\boldsymbol{T}, A) \ge \alpha\)、上召回率 \(\widehat{\rho}^*(\boldsymbol{T}, A) \le \beta\)），生成器则基于已观测集合 \(A_n\) 与历史生成集合 \(G_{n-1}\) 输出新字符串以构成猜测穷举 \(\boldsymbol{G} = \{G_n\}_{n=0}^\infty\)。整体方法首先通过无穷序列极限（上/下极限与跨穷举上确界）建立无限集上的精确率 \(\widehat{\pi}_*(T, \boldsymbol{G})\)、召回率 \(\widehat{\rho}_*(\boldsymbol{T}, G)\) 与尾部精确率 \(\widehat{\tau}_*(T, \boldsymbol{G})\)；随后引入 \(\gamma\)-新颖性约束与稀疏探索集 \(R \subset \mathbb{N}\)；最终在每个时间步根据调度规则，将适配 2-批量对抗的“安全生成轮次”（基于一致假设交集链与全局 Pod 池）与“探索/重复轮次”（按固定枚举遍历 \(\Sigma^*\) 或复述 \(A_n\)）交替执行，从而在不同约束组合下逼近理论最优的精确率-召回率边界。

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["输入：对抗穷举序列 A_n ⊆ T<br/>语言族 T 与全序枚举 E (Σ*)"] --> B["无穷集精确率-召回率与尾部精确率度量<br/>基于穷举序列定义 π̂_*, ρ̂_*, τ̂_*"]
    B --> C["γ-新颖性松弛与可容许探索集调度<br/>设定新颖比例 γ 与稀疏探索集 R"]
    C -->|m ∉ R：进入安全轮次| D["k-批量安全 Pods 生成与探索交替机制<br/>安全分支：更新一致交集链 C_n 与激进集<br/>填充全局 Pod 池 P_n 并输出最小未用串"]
    C -->|m ∈ R：进入探索/重复轮次| E["k-批量安全 Pods 生成与探索交替机制<br/>探索/重复分支：遍历 Σ* 枚举 E 或复述 A_m<br/>回收对抗者永久隐瞒或抢占的字符串"]
    D --> F["输出：生成穷举序列 G_n ↑ G<br/>实现渐近精确率 π̂_* = 1 与高召回率 ρ̂_*"]
    E --> F

关键设计

1. 无穷集精确率-召回率与尾部精确率度量：用有限穷举序列解决无限语言的双向误差与幻觉刻画

由于无限语言 \(T\) 和 \(G\) 上不存在均匀分布，且基数比值 \(\infty/\infty\) 无定义，本文利用“穷举”（Exhaustion，即满足 \(S_0 = \emptyset, S_n \subseteq S_{n+1}\) 且 \(\bigcup_{n=0}^\infty S_n = S\) 的有限集递增序列 \(\boldsymbol{S} = \{S_n\}_{n=0}^\infty\)，若每步增量 \(|\Delta S_n| \le f(n)\) 则称为 \(f\)-有界穷举，\(f(n)=1\) 且每步严格增 1 为枚举 Enumeration）来定义评估指标。如果直接比较目标穷举 \(\boldsymbol{T}\) 与猜测穷举 \(\boldsymbol{G}\) 的前缀交集比值 \(\liminf_{n\to\infty} |T_n \cap G_n|/|G_n|\)，结果会受限于 \(T\) 被穷举的具体顺序；而一个生成串是否有效（非幻觉）只取决于它是否属于完整的 \(T\)。为此，本文对所有可能的目标穷举取上确界，定义“基于成员资格的下精确率” \(\widehat{\pi}_*(T, \boldsymbol{G}) = \sup_{\boldsymbol{T} \in \mathcal{E}(T)} \pi_*(\boldsymbol{T}, \boldsymbol{G})\)，并在 Theorem 2.1 中严格证明对于任意 \(f\)-有界猜测穷举，该上确界恰好等于直观的成员资格渐近比例：

\[\widehat{\pi}_*(T, \boldsymbol{G}) = \sup_{\boldsymbol{T} \in \mathcal{E}_f(T)} \pi_*(\boldsymbol{T}, \boldsymbol{G}) = \liminf_{n\to\infty} \frac{|T \cap G_n|}{|G_n|}\]

对称地，给定目标枚举 \(\boldsymbol{T}\)，通过对所有猜测穷举取上确界得到“基于覆盖度的下召回率” \(\widehat{\rho}_*(\boldsymbol{T}, G) = \sup_{\boldsymbol{G} \in \mathcal{E}(G)} \rho_*(\boldsymbol{T}, \boldsymbol{G}) = \liminf_{n\to\infty} \frac{|T_n \cap G|}{|T_n|}\)（Lemma 2.2），这在数学上推广了 Kleinberg and Wei (2025a) 的密度度量。为了进一步区分“累计错误率趋于 0”与“有限步后完全不犯错”，本文定义了仅考察单步新增集合 \(\Delta G_n = G_n \setminus G_{n-1}\) 的单步尾部精确率 \(t_n = |T \cap \Delta G_n| / |\Delta G_n|\)（当 \(|\Delta G_n|=0\) 时定为 1），并定义下尾部精确率 \(\widehat{\tau}_*(T, \boldsymbol{G}) = \liminf_{n\to\infty} t_n\)。Proposition 2.4 与 Proposition 3.3 揭示了一个关键结构性质：对于单步（或 \(c\)-步有界）穷举，\(\widehat{\tau}_*(T, \boldsymbol{G})\) 只能在有限步内达到并稳定在离散值（单步下非 0 即 1），且生成器满足 Kleinberg and Mullainathan (2024) 的“最终有效性”（\(|G \setminus T| < \infty\)）当且仅当 \(\widehat{\tau}_*(T, \boldsymbol{G}) = 1\) 在有限时间内达成。然而，若生成器仅在时间步 \(n = 2^m\) 输出一个不属于 \(T\) 的幻觉串、其余时间输出合法串，则前 \(n\) 步累计幻觉数仅为 \(\Theta(\log n)\)，此时尾部精确率 \(\widehat{\tau}_*(T, \boldsymbol{G}) = 0\)（无限次幻觉），但全局精确率依然满足 \(\widehat{\pi}_*(T, \boldsymbol{G}) = 1\)。这一分离为“用稀疏无限次幻觉换取高召回率”奠定了理论支点。

2. \(\gamma\)-新颖性松弛与可容许探索集调度：控制非新颖输出配额与渐近消失的探索频率

在严格新颖性约束（Definition 3.4，\(G_n\) 绝不能包含任何已在 \(A_n \cup G_{n-1}\) 中出现过的字符串）下，对抗者每暴露一个字符串就永久剥夺了生成器输出该串的权利，导致即使对抗者完整枚举 \(T\)，最终有效生成器的召回率也被死死压制在 \(1/2\) 以内（Theorem 3.5 & 3.6）。为了刻画允许适度引用/重复训练数据的现实生成场景，本文在 Definition 3.7 中引入连续新颖性参数 \(\gamma \in [0, 1]\)：定义累计新颖集合 \(N_0 = \emptyset, N_n = N_{n-1} \cup (\Delta G_n \setminus A_n)\)（即在首次生成时尚未被对抗者暴露的新串集合），若对所有 \(|G_n| > 0\) 的时间步均满足

\[\frac{|N_n|}{|G_n|} \ge \gamma\]

则称生成器是 \(\gamma\)-新颖的（\(\gamma=1\) 退化为严格新颖，\(\gamma=0\) 为无新颖性限制）。为了在放宽尾部精确率时既能穷尽未知字符串又不破坏 \(\widehat{\pi}_*(T, \boldsymbol{G}) = 1\) 和 \(\gamma\)-新颖性，本文设计了“探索集”（Exploration Set，Definition 4.1）\(R \subset \mathbb{N}\)：要求 \(R\) 为无限集、\(1 \notin R\)、不包含任何两个连续整数，且前 \(m\) 步中的探索轮次数 \(r(m) = |R \cap \{1, \dots, m\}|\) 满足渐近稀疏性 \(\lim_{m\to\infty} r(m)/m = 0\)（典型构造如 \(R = \{2^i : i \in \mathbb{N}\}\)）。针对 \(\gamma \in [0, 1)\) 的情形，由于探索轮次可能输出已被对抗者暴露的非新颖串，仅靠渐近稀疏不足以保证每个有限前缀 \(G_n\) 都满足 \(|N_n|/|G_n| \ge \gamma\)；为此本文进一步定义“\(\gamma\)-可容许探索集”（\(\gamma\)-admissible Exploration Set，Definition 4.2），额外强制在每一个有限时间步 \(m \in \mathbb{N}\) 都满足前缀密度上界 \(r(m) \le (1-\gamma)m\)。Lemma I.1 给出了显式构造：取整数 \(M \ge \max\{2, \lceil 1/(1-\gamma) \rceil\}\) 并令 \(R = \{M 2^i : i \in \mathbb{N}_0\}\)，即可同时满足无连续整数、渐近频率归零以及任意时刻非新颖探索占比不超过 \(1-\gamma\)。

3. \(k\)-批量安全 Pods 生成与探索交替机制：结合 2-批量安全池化与全空间枚举突破召回瓶颈

当生成器在时间步 \(m \notin R\) 执行安全生成例程、在 \(m \in R\) 暂停安全例程并执行探索时，由于 \(R\) 中无连续整数，两次相邻安全轮次之间最多夹杂一次探索轮次，这意味着单步对抗者在安全例程视角下最多连续暴露 2 个新字符串。为此，本文首先将 Kleinberg and Wei (2025b) 的 Pods 算法推广至“\(k\)-批量对抗设置”（\(k\)-batched adversarial setting，对抗者每步最多暴露 \(k\) 个串，生成器每步输出 1 个串，见 Algorithm 2 与 Lemma 4.5）：在每个安全步 \(n\)，算法筛选包含当前所有已暴露集合 \(A_m\) 的一致假设序列 \((S_i^{(n)})_{i \ge 1}\)，构造递减交集链 \(C_n = (\mathcal{I}_i^{(n)} = \bigcap_{j \le i} S_j^{(n)})_{i \ge 1}\)（Algorithm 3）；通过 IdIntersect（Algorithm 4）在链上自适应下探或回退至最大公共无限前缀，选出在有限步后必定满足最终有效（\(\mathcal{I}^{(n)} \subseteq T\)）、跨轮次可比且无限次包含完整 \(A\) 的“识别交集” \(\mathcal{I}^{(n)}\)；再由 AggrSet（Algorithm 5）在 \(\mathcal{I}^{(n)}\) 临时收缩时回退选取更大的“激进集” \(\widetilde{\mathcal{I}}^{(n)} \in \{\mathcal{I}^{(n)}, \mathcal{I}^{(n-1)}\}\)；随后从 \(\widetilde{\mathcal{I}}^{(n)}\) 中剔除已用集合 \(U_n\)，按字典序 \(\prec\) 取出前 \(s_n\) 个最小未用串组成当前分舱 \(P_n\) 并汇入全局分舱池 \(\mathcal{P}_n = \mathcal{P}_{n-1} \cup P_n\)，最后输出池中最小的未用串 \(\min_\prec(\mathcal{P}_n \setminus (A_m \cup G_{m-1}))\)。通过两步计费证明（Charging Argument，将漏掉的对抗串与池中积压串按最多 \(k:1\) 的重数映射到已输出串），本文在 Lemma 4.5 & 4.6 中证明了 \(k\)-批量下安全算法能达到紧致的 \(\frac{1}{k+1} \widehat{\rho}_*(\boldsymbol{T}, A)\) 召回率下界（在 \(k=2\) 时即提供 \(\alpha/3\) 的保底召回率）。

在此基础上，本文针对三种设置设计了具体的交替生成算法： 1. 严格新颖 + 允许无限次幻觉（Algorithm 6，\(\gamma=1, \widehat{\tau}_* = 0\)）：在 \(m \notin R\) 运行上述 2-批量安全 Pods 例程（贡献至少 \(\alpha/3\) 召回率，且有限步后仅输出 \(T\) 内合法串）；在 \(m \in R\) 按固定枚举 \(\boldsymbol{E}\) 遍历 \(\Sigma^*\)，跳过已在 \(A_m \cup G_{m-1}\) 中见过的字符串并输出第一个未见串 \(\Delta E_j\)。由于凡是未被对抗者暴露的目标串（\(x \in T \setminus A\)）永远不会被 \(A_m\) 封锁，无限次探索必然穷尽整个 \(T \setminus A\)，由 Lemma 4.7 直接贡献至少 \(1 - \widehat{\rho}^*(\boldsymbol{T}, A) \ge 1 - \beta\) 的召回率；同时因探索次数 \(r(n)/n \to 0\)，可能产生的无限次幻觉被完全稀释，从而实现 \(\widehat{\pi}_*(T, \boldsymbol{G}) = 1\) 与 \(\widehat{\rho}_*(\boldsymbol{T}, G) \ge \max(1 - \beta, \alpha/3)\)（Theorem 4.8）。 2. \(\gamma\)-新颖 + 允许无限次幻觉（Algorithm 7，\(\gamma \in [0, 1), \widehat{\tau}_* = 0\)）：采用 \(\gamma\)-可容许探索集 \(R\)，且在探索轮次 \(m \in R\) 遍历 \(\Sigma^*\) 的枚举 \(\boldsymbol{E}\) 时，仅跳过已生成集合 \(G_{m-1}\) 而不再跳过对抗者已暴露的 \(A_m\)。这一改动使得探索轮次最终能将 \(\Sigma^*\)（进而整个目标语言 \(T\)）完整纳入 \(G\)，实现完美召回率 \(\widehat{\rho}_*(\boldsymbol{T}, G) = 1\)；而只在探索轮次可能发生的非新颖输出被 \(r(n) \le (1-\gamma)n\) 严格控制在 \(1-\gamma\) 配额内（Theorem 4.9）。 3. \(\gamma\)-新颖 + 完美尾部精确率（Algorithm 8，\(\gamma \in [0, 1), \widehat{\tau}_* = 1\)）：当不允许无限次幻觉时，不能盲目枚举 \(\Sigma^*\)。算法将时间划分为长度为 \(L = \lceil \frac{1}{1-\gamma} \rceil\) 的分块，每个分块前 \(L-1\) 步运行 2-批量安全 Pods 例程，最后 1 步（当 \(m \equiv 0 \pmod L\) 且 \(A_m \setminus G_{m-1} \neq \emptyset\) 时）作为“重复轮次”直接输出对抗者已暴露但尚未生成的最小串 \(\min_\prec(A_m \setminus G_{m-1})\)。因为 \(A \subseteq T\)，重复轮次永不产生幻觉（保持 \(\widehat{\tau}_*(T, \boldsymbol{G}) = 1\)），且每 \(L\) 步最多 1 次重复严格满足 \(\gamma\)-新颖性，同时确保最终回收全部 \(A\)，将召回率从 \(\alpha/2\) 翻倍提升至紧致的 \(\alpha\)（Theorem I.3）。

实验关键数据

本文是一篇纯理论计算机科学（形式语言学习理论）论文，全文通过严格的数学定理、构造性算法与对抗下界证明来展示结论，不包含经验数据集或神经网络数值实验。以下根据原文 Figure 1 及第 2–4 节与附录 E–I 的全部核心定理，整理各约束设置下的理论界对比表与算法机制消融分析表。

主实验

下表汇总了本文与基线工作（Kleinberg and Wei, 2025b，简称 KW25b）在不同新颖性约束（\(\gamma\)）、尾部精确率约束（\(\widehat{\tau}_*\)，对应是否允许无限次幻觉）以及对抗穷举完整度（部分暴露 \(A \subsetneq T\)，满足 \(\widehat{\rho}_*(\boldsymbol{T}, A) \ge \alpha, \widehat{\rho}^*(\boldsymbol{T}, A) \le \beta\)；完全暴露 \(A = T\)，即 \(\alpha = \beta = 1\)）下的渐近精确率 \(\widehat{\pi}_*(T, \boldsymbol{G})\) 与下召回率 \(\widehat{\rho}_*(\boldsymbol{T}, G)\) 保证（对应原文 Figure 1）：

新颖性设置 尾部精确率约束 对抗暴露模式 下召回率保证 \(\widehat{\rho}_*(\boldsymbol{T}, G)\) 全局精确率保证 \(\widehat{\pi}_*(T, \boldsymbol{G})\) 对应定理 / 算法来源
无新颖性约束 (\(\gamma = 0\)) 完美尾部精确率 (\(\widehat{\tau}_* = 1\)，有限次幻觉) 部分穷举 (\(A \subsetneq T\)) / 完全穷举 (\(A = T\)) \(\ge \alpha\)（紧致界）/ \(= 1\) \(= 1\) Theorem E.1（直接复述对抗者 \(\Delta A_n\)）
无新颖性约束 (\(\gamma = 0\)) 放宽尾部精确率 (\(\widehat{\tau}_* \ge 0\)，允许无限幻觉) 部分穷举 (\(A \subsetneq T\)) / 完全穷举 (\(A = T\)) \(= 1\) / \(= 1\) \(= 1\) Theorem 4.3 (Algorithm 1，\(f\)-有界通用)
\(\gamma\)-新颖性松弛 (\(\gamma \in [0, 1)\)) 完美尾部精确率 (\(\widehat{\tau}_* = 1\)，有限次幻觉) 部分穷举 (\(A \subsetneq T\)) / 完全穷举 (\(A = T\)) \(\ge \alpha\)（紧致界）/ \(= 1\) \(= 1\) Theorem I.3 & Corollary I.4 (Algorithm 8)
\(\gamma\)-新颖性松弛 (\(\gamma \in [0, 1)\)) 放宽尾部精确率 (\(\widehat{\tau}_* \ge 0\)，允许无限幻觉) 部分穷举 (\(A \subsetneq T\)) / 完全穷举 (\(A = T\)) \(= 1\) / \(= 1\) \(= 1\) Theorem 4.9 & Corollary I.2 (Algorithm 7)
严格新颖性 (\(\gamma = 1\)) 完美尾部精确率 (\(\widehat{\tau}_* = 1\)，有限次幻觉) 单步部分穷举 / 单步完全穷举 \(\ge \frac{\alpha}{2}\)（紧致界）/ \(\ge \frac{1}{2}\) \(= 1\) KW25b Theorem 3.5 & 3.6 (Algorithm 2, \(k=1\))
严格新颖性 (\(\gamma = 1\)) 完美尾部精确率 (\(\widehat{\tau}_* = 1\)，有限次幻觉) \(k\)-批量对抗穷举 (\(k \ge 2\)) \(\ge \frac{\alpha}{k+1}\)（最坏情况最优上界匹配） \(= 1\) 本文 Lemma 4.5 & Lemma 4.6 (Algorithm 2)
严格新颖性 (\(\gamma = 1\)) 放宽尾部精确率 (\(\widehat{\tau}_* \ge 0\)，允许无限幻觉) 单步部分穷举 (\(A \subsetneq T\)) \(\ge \max\left(1 - \beta, \frac{\alpha}{3}\right)\) \(= 1\) 本文 Theorem 4.8 (Algorithm 6)
严格新颖性 (\(\gamma = 1\)) 放宽尾部精确率 (\(\widehat{\tau}_* \ge 0\)，允许无限幻觉) 单步完全穷举 (\(A = T, \alpha=\beta=1\)) \(\ge \frac{1}{2}\)（退化回 KW25b，无法进一步提升） \(= 1\) Section 4.2 结论 & Theorem 3.5

消融实验

下表对本文核心算法组件（稀疏探索轮次、2-批量安全 Pods 例程、探索时是否跳过对抗串 \(A_m\)、周期性重复轮次）在不同设置下的作用进行机制拆解与理论对比：

算法变体 / 组件配置 新颖性 \(\gamma\) 尾部精确率 \(\widehat{\tau}_*\) 召回率下界 \(\widehat{\rho}_*(\boldsymbol{T}, G)\) 组件作用与理论机制说明
仅单步安全 Pods 例程 (KW25b Baseline) \(\gamma = 1\) \(= 1\) \(\frac{\alpha}{2}\) 无探索轮次；受限于必须对所有候选子语言 \(A \in \mathcal{T}\) 保持最终有效，无法输出 \(T \setminus A\)，当 \(\alpha \to 0\) 时召回率趋于 0
仅 \(k\)-批量安全 Pods 例程 (Lemma 4.5) \(\gamma = 1\) \(= 1\) \(\frac{\alpha}{k+1}\)（\(k=2\) 时为 \(\frac{\alpha}{3}\)） 为插入探索/重复轮次提供缓冲底座；对抗者每步暴露 \(k\) 串使每个 Pod 索引最多承受 \(k\) 次计费，召回分母由 2 变为 \(k+1\)
仅稀疏探索轮次 (\(T \setminus A\) 覆盖分支, Lemma 4.7) \(\gamma = 1\) \(= 0\) \(1 - \beta\) 遍历 \(\Sigma^* \setminus (A_m \cup G_{m-1})\) 穷尽所有对抗者未暴露的串；若无安全轮次稀释错误，则全局精确率 \(\widehat{\pi}_*\) 将退化崩溃
Algorithm 6：2-批量安全 Pods + 跳过 \(A_m\) 的探索 \(\gamma = 1\) \(= 0\)（一般情况） \(\max\left(1 - \beta, \frac{\alpha}{3}\right)\) 完整严格新颖模型；当 \(\beta < 1 - \frac{\alpha}{3}\)（例如 \(\alpha=\beta < 0.6\)）时严格优于 KW25b 的 \(\frac{\alpha}{2}\)，在 \(\alpha,\beta \to 0\) 时召回率趋近于 1
Algorithm 7：2-批量安全 Pods + 不跳过 \(A_m\) 的 \(\gamma\)-可容许探索 \(\gamma \in [0, 1)\) \(= 0\)（一般情况） \(1\) 将探索过滤条件从 \(E_j \subseteq A_m \cup G_{m-1}\) 放宽为 \(E_j \subseteq G_{m-1}\)，用至多 \((1-\gamma)\) 比例的非新颖配额换取对 \(\Sigma^*\) 的全覆盖
Algorithm 8：2-批量安全 Pods + 周期 \(L=\lceil \frac{1}{1-\gamma} \rceil\) 重复轮次 \(\gamma \in [0, 1)\) \(= 1\) \(\alpha\) 用周期性复述 \(\min_\prec(A_m \setminus G_{m-1})\) 替代盲目探索，在不产生任何额外幻觉的前提下完全消除对抗者的“偷串”损失

关键发现

  • 稀疏幻觉在对抗者隐瞒数据时的显著收益：在严格新颖性（\(\gamma=1\)）下，若要求完美尾部精确率（零最终幻觉），当对抗者仅暴露极小比例的目标语言（\(\alpha, \beta \to 0\)）时，任何算法的召回率上限均为 \(\alpha/2 \to 0\)（因算法无法区分真实目标究竟是 \(T\) 还是子集 \(A\)，不敢迈出 \(A\) 半步）。而本文 Algorithm 6 允许在渐近密度为 0 的探索集 \(R\) 上盲目枚举 \(\Sigma^*\)，虽然产生了无限次幻觉（\(\widehat{\tau}_* = 0\)），但全局精确率依然锁定为 \(\widehat{\pi}_* = 1\)，且召回率达到 \(\max(1-\beta, \alpha/3) \to 1\)，实现了从 0 到 1 的质的飞跃。
  • 两分支召回率不可直接相加的本质原因：在 Theorem 4.8 中，探索轮次保证了至少 \(1-\beta\) 的召回率（覆盖 \(T \setminus A\)），2-批量安全轮次保证了至少 \(\alpha/3\) 的召回率，但总召回率是 \(\max(1-\beta, \alpha/3)\) 而非二者之和。原因在于安全 Pods 例程仅保证生成串属于 \(T\)，并不保证其属于 \(A\)；在极端情况下，安全轮次与探索轮次生成的有效串可能全部落在 \(T \setminus A\) 中而完全重叠。
  • 任意微小的非新颖配额（\(\gamma < 1\)）即可引发相变：只要将严格新颖性 \(\gamma = 1\) 略微放宽至任意固定的 \(\gamma \in [0, 1)\)（哪怕要求 \(99.9\%\) 的输出必须是新颖串），极限生成的难度便发生根本性下降——在要求零最终幻觉（\(\widehat{\tau}_* = 1\)）时，Algorithm 8 可借由每 \(L = \lceil 1/(1-\gamma) \rceil\) 步一次的合法复述将召回率从 \(\alpha/2\) 提升至紧致的 \(\alpha\)；若同时允许渐近消失的无限次幻觉，Algorithm 7 更能对任意部分对抗穷举同时实现 \(\widehat{\rho}_*(\boldsymbol{T}, G) = 1\) 与 \(\widehat{\pi}_*(T, \boldsymbol{G}) = 1\)。

亮点与洞察

  • 基于上确界消除穷举依赖的精确率/召回率对偶构造：针对无限集合上无法直接定义基数比值且固定穷举前缀会导致评估偏置的问题，本文巧妙地通过固定一端穷举、对另一端所有合法穷举取上确界（\(\sup_{\boldsymbol{T} \in \mathcal{E}_f(T)}\) 与 \(\sup_{\boldsymbol{G} \in \mathcal{E}(G)}\)），并证明其精确退化为单侧无限集合交集的极限下确界（Theorem 2.1 与 Lemma 2.2）。这一数学技巧既避开了在 \(\Sigma^*\) 上强行假设先验概率分布，又把现有文献孤立的“覆盖密度”无缝纳入了经典的 Precision-Recall 对偶框架。
  • 区分“全局精确率为 1”与“尾部精确率为 1”的理论洞见：本文最让人“啊哈”的地方在于指出“渐近精确率等于 1”（错误率趋于 0）绝不等价于“最终不犯错”（Eventual Validity）。通过单步增量比值的下极限定义尾部精确率 \(\widehat{\tau}_*\)，作者清晰地证明了单步生成下“最终有效”等价于 \(\widehat{\tau}_*\) 在有限步稳定到 1；而一旦允许 \(\widehat{\tau}_* = 0\) 并利用密度趋于 0 的探索集 \(R\)（如 2 的幂次步）穿插盲探，就能用“无限个但占比无穷小的幻觉”换取对对抗者永久隐瞒区域的完全覆盖。
  • 可迁移至在线学习与安全探索任务的 \(\gamma\)-可容许调度与批量缓冲思想：本文将稀疏探索轮次插入确定性安全算法时，将探索轮次导致的“安全步暂停”建模为虚拟的 2-批量对抗输入，并用 \(\gamma\)-可容许集 \(R = \{M 2^i\}\) 严格锁定任意有限时刻的探索预算上限。这种“用 \(k\)-批量鲁棒性吸收探索停顿 + 用几何级数前缀界控制任意时刻违规率”的组合范式，可直接迁移至带安全约束的在线强化学习、流式主动学习以及受控投机解码（Speculative Decoding）的理论分析中。

局限与展望

  • 完全对抗穷举且严格新颖时仍受困于 \(1/3\) 与 \(1/2\) 鸿沟：作者在第 4.2 节末尾指出，当 \(\gamma=1\) 且对抗者提供完整穷举（\(\alpha=\beta=1\)）时，Algorithm 6 给出的召回率保证为 \(\max(1-1, 1/3) = 1/3\)，反而不如直接运行不带探索的原始 KW25b 算法（召回率 \(1/2\)）。这是因为插入探索轮次迫使安全例程面对 2-批量对抗，使其保底系数从 \(1/2\) 降为 \(1/3\)，而此时 \(T \setminus A = \emptyset\) 使探索轮次毫无增量贡献；如何在不预知 \(\alpha, \beta\) 的情况下自适应避免这一常数折损仍有待解决。
  • 盲目字典序枚举 \(\Sigma^*\) 的计算与现实距离：在探索轮次中，Algorithm 1、6、7 直接按照 \(\Sigma^*\) 的固定枚举 \(\boldsymbol{E}\) 逐个输出字符串来兜底覆盖 \(T \setminus A\)。尽管理论上在无穷极限下能够遍历所有目标串并维持渐近精确率为 1，但在有限时间步内，从 \(\Sigma^*\) 中盲目枚举极易输出大量毫无意义的乱码幻觉，且未利用任何已学习的语言结构先验（如当前一致假设集 \(\bigcup S_i^{(n)}\)）。
  • 未来改进方向：一个极具价值的推进方向是设计“假设引导的受控探索（Hypothesis-Guided Exploration）”——在探索轮次中不再盲目遍历整个 \(\Sigma^*\)，而是从一致交集链 \(C_n\) 的较浅层（即包含更多候选语言、虽未验证绝对安全但比 \(\Sigma^*\) 精确得多的并集或浅层交集 \(\mathcal{I}_1^{(n)}\)）中进行采样，并结合在线估计的对抗暴露速率动态调整探索集 \(R\) 的稀疏度，从而在保持完美渐近精确率的同时加快有限步内的有效召回收敛速度。

相关工作与启发

  • vs Kleinberg and Mullainathan (2024) [Language generation in the limit]: 他们开创了极限语言生成范式，证明了对于任意可数无限语言族都存在满足严格新颖性与最终有效性（有限步后零幻觉）的生成算法，但完全忽略了生成集合对目标语言的覆盖度（召回率可能任意趋近于 0）；本文则通过引入基于穷举的精确率、召回率与尾部精确率，揭示了其“最终有效性”本质上是要求尾部精确率在有限步稳定至 1，并证明放宽该要求可大幅提升稀疏数据下的覆盖率。
  • vs Kleinberg and Wei (2025a, 2025b) [Density measures & Partial enumeration]: 他们提出了沿固定目标枚举评估的密度度量，并设计了基于识别交集与分舱池（Pods）的生成算法，在单步部分穷举（密度 \(\alpha\)）和严格新颖、零最终幻觉下取得了 \(\alpha/2\) 的最优密度界；本文不仅将其密度推广为跨穷举上确界的覆盖召回率、补齐了对偶的成员精确率度量，还在技术上将 Pods 算法推广至 \(k\)-批量对抗设置（证明了紧致的 \(\frac{\alpha}{k+1}\) 界），进而结合稀疏探索集与 \(\gamma\)-新颖性松弛突破了 \(\alpha/2\) 的理论天花板。
  • vs Kalavasis et al. (2025) & Charikar and Pabbaraju (2025): 他们从不可能定理的角度证明了在要求零最终幻觉时，追求完整覆盖度（广度）会退化为不可行的极限语言识别问题；本文则给出了积极的破局路径——证明只要容忍发生率趋于 0 的无限次幻觉，或者容忍任意微小固定比例（\(1-\gamma > 0\)）的非新颖重复输出，就能绕过这一不可能定理，在极限下同时实现精确率 1 与召回率 1。

评分

  • 新颖性: ⭐⭐⭐⭐⭐ 将极限生成形式化为无穷集上的 Precision-Recall 与尾部精确率框架，打破了“必须有限步后零幻觉”与“100% 严格新颖”的思维定式，概念创新极为深刻。
  • 实验充分度: ⭐⭐⭐⭐ 纯理论工作无数值实验，但全面覆盖了 \(\gamma=0, \gamma \in (0,1), \gamma=1\)、完全/部分穷举、完美/松弛尾部精确率组成的全谱系矩阵，且给出了匹配的上下界证明。
  • 写作质量: ⭐⭐⭐⭐⭐ 定义严谨、符号体系清晰，正文通过直观的 Proof Sketch 与总览图（Figure 1）串联主线，复杂的计费证明与构造细节完整收纳于附录，可读性极佳。
  • 价值: ⭐⭐⭐⭐ 为理解现代大语言模型中“幻觉不可避免但可通过控制错误率换取覆盖广度”以及“适度复述训练数据对覆盖率的关键作用”提供了坚实的理论计算机科学支撑。

相关论文