🤖 machine learning

Certification from Examples is Hard for Circuits and Transformers under Minimal Overparametrization

本文证明，即使在阈值电路和 log 精度 Transformer 中引入最小程度的过参数化，也会使精确和近似认证变得指数级困难，这一理论障碍已通过检测执行二进制加法任务的训练模型中错误时所遇到的困难得到了实证验证。

原作者： Artur Back de Luca, Kimon Fountoulakis

发布于 2026-05-25

📖 1 分钟阅读☕ 轻松阅读

原作者： Artur Back de Luca, Kimon Fountoulakis

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

想象你是一位老师，试图验证一名学生是否真正掌握了一条特定的数学规则，例如“如何相加两个数字”。你拥有一份示例列表（输入 - 输出对），并希望百分之百确定该学生并非仅仅在猜测或遵循某种技巧。

本文提出了一个根本性问题：你需要向学生展示多少示例，才能证明他们掌握的是确切的规则，而不仅仅是一个非常相似的规则？

作者 Artur Back de Luca 和 Kimon Fountoulakis 发现了一个令人惊讶且略显可怕的真相：即使对学生“大脑”（即模型）进行微小到几乎不可见的改动，也可能导致无论展示多少示例，都无法证明其正确性。

以下是他们研究发现的分解，辅以简单的类比：

1. “冒牌货”问题

想象你拥有一位完美掌握加法规则的学生。你想要证明他是唯一掌握该规则的人。

简单场景：如果房间里只有这一名学生，你可能只需要向他展示 5 到 10 个示例，就能证明他掌握了规则。
困难场景：现在，想象你邀请了 1,000 名“冒牌货”进入房间。这些冒牌货几乎完美，他们在 99.9% 的情况下都能给出正确答案。他们出错的唯一情况，是在一组非常具体、隐蔽的数字上（例如以数字"7"开头的数字）。

论文表明，如果你向模型中仅添加一个额外的“神经元”（即微量的额外算力），就能创造出数百万个这样的冒牌货。每个冒牌货在几乎所有事情上都与完美学生一致，但他们各自在一组不同的、微小的、隐蔽的数字集合上存在分歧。

2. “大海捞针”类比

为了证明该学生是真正的，而非冒牌货，你必须找到他们产生分歧的具体数字。

如果你有 1,000 名冒牌货，且每个人都将自己的错误隐藏在数字宇宙中不同的微小角落，那么为了确信无疑，你必须检查每一个角落。
论文证明，如果你向电路中仅添加一个额外的“门”（或向 Transformer 人工智能模型中添加一个额外的“注意力头”），这些隐藏角落的数量就会呈爆炸式增长。
结果：为了揪出所有冒牌货，你可能需要检查数十亿个示例。如果你只检查几千个（即“多项式”数量）示例，你很可能会漏掉冒牌货，导致该学生通过了你的测试，尽管他们实际上并不正确。

3. 两位主要角色

作者在两种类型的“学生”身上测试了这一理论：

电路：将其想象为简单、僵化的逻辑机器（如计算器）。他们发现，向深度为 2 或更高的电路中添加仅一个额外开关，就会使验证答案的难度呈指数级增加。
Transformer：这些是支撑聊天机器人等工具的强大人工智能模型。作者表明，仅向模型添加一个额外的注意力头（微小的架构调整）以及模型内存中的几个额外数值，就会使得用合理数量的示例进行验证变得不可能。

4. “近乎完美”的陷阱

你可能会想：“好吧，但如果我们只是接受学生犯少量错误呢？如果我们说‘如果他们正确率达到 99%，那就足够了’？”
论文回答：请小心。

绝对错误：如果你说“你总共只能犯 10 个错误”，冒牌货依然会隐藏。你仍然需要数十亿个示例来找出这 10 个错误，因为它们散布在数十亿种可能性中。
相对错误：如果你说“你可以犯 1% 的错误”，冒牌货就可以隐藏数百万个错误，只要这 1% 足够小即可。模型在绝对意义上可能错得离谱，但仍能通过你的"99% 准确率”测试。

