🤖 machine learning

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

本論文は、多様なアルゴリズム的スケッチを列挙し、それらを複数の候補で埋めることで、フラットサンプリングを上回る小規模コードモデル向けの低コスト推論時スケーリング戦略「Sketch-and-Verify」を導入するが、これはより強力なモデル階層のパフォーマンスを完全に代替するものではない。

原著者： Shan Jiang, Zijian Yi, Chenguang Zhu

公開日 2026-05-12

📖 1 分で読めます☕ さくっと読める

CC BY 4.0

原著者： Shan Jiang, Zijian Yi, Chenguang Zhu

原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 ✨ これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。免責事項の全文を読む

あなたが複雑なパズルを解こうとしているが、頼れるのは小さくて安価なロボットだけだと想像してください。このロボットは速く安価ですが、悪い癖があります。問題を解こうとすると、ほぼ常に同じ間違った考え方を採用してしまうのです。100 回試すよう頼んでも、それは結局、その同じ間違った答えの 100 通りのわずかに異なるバリエーションを返すに過ぎません。

これが、論文「Sketch-and-Verify（スケッチと検証）」が解決しようとしている問題です。この論文は、その小さくて安価なロボットを、超高性能で巨額なロボットにアップグレードすることなく、より多くの問題を解決できるようにするための新しいアプローチを提案しています。

この手法の仕組みを、簡単なステップに分解して説明します。

1. 問題：「いつもの歌」

通常、AI にコード作成を依頼する際、「100 回試して、最も良いものを選んでください」と言うだけです。

欠点: AI の「デフォルト」の考え方が間違っている場合、100 回試すよう頼むことは、ある人が悪い歌の 100 通りの異なるバージョンを書くよう頼むようなものです。歌詞やテンポは変わっても、メロディ自体は間違っています。AI は変数名や書式の変更といった「表面的な」変化のループに陥り、根本的に異なるアプローチを試すことがありません。

2. 解決策：「建築家と建設業者」

著者は、Sketch-and-Verifyと呼ばれる 2 段階のプロセスを提案しています。AI にすぐにコード全体を書かせるのではなく、作業を 2 つの役割に分けます。

ステップ 1：建築家（スケッチ）
まず、AI に建築家として振る舞うよう頼みます。「まだコードは書かないで。この問題を解決する 5 つの全く異なる方法をリストアップしてください」と伝えます。
- 例: 「戦略 A: マップを使用する。戦略 B: リストを先にソートする。戦略 C: ループを使用する。」
- AI が戦略を選んだら、穴の開いた大まかな「設計図」（スケッチ）を描きます。この設計図には主要な構造（壁や屋根）が含まれますが、具体的な詳細（塗料の色やドアノブ）は ?? とマークされた空の枠として残されます。
- これが役立つ理由: これにより、AI は建設を始める前に、異なる 経路について考えることを強いられます。これにより、AI は同じ場所をぐるぐる回るのではなく、解決策の異なる「地域」を探査することが保証されます。
ステップ 2：建設業者（充填）
次に、各設計図に対して、AI は建設業者として振る舞います。?? の穴を埋めて完全なプログラムを作成します。
- AI が 5 つの設計図（戦略）を作成し、それぞれを 10 回ずつ埋めたとすると、テスト可能な 50 個の全く異なるプログラムが生まれます。
- 設計図が異なっていたため、これらの 50 個のプログラムは構造的に多様です。これらは単に同じアイデアの書き換えではなく、本質的に異なるアプローチです。
ステップ 3：検査員（検証）
最後に、これらすべてのプログラムをテストにかけます。動作するものを残し、最も良いものを選びます。

3. 結果：安価 vs 高価

研究者たちは、Google の Gemini AI の 3 つのバージョンを用いて、標準的なコーディングテストである**HumanEval+**でこれをテストしました。

Lite: 小型、安価、高速なモデル。
Flash: 中規模モデル。
Pro: 大型、高価、高性能なモデル。

主な発見:

安価なロボット（Lite）の場合: 「Sketch-and-Verify」手法は画期的でした。
- Lite ロボットに通常の 100 回試行（フラットサンプリング）を頼んだ場合、難しい問題の約**53%**を解決できました。
- Sketch-and-Verify 手法（10 の設計図を作成し、それぞれを 10 回ずつ埋める）を用いた場合、難しい問題の**79%**を解決できました。
- 比喩: 学生に「同じテーマで 100 本のエッセイを書くのではなく、10 個の異なるテーマの 10 本のアウトラインを書き、それから埋めてください」と言うようなものです。学生は同じ労力でより学び、より良い成績を得ることができます。
高価なロボット（Pro）の場合: この手法はあまり役立ちませんでした。
- Pro ロボットはすでに非常に賢く、その「デフォルト」の考え方は通常正しいものです。あえて異なる戦略をスケッチさせることは、むしろ最良の直感から注意をそらさせ、わずかに悪化させる結果となりました。
- ルール: もし超高性能なロボットを持っているなら、ただ深く考えさせる（Greedy）だけでよいです。もし安価なロボットしかないなら、Sketch-and-Verify を使って、強制的に創造的に考えさせます。

