mlsanityData to 7 Oct 2026

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

arXiv 2605.08658 ↗First posted 9 May 2026cs.LG cs.AI cs.SEcited by 0

On the map: LLM reasoning → Test-time compute and efficient thinking

Abstract (arXiv)

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.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Placed in Test-time compute and efficient thinking, one of 17 directions in LLM reasoning. Builds on 21 of its 25 references that are in the map. First posted on arXiv 9 May 2026.

Builds on

21 of 25 references.

Closest ancestors · 2

Same direction, newest first

  1. 2025Wider or Deeper? Scaling LLM Inference-Time Compute with Adaptive Branching Tree Search6 Mar
  2. 2024Inference Scaling Laws: An Empirical Analysis of Compute-Optimal Inference for Problem-Solving with Language Models1 Aug

Other references · 19

  1. 2021Evaluating Large Language Models Trained on Codecited by 8,053
  2. 2022Self-Consistency Improves Chain of Thought Reasoning in Language Modelscited by 5,601
  3. 2023Reflexion: Language Agents with Verbal Reinforcement Learningcited by 4,064
  4. 2024LiveCodeBench: Holistic and Contamination Free Evaluation of Large Language Models for Codecited by 1,906
  5. 2022Competition-Level Code Generation with AlphaCodecited by 1,427
  6. 2023Is Your Code Generated by ChatGPT Really Correct? Rigorous Evaluation of Large Language Models for Code Generationcited by 1,332
  7. 2023Language Agent Tree Search Unifies Reasoning Acting and Planning in Language Modelscited by 551
  8. 2022CodeT: Code Generation with Generated Testscited by 369
  9. 2022Natural Language to Code Translation with Executioncited by 122
  10. 2023Self-planning Code Generation with Large Language Modelscited by 121
  11. 2025Sketch-of-Thought: Efficient LLM Reasoning with Adaptive Cognitive-Inspired Sketchingcited by 116
  12. 2022Coder Reviewer Reranking for Code Generationcited by 83
7 more
  1. 2024A Simple Model of Inference Scaling Lawscited by 36
  2. 2024Unlocking Reasoning Potential in Large Langauge Models by Scaling Code-form Planningcited by 24
  3. 2025On the Effectiveness of Large Language Models in Writing Alloy Formulascited by 7
  4. 2024Generating executable oracles to check conformance of client code to requirements of JDK Javadocs using LLMscited by 6
  5. 2025CASCADE: LLM-Powered JavaScript Deobfuscator at Googlecited by 5
  6. 2025An approach for API synthesis using large language modelscited by 4
  7. 2025OBsmith: LLM-Powered JavaScript Obfuscator Testingcited by 2

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way

  1. 2025Sample, Scrutinize and Scale: Effective Inference-Time Search by Scaling Verification
  2. 2026Test-Time Scaling in the Wild: Why Exploitation, Not Exploration, Is the Bottleneck
  3. 2026Verification Trap: Understanding Test-Time Selection Failures under False Premises in Code Generation
  4. 2025Pareto Optimal Code Generation
  5. 2025T1: Tool-integrated Verification for Test-time Compute Scaling in Small Language Models
  6. 2026CoBa: Cost-Effective Test-Time Scaling via Compute-Balanced Routing
  7. 2026Hill Sampling for Test-Time Scaling: A Simple and Better Alternative to Repeated Sampling, Evolution, and Training
  8. 2026Interaction Scaling: Grounding the Third Axis of Test-Time Compute