Source note
Sketch-and-Verify: Structured Inference-Time Scaling via Program Sketching
Summary
SketchVerify is an inference-time method for code generation that spends extra compute on different algorithmic sketches before sampling implementations. Its strongest claim is a weak-model gain on hard HumanEval+ problems; stronger model greedy decoding can still be cheaper and more accurate.
Problem
- Small code models often repeat the same wrong algorithm when sampled many times, so extra candidates may add cosmetic variation instead of new solution strategies.
- This matters when a practitioner must use a cheap or low-latency model tier and wants better pass@1 without switching models.
- Flat sampling gives no direct control over how many distinct algorithms the model tries.
Approach
- The model first lists K different algorithmic strategies for a programming problem, such as hash map, sorting with two pointers, or dynamic programming.
- For each strategy, it writes a partial Python program sketch with ?? holes for expressions, conditions, or bounds while keeping the main control flow fixed.
- The model fills each sketch M times, producing K×M candidate programs.
- Candidates are compiled and run on generated tests; passing candidates are grouped by execution fingerprints, and the shortest program in the largest behavior cluster is selected.
- The method keeps the selector close to flat Semantic Voting, so the main change is candidate generation rather than a new voting rule.
Results
- On 19 HumanEval+ problems where Gemini 3.1 Flash Lite greedy fails, Lite Sketch K=2,M=5 solved 11/19 problems, or 58%, versus flat N=10 solving 5/19, or 26%, a +32 pp gain at matched candidate count.
- On the same hard subset, Lite Sketch K=10,M=10 solved 15/19, or 79%, versus flat N=100 solving 10/19, or 53%, a +26 pp gain at matched candidate count.
- Lite Sketch K=2,M=5 cost $3.8e-4 per problem and beat flat N=50, which solved 9/19, or 47%, at $1.1e-3 per problem.
- On full HumanEval+, Lite Sketch K=10,M=10 reached 92.1% pass@1, compared with Lite greedy at 85.4% and flat Semantic Voting at 92.7%.
- On a 100-problem Lite scaling sweep, Sketch K=2,M=5 reached 91.0% at about 11.6K tokens, while flat N=10 reached 85.0% at about 8.0K tokens; Sketch K=10,M=10 reached 93.0% at about 88.4K tokens, while flat N=100 reached 89.0% at about 62.0K tokens.
- Cross-tier results weaken the deployment claim: on the hard subset, Flash greedy solved 17/19, or 89%, at $1.1e-4 per problem, beating Lite Sketch K=10,M=10 at 15/19, or 79%, and $2.8e-3 per problem.