4. 結論

この論文は、Sketch-and-Verifyが、より小さく安価な AI モデルに依存せざるを得ない状況において、追加の計算リソースを賢く使う方法であると主張しています。

魔法ではない: これは弱いモデルを強いモデルよりも強くするものではありません。もし高価な「Pro」モデルを予算的に許容できるなら、それを使うべきです。
戦略である: 予算や速度の制約により、安価なモデルを使用しなければならない場合、この手法はそこから追加のパフォーマンスを引き出す最良の方法です。これは、AI が行き詰まるのを防ぎ、人間のブレインストーミングセッションのように、異なる解決策を探査することを強制します。

要約すると：AI に「もっと頑張れ」と言うのではなく、「違う方法で試せ」と言いなさい。

技術概要：Sketch-and-Verify：プログラムスケッチによる構造化推論時スケーリング

1. 問題定義

本論文は、実務家が直面する特定の運用制約に焦点を当てている。遅延時間や予算の理由から選択された、固定された小規模かつ費用対効果の高いコードモデル（例：Gemini 3.1 Flash Lite）が与えられた場合、精度を向上させるために限られた追加の推論時計算リソースをどのように配分すべきか。

標準的なアプローチはフラットサンプリング（ $N$ 個の独立した候補プログラムを生成し、実行を通じて最良のものを選択する）である。著者らは、フラットサンプリングがプログラム空間を均質とみなすため非効率的であると主張する。大規模言語モデル（LLM）は、しばしば単一の「モード」アルゴリズム戦略に高い確率質量を割り当てる。その結果、高温（high temperature）設定や大きな $N$ を用いても、生成される候補プールには構造的な多様性が欠如しており、主に 2〜3 の戦略の同じものの表面的な外観的変種（異なる変数名、フォーマットなど）で構成される。モデルのデフォルト戦略が特定の問題に対して誤っている場合、サンプリング数を増やしてもフラットサンプリングは正しい解を発見できない可能性が高い。

2. 手法：SKETCHVERIFY

著者らは、検索空間をアルゴリズム戦略と実装詳細に因数分解することで推論時計算を再構成するSKETCHVERIFYを提案する。プログラムスケッチ（Solar-Lezama, 2008, 2013）および LLM 駆動のコンパイラテストに関する先行研究（OBsmith, Jiang et al., 2026b）に触発され、本手法は以下の 4 つの段階で動作する。

段階 1：スケッチ生成（カテゴリファースト・プロンプティング）
- カテゴリ列挙：LLM に、自然言語で $K$ 個の根本的に異なるアルゴリズム戦略（例：「ハッシュマップ」、「2 ポインタ法」、「動的計画法」）を列挙するようプロンプトする。これにより、モデルはコーディング前に戦略空間について推論することを強制される。
- スケッチ作成：各戦略について、LLM はアルゴリズム、データ構造、制御フローが完全に指定されたが、実装詳細（式、条件、ループ境界）が ?? というプレースホルダーに置き換えられた部分的なプログラム（「スケッチ」）を生成する。目標はスケッチあたり 4〜8 の穴（ホール）である。
- 主要な革新点：この 2 段階のプロセスにより、自己回帰モデルが単一のデフォルト戦略に固執するのを防ぎ、 $K$ 個のスケッチ全体にわたって構造的な多様性を確保する。
段階 2：充填
- 各有効なスケッチを $M$ 回充填して、 $K \times M$ 個の完全な候補プログラムを生成する。
- 単一のスケッチ内での多様性を促進するため、3 回目ごとに充填は前の充填を条件とし、異なる実装を提供するよう求められる。
段階 3：検証
- 候補をコンパイルおよびクラッシュなしの実行でフィルタリングする。
- 生き残った候補を、同様のスケッチベースのアプローチで生成された $D$ 個の多様なテスト入力上で実行する。
- 各候補に対して実行フィンガープリント（状態と出力のペアのベクトル）を生成する。同一のフィンガープリントは機能的等価性を示す。
段階 4：選択
- 候補を実行フィンガープリントに基づいてクラスタリングする。
- 最大クラスター（最も堅牢な行動的合意を表す）を選択する。
- 最大クラスターから、最短のプログラムを返す（オッカムの剃刀）。この選択ルールは、同時進行中の「セマンティック・ボティング」研究ラインと同一であり、構造化生成の利点を選択メカニズムから分離している。

3. 主要な貢献

