🤖 machine learning

Sketch-and-Verify: Structured Inference-Time Scaling via Program Sketching

本文介绍了“草图与验证”（Sketch-and-Verify），这是一种面向小型代码模型的成本效益型推理时扩展策略，它通过枚举多样化的算法草图并用多个候选方案填充这些草图，其表现优于扁平采样，尽管其性能尚无法完全取代更强大模型层级的表现。

原作者： Shan Jiang, Zijian Yi, Chenguang Zhu

发布于 2026-05-12

📖 1 分钟阅读☕ 轻松阅读

原作者： Shan Jiang, Zijian Yi, Chenguang Zhu

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

想象一下，你正试图解决一个棘手的谜题，但只有一台小型、廉价的机器人来协助你。这台机器人速度快且成本低，但它有个坏习惯：当它尝试解决问题时，几乎总是选择同一种错误的思维方式。如果你让它尝试 100 次，它只会给你 100 个略微不同的同一错误答案的变体。

这正是论文《草图与验证》（Sketch-and-Verify）试图解决的问题。它提供了一种新方法，让这台小型、廉价的机器人能够解决更多问题，而无需升级为超级昂贵的大型机器人。

以下是该方法的运作原理，分解为简单步骤：

1. 问题：“老调重弹”

通常，当我们要求 AI 编写代码时，我们只是说：“尝试 100 次，然后给我最好的那个。”

缺陷：如果 AI 的“默认”想法是错误的，让它尝试 100 次，就像要求一个人写出 100 个同一首糟糕歌曲的不同版本。你可能会改变歌词或节奏，但旋律仍然是错的。AI 会陷入“表面”变化的循环（例如更改变量名或格式），而从未尝试从根本上不同的方法。

2. 解决方案：“建筑师与建造者”

作者提出了一种名为草图与验证（Sketch-and-Verify）的两步流程。他们不是要求 AI 立即编写完整代码，而是将工作分为两个角色：

步骤 1：建筑师（草图）
首先，他们要求 AI 扮演建筑师的角色。他们说：“先不要写代码。只需列出 5 种完全不同的解决这个问题的方法。”
- 示例：“策略 A：使用映射。策略 B：先对列表排序。策略 C：使用循环。”
- 一旦 AI 选定一种策略，它就会绘制一个带有空缺的粗略“蓝图”（即草图）。蓝图包含主要结构（墙壁和屋顶），但将具体细节（油漆颜色、门把手）留作标记为 ?? 的空槽。
- 为何有效：这迫使 AI 在开始构建之前停下来思考不同的路径。它确保 AI 探索不同的解决方案“街区”，而不是在同一个街区里原地打转。
步骤 2：建造者（填充）
现在，对于每个蓝图，AI 扮演建造者的角色。它填充 ?? 空槽以创建完整的程序。
- 如果 AI 生成了 5 个蓝图（策略）并将每个填充 10 次，那么它现在就有 50 个完全不同的程序可供测试。
- 由于蓝图各不相同，这 50 个程序在结构上是多样化的。它们不仅仅是同一想法的重写，而是真正不同的方法。
步骤 3：检查员（验证）
最后，他们通过测试运行所有这些程序。他们保留那些能运行的程序，并挑选出最好的一个。

3. 结果：廉价 vs. 昂贵

研究人员在名为**HumanEval+**的标准代码测试上，使用 Google Gemini AI 的三个版本对此进行了测试：

Lite：小型、廉价、快速的模型。
Flash：中型模型。
Pro：大型、昂贵、智能的模型。

主要发现：

