用程序草图结构化测试时计算，提升小模型的代码生成效果
Sketch-and-Verify: Structured Inference-Time Scaling via Program Sketching
- 通过生成带占位符的程序草图，系统性探索不同算法策略
- 在相同候选数下，草图法比随机采样在硬题上高出32个百分点
- 适合预算有限但想优化小模型性能的开发者使用
SKETCHVERIFY 是一种针对特定模型层级的成本-性能策略，而非通用精度提升方法。当实践者受限于小型廉价代码模型（如 Gemini 3.1 Flash Lite）的延迟、部署或预算时，如何有效利用少量额外测试时计算？该方法将搜索空间分解：LLM 枚举 K 种不同算法策略，为每种生成一个含 ?? 占位符的程序草图，并对每个草图填充 M 次，生成 K×M 个结构多样候选，经执行验证后通过指纹聚类选择最优解。每个新增草图确保探索新算法，而额外随机样本则很可能重复已有路径。核心证据来自 HumanEval+ 上三个 Gemini 层级（Lite、Flash、Pro）的成本-质量帕累托图，以及对 Lite greedy 失败的 19 个问题的重新分析。结果表明：(1) 同层级内，草图法在匹配候选数量时显著优于随机采样；在硬子集上，Lite Sketch K=2, M=5 恢复 11/19（58%），而 flat N=10 仅 5/19（26%，+32pp）；Lite Sketch K=10, M=10 恢复 15/19（79%），而 flat N=100 仅 10/19（53%，+26pp）。即使预算增至 3 倍，flat N=50 仍落后于 Sketch K=2, M=5 11pp。(2) 跨层级，草图法无法替代升级：Pro greedy（89%）在 pass@1 和美元成本上均优于 Lite Sketch K=10, M=10（79%）。实践建议：若更强模型可用，优先在该模型上使用贪婪搜索；否则，草图法是高效利用额外计算的手段。通过 Flash Lite 的缩放实验刻画了 K 与 M 的权衡，报告了 Flash 与 Pro 在 HumanEval+ 上的饱和表现，并证明该方法可与基于执行的选择机制（如 Semantic Voting）无缝组合。
原文摘要 · Abstract (English)
SKETCHVERIFY is a within-tier cost-performance policy, not a universal accuracy improvement. The operational question: a practitioner stuck with a small, cheap code model (here, Gemini 3.1 Flash Lite) for latency, deployment, or budget reasons -- how should they spend a small amount of extra test-time compute? SKETCHVERIFY factorizes the search space: the LLM enumerates K distinct algorithmic strategies, writes a program sketch for each (a partial program with ?? holes), and fills each sketch M times, producing K x M structurally diverse candidates that are verified by execution and selected by fingerprint clustering. Each extra sketch is guaranteed to explore a different algorithm; each extra flat sample likely duplicates an existing one. Our central evidence is a cost-quality Pareto plot on HumanEval+ across three Gemini tiers (Lite, Flash, Pro), and a reanalysis of the 19 problems where Lite greedy fails. Two findings: (1) Within-tier, sketching dominates flat sampling at matched candidate count. On the hard subset, Lite Sketch K=2, M=5 recovers 11/19 (58%) vs. flat N=10 at 5/19 (26%, +32pp); Lite Sketch K=10, M=10 recovers 15/19 (79%) vs. flat N=100 at 10/19 (53%, +26pp). Flat cannot close the gap even at ~3x the budget: flat N=50 still loses to Sketch K=2, M=5 by +11pp. (2) Cross-tier, sketching does not replace upgrading. Pro greedy (89%) dominates Lite Sketch K=10, M=10 (79%) on both pass@1 and dollar cost. Practitioner rule: if a stronger tier is available, use greedy on it; otherwise sketching is the cost-effective way to spend extra compute. We characterize the K-vs-M trade-off via a Flash Lite scaling sweep, report HumanEval+ saturation on Flash and Pro, and show the method composes cleanly with execution-based selection from the concurrent Semantic Voting line of work.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。