SKETCHVERIFY フレームワーク：推論時スケーリングにプログラムスケッチを適用する、ティア内（within-tier）のコストパフォーマンスポリシーを導入する。検索空間を $K$ （戦略）と $M$ （実装）に因数分解することで、弱いモデルにおけるフラットサンプリングよりも急峻な pass@1 スケーリング曲線を実現する。
コスト - 品質のパレート分析：**HumanEval+**ベンチマーク、特にベースラインの Lite モデル（貪欲法）が失敗する 19 問題の「ハードな部分集合」を再分析した厳密な分析を提供する。
- ティア内：候補数が一致した場合、スケッチングはフラットサンプリングを凌駕する。ハードな部分集合において、Lite スケッチ（ $K=2, M=5$ ）は 58% の問題を回復するのに対し、フラットサンプリング（ $N=10$ ）は 26% にとどまる。予算を 3 倍に増やしても、フラットサンプリング（ $N=50$ ）は 47% に達するのみで、より安価なスケッチ構成に依然として劣る。
- ティア間：スケッチングはモデルのアップグレードを置換するものではない。より強力なティア（例：Gemini Pro 貪欲法）は、コストと精度の両面で Lite+スケッチ構成を凌駕する。スケッチングはモデルティアのアップグレードに代わるものではなく、それを補完するものである。
カテゴリファースト分解：外観的変種ではなく構造的な多様性を生成するために不可欠な、特定のプロンプティング戦略（コーディング前に戦略名を列挙する）を提案する。
$K$ 対 $M$ のトレードオフ特性：スケーリングスイープを通じて、 $K$ と $M$ の関係が単調ではないことを示す。混合配分（例： $K=2, M=5$ ）は、純粋なフラット（ $K=1$ ）または純粋なスケッチ（ $M=1$ ）の極端なケースよりもよく機能することが多く、単に $K$ を増加させることが常に線形的な利益をもたらすわけではない（例： $K=5, M=10$ は一部の指標で $K=2, M=5$ より劣った）。
構成可能性：構造化生成が、実行ベースの選択（セマンティック・ボティング）とクリーンに構成可能であることを実証する。この手法は多様な候補プールの生成器として機能し、選択器は生成方法に依存しない。

4. 実験結果

ベンチマーク：HumanEval+（拡張テストスイート付きの 164 個の Python 問題）で評価。MBPP+ および LiveCodeBench でのクロスベンチマーク検証は今後の課題として記載されている。
モデル：思考レベルが低い Google Gemini モデルの 3 つのティア（Pro, Flash, Flash Lite）。
ハードな部分集合のパフォーマンス（Lite 貪欲法が失敗する 19 問題）：
- Lite スケッチ（ $K=10, M=10$ ）：pass@1 79%。
- Lite フラット（ $N=100$ ）：pass@1 53%。
- Lite スケッチ（ $K=2, M=5$ ）：pass@1 58%（フラット $N=50$ より低いコスト）。
- Flash/Pro 貪欲法：すべての Lite 構成を上回り、精度の主な駆動力はモデルの能力であることを確認する。
スケーリング曲線：完全な HumanEval+ セットにおいて、Lite フラットサンプリングは約 89% の pass@1 で飽和する。SKETCHVERIFY はこの天井を破り、 $K=10, M=10$ で 93% に達する。ただし、モデルがほぼ飽和している Flash や Pro においては、貪欲デコーディングと比較してスケッチングによる利益は限定的か存在しない。

5. 意義と主張

本論文は、SKETCHVERIFY を普遍的な精度向上ではなく、ティア内コストパフォーマンスポリシーとして位置づける。

実務家向けルール：より強力なモデルティアが利用可能な場合、そのティアで貪欲デコーディングを使用する。遅延時間、展開、または予算の制約により弱いモデルに制限されている場合、SKETCHVERIFY は追加の推論時計算リソースを費やす最も費用対効果の高い方法である。
メカニズム：この手法は、フラットサンプリングの確率的偶然に頼って新しいアプローチを偶然発見するのではなく、異なるアルゴリズム戦略の探索（構造的な多様性）を明示的に強制することで成功する。
限界：著者らは、単一のモデルファミリー（Gemini）への依存、単一の思考レベルへの依存、およびスケッチの品質がモデル自身の戦略分布によって制限されること（モデルが正しい戦略を考案できない場合、スケッチングもそれを生成できない）といった限界を認めている。また、スケッチ生成フェーズで約 7% のトークンオーバーヘッドがあることも指摘している。

論文は、戦略的多様性に苦しむ弱いモデルに対してスケッチングが極めて効果的である一方で、すでに能力の天井に達しているモデルや、正しい戦略がモデルの潜在知識の範囲外にある問題に対する万能薬ではないと結論付けている。