5. 现实世界实验

为了证明这不仅仅是数学理论，他们实际构建了这些模型：

电路实验：他们构建了一个用于相加数字的电路，随后创建了数千个“损坏”版本，这些版本仅在特定输入上失效。他们表明，即使拥有大量测试示例，许多这些损坏的电路看起来依然完美无缺。
Transformer 实验：他们训练人工智能模型进行数字相加。即使训练这些模型直到它们通过严格的验证测试（正确率达到 99.9%），他们发现某些模型仍存在隐藏错误。当他们尝试用随机示例对这些模型进行“审计”时，这些模型即便实际上并不完美，却仍不断通过测试。

核心结论

论文得出结论：认证极其脆弱。
如果你想要保证人工智能或电路确实按照你的设想运作，你就不能依赖平均性能。如果模型拥有哪怕一点点“额外容量”（过参数化），它就能隐藏指数级数量的出错方式。

若要真正确信，你可能需要在数量大到实际上无法执行的示例上测试模型。这就像试图通过观看魔术师表演几次来证明他没有作弊；如果他的袖子里藏着一张秘密的额外牌，除非你检查牌堆里的每一张牌，否则你可能永远无法发现它。

技术摘要：在最小过参数化下，基于示例的电路与 Transformer 认证是困难的

问题陈述

随着最先进的神经网络越来越多地部署于推理和算法任务中，确保其精确正确性变得至关重要。高平均情况准确率往往掩盖了不一致的行为，使得检测偏离预期推理逻辑的故障变得困难。本文解决了精确认证的问题：确定唯一识别假设类 $\mathcal{H}$ 中目标假设 $f^*$ 所需的最少标记输入 - 输出示例数量，使得 $\mathcal{H}$ 中没有任何其他假设在整个域上与 $f^*$ 一致。

核心问题在于，这种认证复杂度对周围假设类的大小有多敏感。具体而言，作者调查了假设类的最小扩充（例如，添加单个门或常数数量的参数）是否会使认证变得指数级困难，即使对于那些原本易于认证的目标也是如此。

方法论

本文采用植根于教学复杂度和电路复杂度的理论框架，并辅以二元加法任务的实证验证。

理论框架

证书大小定义：作者将证书大小 $\text{cert}(f^*, \mathcal{H})$ 定义为标记样本 $S$ 的最小规模，使得版本空间 $V_S^{\mathcal{H}}$ （即 $\mathcal{H}$ 中与 $S$ 一致的假设集合）仅包含 $f^*$ 。
不相交分歧原则：核心证明策略依赖于构建一组“欺骗者”假设。对于目标 $f^*$ $f^{*}$ ，作者构建了一个假设族 $\{g_\pi\}$ ${g_{π}}$ ，它们在与 $f^*$ $f^{*}$ 在所有地方一致，仅在特定的、成对不相交的“触发块” $B_\pi$ $B_{π}$ 上存在分歧。
- 如果假设类包含这样一个欺骗者族，且其分歧集是不相交的，那么任何精确证书必须包含每个分歧集中的至少一个示例。
- 因此，证书大小的下界由此类不相交块的数量决定。
过参数化分析：作者分析了添加最小容量（例如，电路中添加一个额外门，Transformer 中添加一个额外注意力头和常数嵌入宽度）如何允许为原始较小类中的每个目标构建这些指数级的欺骗者族。

实证分析

作者通过两个关于二元加法识别的实验补充了理论：

