🤖 machine learning

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

The paper introduces Sketch-and-Verify, a cost-effective inference-time scaling strategy for small code models that outperforms flat sampling by enumerating diverse algorithmic sketches and filling them with multiple candidates, though it cannot fully replace the performance of stronger model tiers.

Original authors: Shan Jiang, Zijian Yi, Chenguang Zhu

Published 2026-05-12

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Shan Jiang, Zijian Yi, Chenguang Zhu

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to solve a tricky puzzle, but you only have a small, inexpensive robot to help you. This robot is fast and cheap, but it has a bad habit: when it tries to solve a problem, it almost always picks the same wrong way of thinking. If you ask it to try 100 times, it will just give you 100 slightly different versions of that same wrong answer.

This is the problem the paper "Sketch-and-Verify" tries to solve. It offers a new way to use that small, cheap robot so it can solve more problems without needing to upgrade to a super-expensive, giant robot.

Here is how the method works, broken down into simple steps:

1. The Problem: The "Same Old Song"

Usually, when we ask an AI to write code, we just say, "Try 100 times and give me the best one."

The Flaw: If the AI's "default" idea is wrong, asking it to try 100 times is like asking a person to write 100 different versions of a bad song. You might change the lyrics or the tempo, but the melody is still wrong. The AI gets stuck in a loop of "cosmetic" changes (changing variable names or formatting) without ever trying a fundamentally different approach.

2. The Solution: The "Architect and the Builder"

The authors propose a two-step process called Sketch-and-Verify. Instead of asking the AI to write the whole code immediately, they split the job into two roles:

Step 1: The Architect (The Sketch)
First, they ask the AI to act like an architect. They say: "Don't write the code yet. Just list 5 completely different ways to solve this problem."
- Example: "Strategy A: Use a map. Strategy B: Sort the list first. Strategy C: Use a loop."
- Once the AI picks a strategy, the AI draws a rough "blueprint" (a sketch) with holes in it. The blueprint has the main structure (the walls and roof) but leaves the specific details (the paint color, the doorknob) as empty slots marked ??.
- Why this helps: This forces the AI to stop and think about different paths before it starts building. It guarantees that the AI explores different "neighborhoods" of solutions instead of just walking in circles in the same one.
Step 2: The Builder (The Fill)
Now, for each blueprint, the AI acts as a builder. It fills in the ?? holes to create a complete program.
- If the AI made 5 blueprints (strategies) and filled each one 10 times, it now has 50 completely different programs to test.
- Because the blueprints were different, these 50 programs are structurally diverse. They aren't just rewrites of the same idea; they are genuinely different approaches.
Step 3: The Inspector (Verify)
Finally, they run all these programs through a test. They keep the ones that work and pick the best one.

3. The Results: Cheap vs. Expensive

The researchers tested this on a standard coding test called HumanEval+ using three versions of Google's Gemini AI:

Lite: The small, cheap, fast model.
Flash: The medium model.
Pro: The big, expensive, smart model.

The Big Findings:

For the Cheap Robot (Lite): The "Sketch-and-Verify" method was a game-changer.
- If they just asked the Lite robot to try 100 times normally (Flat Sampling), it solved about 53% of the hard problems.
- If they used the Sketch-and-Verify method (making 10 blueprints and filling them 10 times), it solved 79% of the hard problems.
- The Analogy: It's like telling a student, "Don't just write 100 essays on the same topic. Write 10 outlines for 10 different topics, then fill them in." The student learns more and gets a better grade for the same amount of effort.
For the Expensive Robot (Pro): The method didn't help much.
- The Pro robot is already so smart that its "default" idea is usually right. Forcing it to sketch different strategies actually made it slightly worse because it was distracted from its best instinct.
- The Rule: If you have a super-smart robot, just let it think hard (Greedy). If you only have a cheap robot, use Sketch-and-Verify to force it to think creatively.

4. The Bottom Line

The paper argues that Sketch-and-Verify is a smart way to spend extra computing power when you are stuck with a smaller, cheaper AI model.

It's not magic: It doesn't make a weak model stronger than a strong model. If you can afford the expensive "Pro" model, just use that.
It is a strategy: If you must use the cheap model (because of budget or speed), this method is the best way to squeeze extra performance out of it. It stops the AI from getting stuck in a rut and forces it to explore different solutions, much like a human brainstorming session.

In short: Don't just ask the AI to try harder; ask it to try differently.

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

1. Problem Statement

The paper addresses a specific operational constraint faced by practitioners: given a fixed, small, and cost-effective code model (e.g., Gemini 3.1 Flash Lite) chosen for latency or budget reasons, how should one allocate a limited amount of extra test-time compute to improve accuracy?

Standard approaches involve flat sampling (generating $N$ independent candidate programs and selecting the best via execution). The authors argue that flat sampling is inefficient because it treats the program space as homogeneous. Large language models (LLMs) often assign high probability mass to a single "modal" algorithmic strategy. Consequently, even with high temperature or large $N$ , the resulting candidate pool lacks structural diversity; it consists mostly of superficial cosmetic variants (different variable names, formatting) of the same 2–3 strategies. If the model's default strategy is incorrect for a specific problem, flat sampling will likely fail to discover the correct solution regardless of the number of samples.

2. Methodology: SKETCHVERIFY

The authors propose SKETCHVERIFY, a method that restructures inference-time compute by factorizing the search space into algorithmic strategy and implementation details. Inspired by program sketching (Solar-Lezama, 2008, 2013) and prior work on LLM-powered compiler testing (OBsmith, Jiang et al., 2026b), the method operates in four stages:

