プログラムスケッチによる構造化推論時スケーリング手法 Sketch-and-Verify: Structured Inference-Time Scaling via Program Sketching

Inference-time scaling, the practice of spending extra compute at decoding to lift model accuracy, has become one of the most active research fronts in large language models. This paper, Sketch-and-Verify, argues that the dominant approach of brute-force sampling or long chain-of-thought is wasteful, and proposes instead to structure the extra compute through program sketches.

The core idea borrows from classical program synthesis. A sketch is a partial program in which the high-level control flow and the overall shape of the solution are fixed by the author, while specific expressions are left as holes to be filled by a synthesizer. The authors adapt this pattern to LLM reasoning: the model first produces a sketch that captures the skeleton of a candidate solution, a search procedure then generates concrete completions for the holes, and a verifier checks each filled-in candidate. By committing early to structural decisions, the search space at scaling time becomes a tree of well-formed variants rather than a flat pool of independent samples.

This design echoes a broader trend toward hybrid neuro-symbolic reasoning. Methods such as Tree-of-Thoughts, Self-Consistency, Best-of-N sampling, and process reward models all try to convert raw compute into better answers by adding some form of branching and scoring. Program-Aided Language Models and tool-augmented reasoning take a different route, offloading subproblems to interpreters. Sketch-and-Verify sits between these lines: it keeps generation inside the model but constrains it with an explicit structural prior, which is likely to be most effective on tasks where correctness can be mechanically checked, such as code synthesis, mathematical derivations, or constraint satisfaction.

There are several reasons to find the approach attractive. First, sketches act as a form of compute budgeting; expensive search effort is directed only at the parts of the solution that the model is genuinely uncertain about. Second, verifier feedback becomes more informative because failures localize to specific holes rather than to entire chains. Third, the framework is compatible with existing scaling tricks, so it could plausibly be stacked with reward models or self-refinement loops.

The paper also raises questions that remain open. The quality of the initial sketch is critical: a wrong skeleton cannot be repaired by hole-filling, so the method may inherit the brittleness of one-shot planning. Designing verifiers that are both sound and cheap is nontrivial outside formally checkable domains. And the right granularity of holes, too coarse and search explodes, too fine and the structural benefit fades, will likely need tuning per task. Readers should also note that the cited arXiv identifier appears unusual, so bibliographic details may warrant verification.

Even so, the broader message is in line with where the field seems to be heading. As frontier labs from OpenAI to DeepSeek invest in reasoning-time compute, methods that impose explicit structure on that compute, rather than simply spending more of it, are likely to play a growing role. Sketch-and-Verify is a concrete proposal in that direction and a useful reference point for anyone designing inference-time systems.