📊 statistics

Exponential Sample Complexity Separation between Flat and Hierarchical Agentic Theorem Provers

本文表明，层次化定理证明器通过从教师轨迹中学习可复用的证明结构，避免了扁平化表示中固有的困难子证明的冗余重复，从而相比扁平化证明器实现了样本复杂度的指数级降低。

原作者： Sho Sonoda, Shunta Akiyama, Yuya Uezato

发布于 2026-05-11

📖 1 分钟阅读☕ 轻松阅读

原作者： Sho Sonoda, Shunta Akiyama, Yuya Uezato

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

想象一下，你正在教一名学生如何解一个非常复杂的谜题，比如一个巨大的拼图或一道难题。目标是让学生在有限的时间和精力内，尽可能快速高效地找到解决方案。

这篇论文提出了一个简单的问题：是教学生每次都从头开始解决整个谜题更好，还是教他们识别并复用那些已经解决的小块拼图更好？

作者认为，教学生复用小块（分层方法），比强迫他们**每次都从头解决每一个微小步骤（扁平方法）**要高效得多，其效率呈指数级提升，即使这些“小块”本身也很难搞懂。

以下是使用日常类比进行的分解说明：

1. 两种学习方式

“扁平”学生（勤奋者）
想象一名学生拿到了一份大型宴会的食谱。每当食谱要求“制作酱汁”时，这名学生都必须从零开始：切洋葱、剥蒜、炖番茄，然后全部混合。即使食谱要求制作十次酱汁，这名学生也会制作十批独立的酱汁，切十次洋葱。

在论文中： 这代表一种“扁平”证明器。它将整个证明视为一条长长的、直线的步骤序列。如果某个特定的逻辑论证（如引理）需要五次，学生就必须学习并执行这五个步骤五次，每次都是独立的。

“分层”学生（聪明的组织者）
现在想象一名更聪明的学生。当他们看到“制作酱汁”时，会意识到：“我以前做过这个！”他们会记下一条笔记：“酱汁食谱：切、剥、炖。”下次食谱再次需要酱汁时，他们只需说“使用酱汁食谱”，而无需再次切洋葱。他们建立了一个可复用的“模块”（引理）库。

在论文中： 这代表一种“分层”证明器。它将问题分解为一张地图（DAG，即有向无环图），其中共享的部分只需解决一次，然后被多次引用。

2. 核心发现：“指数级”差距

论文的主要发现涉及样本复杂度。简单来说，这意味着：“学生需要学习多少示例才能熟练掌握这项任务？”

作者证明，如果一个问题需要多次复用某个困难的子步骤，那么“扁平”学生在训练数据中需要看到的该困难步骤的重复次数，要比“分层”学生多指数级的倍数。

图书馆的类比：

扁平学生： 要学习写一本引用了某首名诗 1000 次的书，这名学生必须把整本书读 1000 遍，每次都要背诵那 10 行诗。他们需要一座巨大的图书馆来学习这个。
分层学生： 这名学生只读一遍书。他们只一次背诵那 10 行诗，并将它们放入一个“引用框”中。当需要再次引用时，只需指向那个框。他们只需要一个极小的图书馆就能学会同样的东西。

论文表明，如果这首“诗”（即困难的子证明）很难，扁平学生可能需要数百万个示例来学习，而分层学生可能只需要几十个。这种差异不仅仅是稍微大一点，而是指数级的差距。

3. 为什么会发生这种情况？

作者使用**MDP（马尔可夫决策过程）**这一概念对此进行了建模，这仅仅是一种描述具有规则、状态和移动的游戏的复杂方式。

教师： 一个完美的求解器，向学生展示成功的证明。
数据： 学生通过观察这些成功的证明来学习。
问题： 如果教师的证明使用了一个巧妙的捷径（引理）五次，那么数据的“扁平”视图看起来就像五条独立的、漫长且艰难的路径。学生必须学习这五条独立的路径。
解决方案： “分层”视图则看到，这五条路径实际上只是同一条路径的重复。学生只需要学习这一条路径。

论文提供了数学公式（界限）来证明：分层学生所需的训练示例数量保持在一个较小的水平，而扁平学生所需的数量则随着问题深度的增加而呈爆炸式增长。

4. 这对 AI 定理证明器的意义

这篇论文专注于代理定理证明器——即试图证明数学定理的 AI 系统。这些系统通常尝试将大问题分解为更小的“子目标”或“引理”。

怀疑论者的观点： “为什么要费劲分解？证明那个小引理很难。为什么要浪费时间在上面？”
论文的回答： “因为如果你不分解并复用解决方案，你就不得不一遍又一遍地解决同一个难题。‘浪费’一次去解决引理，实际上比解决它一千次要节省得多。”

总结

这就好比盖房子：

扁平方法： 你通过一块一块地砌砖来盖房子，即使你需要建造相同的墙面图案 100 次。你需要堆积如山的砖块和大量的时间。
分层方法： 你只建造一次“墙体模块”。然后，你只需将这个预制模块堆叠 100 次。你需要的原材料和时间要少得多。

论文从数学上证明，对于复杂问题，“模块”方法（分层）所需的训练示例数量，比“一块砖一块砖”的方法（扁平）要少指数级。这解释了为什么现代使用“引理”和“子目标”的 AI 定理证明器，在统计上比那些试图用一条长长的扁平直线解决所有问题的证明器更高效。

标题： 扁平化与分层智能体定理证明器之间指数级的样本复杂度分离

作者： Sho Sonoda, Shunta Akiyama, Yuya Uezato
所属机构： CyberAgent, RIKEN AIP
日期： 2026 年 5 月 7 日

1. 问题陈述