Stage 1: Sketch Generation (Category-First Prompting)
- Category Enumeration: The LLM is prompted to list $K$ fundamentally different algorithmic strategies (e.g., "hash map," "two pointers," "dynamic programming") in natural language. This forces the model to reason about the strategy space before coding.
- Sketching: For each strategy, the LLM generates a partial program (a "sketch") where the algorithm, data structures, and control flow are fully specified, but implementation details (expressions, conditions, loop bounds) are replaced with ?? placeholders. The target is 4–8 holes per sketch.
- Key Innovation: This two-step process prevents the autoregressive model from fixating on a single default strategy, ensuring structural diversity across the $K$ sketches.
Stage 2: Filling
- Each valid sketch is filled $M$ times to produce $K \times M$ complete candidate programs.
- To encourage variation within a single sketch, every third fill is conditioned on the previous fill and asked to provide a different implementation.
Stage 3: Verification
- Candidates are filtered for compilation and crash-free execution.
- Surviving candidates are executed on $D$ diverse test inputs (generated via a similar sketch-based approach).
- An execution fingerprint is generated for each candidate: a vector of (status, output) pairs. Identical fingerprints indicate behavioral equivalence.
Stage 4: Selection
- Candidates are clustered by their execution fingerprints.
- The largest cluster (representing the most robust behavioral consensus) is selected.
- From the largest cluster, the shortest program is returned (Occam's razor). This selection rule is identical to the concurrent "Semantic Voting" line of work, isolating the benefit of structured generation from the selection mechanism.

3. Key Contributions

SKETCHVERIFY Framework: Introduces a within-tier cost-performance policy that applies program sketching to inference-time scaling. It factorizes the search space into $K$ (strategies) and $M$ (implementations), achieving a steeper pass@1 scaling curve than flat sampling on weak models.
Cost-Quality Pareto Analysis: Provides a rigorous analysis on the HumanEval+ benchmark, specifically reanalyzing a "hard subset" of 19 problems where the baseline Lite model (greedy) fails.
- Within-Tier: Sketching dominates flat sampling at matched candidate counts. On the hard subset, Lite Sketch ( $K=2, M=5$ ) recovers 58% of problems vs. 26% for flat sampling ( $N=10$ ). Even with a 3x budget increase, flat sampling ( $N=50$ ) only reaches 47%, still losing to the cheaper sketch configuration.
- Cross-Tier: Sketching does not replace model upgrading. Stronger tiers (e.g., Gemini Pro greedy) dominate Lite+Sketch configurations on both cost and accuracy. Sketching is a complement to, not a substitute for, upgrading the model tier.
Category-First Decomposition: Proposes a specific prompting strategy (enumerating strategy names before coding) that is critical for generating structural diversity rather than cosmetic variants.
K-vs-M Trade-off Characterization: Through scaling sweeps, the authors show the relationship between $K$ and $M$ is non-monotone. Mixed allocations (e.g., $K=2, M=5$ ) often outperform pure-flat ( $K=1$ ) or pure-sketch ( $M=1$ ) extremes, and simply increasing $K$ does not always yield linear gains (e.g., $K=5, M=10$ underperformed $K=2, M=5$ in some metrics).
Composability: Demonstrates that structured generation composes cleanly with execution-based selection (Semantic Voting). The method acts as a generator of a diverse candidate pool, while the selector remains agnostic to the generation method.

4. Experimental Results

Benchmarks: Evaluated on HumanEval+ (164 Python problems with augmented test suites). Cross-benchmark validation on MBPP+ and LiveCodeBench is noted as future work.
Models: Three tiers of Google Gemini models (Pro, Flash, Flash Lite) at low thinking levels.
Hard Subset Performance (19 problems where Lite greedy fails):
- Lite Sketch ( $K=10, M=10$ ): 79% pass@1.
- Lite Flat ( $N=100$ ): 53% pass@1.
- Lite Sketch ( $K=2, M=5$ ): 58% pass@1 (at a lower cost than Flat $N=50$ ).
- Flash/Pro Greedy: Outperforms all Lite configurations, confirming that model capability is the primary driver of accuracy.
Scaling Curves: On the full HumanEval+ set, Lite flat sampling saturates at ~89% pass@1. SKETCHVERIFY breaks this ceiling, reaching 93% at $K=10, M=10$ . However, on Flash and Pro, where models are near-saturated, the gains from sketching are marginal or non-existent compared to greedy decoding.

5. Significance and Claims

The paper positions SKETCHVERIFY as a within-tier cost-performance policy, not a universal accuracy improvement.

Practitioner Rule: If a stronger model tier is available, use greedy decoding on that tier. If constrained to a weaker model (due to latency, deployment, or budget), SKETCHVERIFY is the most cost-effective way to spend extra test-time compute.
Mechanism: The method succeeds by explicitly forcing the exploration of different algorithmic strategies (structural diversity) rather than relying on the stochasticity of flat sampling to accidentally find a new approach.
Limitations: The authors acknowledge limitations including reliance on a single model family (Gemini), a single thinking level, and the fact that sketch quality is bounded by the model's own strategy distribution (if the model cannot conceive of the correct strategy, sketching cannot generate it). They also note a ~7% token overhead for the sketch generation phase.

The paper concludes that while sketching is highly effective for weak models struggling with strategic diversity, it is not a panacea for models that have already reached their capability ceiling or for problems where the correct strategy is entirely outside the model's latent knowledge.