草图和验证:通过程序草图进行结构化推理时间缩放
Sketch-and-Verify: Structured Inference-Time Scaling via Program Sketching
摘要
SKETCHVERIFY 是一项层内性价比策略,而不是普遍的精度改进。操作问题:由于延迟、部署或预算原因,从业者坚持使用小型、廉价的代码模型(此处为 Gemini 3.1 Flash Lite)——他们应该如何花费少量额外的测试时间计算? SKETCHVERIFY 因式分解搜索空间:LLM 枚举 K 个不同的算法策略,为每个策略编写一个程序草图(带有 ?? 漏洞的部分程序),并将每个草图填充 M 次,产生 K x M 结构多样的候选者,这些候选者通过执行进行验证并通过指纹聚类进行选择。每个额外的草图都保证探索不同的算法;每个额外的平面样本可能都会重复现有的样本。我们的核心证据是 HumanEval+ 上跨三个 Gemini 层(Lite、Flash、Pro)的成本质量帕累托图,以及对 Lite 贪婪失败的 19 个问题的重新分析。两个发现:(1)在层内,草图在匹配的候选数量上主导平面抽样。在困难子集上,Lite Sketch K=2、M=5 恢复为 11/19 (58%),而平面 N=10 恢复为 5/19 (26%,+32pp); Lite Sketch K=10、M=10 恢复为 15/19 (79%),而平面 N=100 恢复为 10/19 (53%,+26pp)。即使预算约为 3 倍,Flat 也无法缩小差距:Flat N=50 仍然输给 Sketch K=2、M=5 +11pp。 (2)跨层级,画图不取代升级。 Pro 贪婪 (89%) 在 pass@1 和美元成本上都优于 Lite Sketch K=10、M=10 (79%)。实践者规则:如果有更强的层可用,就使用贪婪;否则,绘制草图是花费额外计算的经济有效的方法。我们通过 Flash Lite 缩放扫描来描述 K-vs-M 权衡,报告 Flash 和 Pro 上的 HumanEval+ 饱和度,并展示该方法与并发语义投票工作线中基于执行的选择完美结合。