近期的智能体定理证明器通常采用分解策略——例如生成中间引理、证明草图或子目标分解——然后再进行战术级搜索。虽然经典证明论表明引理可以缩短推导过程，但发现和证明这些中间步骤的统计学习成本仍然是一个未解之谜。具体而言，如果证明一个引理本身就很困难，那么一个学习到的证明器为何要为此付出努力？

本文探讨了这样一个统计学习问题：与从完全内联的证明轨迹（扁平化）中学习相比，学习可重用的证明结构（分层化）是否能在固定的搜索预算下提高找到已验证证明的概率。作者关注的是由“教师”证明器诱导的数据分布，该分布包含初始定理状态和成功的已验证证明轨迹，而非所有公式的最坏情况证明复杂度。

2. 方法论

作者将定理证明建模为一个确定性有限时域马尔可夫决策过程（MDP），其中状态是证明状态，动作是战术、推理规则或高层分解动作。他们在三种不同的设置下，分析了从成功的教师轨迹中进行的离线模仿学习：

设置 1（扁平化）： 教师生成完全内联的低级证明轨迹。学生模仿这些轨迹，不进行图预测或记忆化。重复的子证明在训练和测试数据中表现为独立的、复制的实例。
设置 2（分层化）： 教师构建一个高层证明有向无环图（DAG），其中节点代表可重用的证明块。学生学习一个图预测器以及用于高层图动作（选择、扩展、重用块）和低级局部求解的策略。训练数据由内联轨迹组成，要求学生推断潜在的证明 DAG 结构。
设置 3（比较）： 扁平化学生和分层化学生都在由分层教师生成的相同源数据（内联轨迹）上进行训练。扁平化学生丢弃潜在的图结构，而分层化学生则推断该结构。该设置隔离了表示形式对样本复杂度的影响。

分析依赖于三个关键量：

$L$ （平均长度）： 成功证明中的决策平均数量。
$\eta$ （内在搜索损失）： 由于教师的下一个动作不在学生的前 $k$ 个候选列表中而损失的概率质量（局部可预测性）。
$e$ （模仿误差）： 学生策略与教师策略之间的 Kullback-Leibler (KL) 散度。

作者假设了 Tsybakov 类型的边界条件，将模仿误差转化为前 $k$ 个遗漏概率，并假设如果教师的动作包含在学生的前 $k$ 个列表中，则搜索是完备的。

3. 主要贡献

形式化： 本文将验证器引导的定理证明形式化为有限时域 MDP，并将“统计可证性”定义为在初始状态分布上，在预算内找到已验证证明的平均概率。
成功保证： 作者推导了扁平化学生（在内联轨迹上训练）和分层学生（在预测可重用 DAG 上训练）的有限样本成功界限。这些界限明确区分了决策数量、内在前 $k$ 损失和学到的排序误差。
指数级分离： 主要的理论结果是充分样本复杂度的指数级分离。当可重用的证明 DAG 被展平为树时，相同的子证明会被指数级地重复。本文证明，即使在同一数据源上训练，分层学习者的充分样本证书也可以比扁平化学习者的指数级小。
潜在图学习： 本文提供了分层学生的学习率，该学生必须使用 EM 风格的后验加权方法从内联轨迹中推断潜在证明 DAG，同时考虑图预测误差和后验不匹配。

4. 结果

核心结果在定理 6中提出，该定理比较了扁平化学生和分层学生达到目标失败水平 $\delta$ 所需的认证充分样本计数（ $\bar{N}$ ）。

扁平化界限： $\bar{N}_{flat}(\delta) \propto (L_{flat}/\delta)^{1/(p\gamma)}$
分层化界限： $\bar{N}_{hier}(\delta) \propto \max(L_{hi}, L_{lo}/\delta)^{1/(p\gamma)}$

其中 $L_{flat}$ 是展开轨迹的长度， $L_{hier} = L_{hi} + L_{lo}$ 是分层表示的长度。

本文表明，对于由大小/深度参数 $D$ 索引的一类定理，如果展平过程导致证明长度呈指数增长（ $L_{flat}/L_{hier} = \exp(\Omega(D))$ ），那么所需样本的比例也会呈指数增长：
$\bar{N}_{flat}(\delta) / \bar{N}_{hier}(\delta) \geq \exp(\Omega(D))$

这种分离产生的原因是，扁平化学习者必须为每一次出现独立地学习相同的困难局部论证，而分层学习者只需学习一次共享块并重复使用它。本文使用了一个割消示例（附录 G）来说明，移除中间引理（展平）如何导致证明规模呈指数级爆炸，从而增加扁平化学习者的样本复杂度。

5. 意义与主张

本文声称提供了一种具体的统计机制来解释为何分层证明是有益的，这不同于最坏情况证明复杂度的论证。其意义在于指出，分解的好处不仅仅在于缩短逻辑推导，更在于减轻学习者的统计负担。

数据分布意识： 该结果强调，学习效率取决于数据分布的结构。如果成功的证明重用了中间论证，那么分层表示能够捕捉这种共享，而扁平化表示则会破坏这种共享，导致冗余的学习任务。
局限性： 作者对其主张持谨慎态度。他们指出，这不是最坏情况的下界，也不排除那些可能实现完美规范化的扁平化学习者（在没有显式分层的情况下完美识别相同的子问题）。这种分离仅在展平破坏了可重用的证明结构，且数据分布包含此类共享普遍存在的证明时才成立。
实际意义： 研究结果表明，对于基于验证器的定理证明，学习预测可重用的证明结构（引理、子目标）可以指数级地降低达到给定成功概率所需的样本复杂度，前提是图预测器能够以高概率覆盖教师的证书。

本文得出结论，当这些引理可重用时，证明引理的“昂贵弯路”在统计上是合理的，因为一次性学习它们的成本远低于在扁平化框架中反复重新发现它们的成本。