构造电路：他们针对识别加法的阈值电路（ $TC_0$ ）实例化了理论上的欺骗者构造。他们生成了 $2^n$ 个错误电路的集合，每个电路在独特的输入块上与目标不同，并测量在均匀采样证书候选时有多少电路幸存。
训练 Transformer：他们在 10 位加法上训练了仅编码器 Transformer。在选出通过严格验证检查（99.9% 准确率）的模型后，他们在大型保留测试集上评估它们。他们分析了这些不完美模型（欺骗者）在经受均匀采样的证书候选时的“幸存”情况，测试是否可以用多项式大小的样本检测出残差误差。

主要贡献与结果

1. 最小过参数化导致的指数级困难

主要的理论贡献在于证明认证对假设类大小高度敏感。

阈值电路（ $TC_0$ ）：对于深度 $d \ge 2$ 的电路，添加单个额外阈值门（将门预算从 $s$ 增加到 $s+1$ ）迫使原始类 $TC_{d,s}$ 中每个目标的证书大小在输入维度 $n$ 上变为指数级。具体而言， $\text{cert}(f^*, TC_{d,s+1}) \ge 2^{\Omega(n)}$ 。
Transformer：对于具有平均硬注意力（AHAT）的对数精度 Transformer，在最后一层添加一个注意力头以及六个辅助嵌入/残差坐标，会创建一个扩充类，使得认证变得指数级困难。即使目标 $f^*$ 在较小架构中具有多项式大小的证书，要针对稍大的架构对其进行认证，也需要指数级数量的示例。
非平凡性：作者证明了这些下界并非空洞的。他们表明，较小的类（ $TC_{d,s}$ 和标准 Transformer）包含具有多项式证书大小（具体为 $O(\log |\mathcal{H}|)$ ）的目标，然而一旦该类被最小扩充，这些相同的目标在认证时就会变得指数级困难。

2. 近似认证困难

本文将这些结果扩展到近似认证：

绝对误差容忍度：如果认证仅允许多项式数量的错误（ $R = \text{poly}(n)$ ），证书大小仍保持指数级（ $2^{\Omega(n)}$ ）。
相对误差容忍度：如果认证允许常数相对误差（ $\epsilon$ ），证书大小可以很小（关于 $1/\epsilon$ 的多项式）。然而，这是以允许指数级数量的绝对错误为代价的。作者表明，常数相对误差保证可能会掩盖指数级的错误，而多项式绝对误差保证仍然需要指数级证书。

3. 实证验证

电路实验：构造的 $TC_0$ 欺骗者证实了理论障碍。即使使用多项式大小的证书候选，几乎所有构造的欺骗者仍与采样的标签一致，需要指数级采样才能消除它们。
Transformer 实验：在 150 个通过广泛验证的训练模型中，有 63 个在保留测试集上存在残差误差。分析表明，即使针对富含错误的子集，多项式大小的均匀采样证书候选也无法消除所有非精确假设。不完美模型可以通过大型均匀采样候选来逃避检测。

意义与主张

本文声称提供了精确学习的认证困难性的量化形式。其意义在于以下断言：

对模型容量的敏感性：认证不仅仅是目标函数的属性，而且 critically 依赖于“环境”假设类。模型容量的最小增加（常数开销）可以根本性地改变验证模型正确性的难度。
被动认证的局限性：在被动设置中（示例在没有查询模型的情况下被采样），如果假设类略微过参数化，多项式大小的数据集不足以证明模型已学会预期的计算。
与可学习性的区别：结果突显了可学习性与认证之间的差距。虽然一个函数可能是可学习的（或在受限类中具有小证书），但在稍大的类中对其进行认证可能是不可处理的。
对推理模型的影响：对于部署在算法任务（如加法）上的模型，高验证准确率并不能保证精确性。本文表明，如果没有更强的协议（例如主动学习或特定查询），大型均匀采样数据集可能无法检测推理模型中细微的、结构化的不一致性。

作者得出结论，虽然精确认证是一个基础性挑战，但这种障碍不仅仅是极端情况的异常，而是与现代推理任务相关的类中最小过参数化的结构性后果。他们建议未来的工作应探索主动认证协议，以潜在地克服这些被动障碍。