对于廉价机器人（Lite）：“草图与验证”方法是一个转折点。
- 如果仅仅让 Lite 机器人正常尝试 100 次（扁平采样），它解决了约 53% 的难题。
- 如果采用草图与验证方法（生成 10 个蓝图并将每个填充 10 次），它解决了 79% 的难题。
- 类比：这就像告诉学生：“不要就同一个主题写 100 篇论文。先为 10 个不同的主题写 10 个大纲，然后再填充内容。”这样学生能学到更多，并在付出相同努力的情况下获得更好的成绩。
对于昂贵机器人（Pro）：该方法帮助不大。
- Pro 机器人已经非常聪明，其“默认”想法通常是正确的。强迫它草拟不同的策略实际上会使其表现稍差，因为这分散了它对最佳直觉的注意力。
- 规则：如果你拥有超级聪明的机器人，就让它深入思考（贪婪搜索）。如果你只有廉价的机器人，就使用草图与验证来迫使它进行创造性思考。

4. 核心结论

该论文认为，草图与验证是一种明智的方式，可以在你受限于较小、较便宜的 AI 模型时，更有效地利用额外的计算资源。

它不是魔法：它不会让弱模型变得比强模型更强。如果你负担得起昂贵的"Pro"模型，直接使用它即可。
它是一种策略：如果你必须使用廉价模型（由于预算或速度限制），那么这种方法是从中榨取额外性能的最佳途径。它能防止 AI 陷入死胡同，并迫使其探索不同的解决方案，就像人类的头脑风暴会议一样。

简而言之：不要只是要求 AI 更努力地尝试；要要求它尝试不同的方法。

技术摘要：Sketch-and-Verify：通过程序草图实现结构化推理时扩展

1. 问题陈述

本文针对从业者面临的一个具体操作约束：给定一个因延迟或预算原因而选定的固定、小型且具成本效益的代码模型（例如 Gemini 3.1 Flash Lite），应如何分配有限的额外推理时计算资源以提高准确性？

标准方法涉及扁平采样（生成 $N$ 个独立的候选程序，并通过执行选择最佳者）。作者认为，扁平采样效率低下，因为它将程序空间视为同质的。大型语言模型（LLM）通常将高概率质量分配给单一的“模态”算法策略。因此，即使使用高温度或较大的 $N$ ，生成的候选池也缺乏结构多样性；它主要由同一 2–3 种策略的表面修饰变体（不同的变量名、格式）组成。如果模型的默认策略对特定问题不正确，无论采样数量多少，扁平采样很可能无法发现正确的解决方案。

2. 方法论：SKETCHVERIFY

作者提出了SKETCHVERIFY，这是一种通过因子化搜索空间为算法策略和实现细节来重构推理时计算的方法。该方法受程序草图（Solar-Lezama, 2008, 2013）和先前关于 LLM 驱动的编译器测试工作（OBsmith, Jiang et al., 2026b）的启发，分为四个阶段运行：

阶段 1：草图生成（类别优先提示）
- 类别枚举： 提示 LLM 以自然语言列出 $K$ 种根本不同的算法策略（例如，“哈希映射”、“双指针”、“动态规划”）。这迫使模型在编码之前对策略空间进行推理。
- 草图绘制： 对于每种策略，LLM 生成一个部分程序（即“草图”），其中算法、数据结构和控制流已完全指定，但实现细节（表达式、条件、循环边界）被替换为 ?? 占位符。目标是每个草图包含 4–8 个空缺。
- 关键创新： 这种两步过程防止自回归模型固着于单一默认策略，确保 $K$ 个草图之间具有结构多样性。
阶段 2：填充
- 每个有效草图被填充 $M$ 次，以生成 $K \times M$ 个完整候选程序。
- 为了鼓励单个草图内的变化，每第三次填充会以前一次填充为条件，并被要求提供不同的实现。
阶段 3：验证
- 对候选程序进行编译和无崩溃执行的过滤。
- 幸存的候选程序在 $D$ 个多样化的测试输入（通过类似的基于草图的方法生成）上执行。
- 为每个候选程序生成执行指纹：一个由（状态，输出）对组成的向量。相同的指纹表示行为等价。
阶段 4：选择
- 根据执行指纹对候选程序进行聚类。
- 选择最大的簇（代表最稳健的行为共识）。
- 从最大簇中返回最短的程序（奥卡姆剃刀）。此选择规则与并行的“语义投票”工作线完全相同，从而将结构化生成的收益与选择机制隔离开来。

3. 主要贡献

SKETCHVERIFY 框架： 引入了一种同层成本 - 性能策略，将程序草图应用于推理时扩展。它将搜索空间因子化为 $K$ （策略）和 $M$ （实现），在弱模型上实现了比扁平采样更陡峭的 pass@1 扩展曲线。
成本 - 质量帕累托分析： 在 HumanEval+ 基准上进行了严格分析，特别是重新分析了 19 个问题的“困难子集”，其中基线 Lite 模型（贪婪）失败。
- 同层比较： 在匹配的候选数量下，草图法优于扁平采样。在困难子集上，Lite 草图（ $K=2, M=5$ ）恢复了 58% 的问题，而扁平采样（ $N=10$ ）仅为 26%。即使预算增加 3 倍，扁平采样（ $N=50$ ）也仅达到 47%，仍低于更便宜的草图配置。
- 跨层比较： 草图法不能替代模型升级。更强的层级（例如 Gemini Pro 贪婪）在成本和准确性上均优于 Lite+ 草图配置。草图法是对模型层级升级的补充，而非替代。
类别优先分解： 提出了一种特定的提示策略（在编码前枚举策略名称），这对于生成结构多样性而非表面修饰变体至关重要。
$K$ 与 $M$ 的权衡特征： 通过扩展扫描，作者展示了 $K$ 和 $M$ 之间的关系是非单调的。混合分配（例如 $K=2, M=5$ ）通常优于纯扁平（ $K=1$ ）或纯草图（ $M=1$ ）的极端情况，且简单地增加 $K$ 并不总是产生线性收益（例如，在某些指标上， $K=5, M=10$ 的表现不如 $K=2, M=5$ ）。
可组合性： 证明了结构化生成与基于执行的（语义投票）选择能够干净地组合。该方法作为多样化候选池的生成器，而选择器则对生成方法保持无关。

4. 实验结果

基准测试： 在 HumanEval+（164 个带有增强测试套件的 Python 问题）上进行了评估。跨基准验证（MBPP+ 和 LiveCodeBench）被列为未来工作。
模型： 三个层级的 Google Gemini 模型（Pro, Flash, Flash Lite），处于低思考水平。
困难子集性能（Lite 贪婪失败的 19 个问题）：
- Lite 草图（ $K=10, M=10$ ）： pass@1 为 79%。
- Lite 扁平（ $N=100$ ）： pass@1 为 53%。
- Lite 草图（ $K=2, M=5$ ）： pass@1 为 58%（成本低于扁平 $N=50$ ）。
- Flash/Pro 贪婪： 优于所有 Lite 配置，证实模型能力是准确性的主要驱动因素。
扩展曲线： 在整个 HumanEval+ 集上，Lite 扁平采样在约 89% 的 pass@1 处饱和。SKETCHVERIFY 打破了这一上限，在 $K=10, M=10$ 时达到 93%。然而，在 Flash 和 Pro 模型上，由于模型已接近饱和，与贪婪解码相比，草图法带来的收益微乎其微或不存在。

5. 意义与主张

本文将 SKETCHVERIFY 定位为一种同层成本 - 性能策略，而非通用的准确性改进方案。

从业者规则： 如果可用更强的模型层级，则在该层级上使用贪婪解码。如果受限于较弱的模型（由于延迟、部署或预算），SKETCHVERIFY 是花费额外推理时计算资源最具成本效益的方式。
机制： 该方法通过显式强制探索不同的算法策略（结构多样性）取得成功，而不是依赖扁平采样的随机性来偶然发现新方法。
局限性： 作者承认了局限性，包括依赖单一模型家族（Gemini）、单一思考水平，以及草图质量受限于模型自身的策略分布（如果模型无法构想出正确的策略，草图法也无法生成它）。他们还指出，草图生成阶段存在约 7% 的 token 开销。

本文结论认为，虽然草图法对于在策略多样性方面挣扎的弱模型非常有效，但它并非适用于那些已达到能力上限的模型，或适用于正确策略完全超出模型潜在知识的问题的万能药。