💬 NLP

Probabilistic Programs of Thought

LLM によるコード生成や推論タスクにおいて、生成されたプログラムと次のトークンの確率分布から「確率的プログラム」を構築し、追加の GPU 計算なしで指数関数的に多くの候補プログラムを効率的にサンプリングすることで、計算コストを大幅に削減しつつ性能を向上させる新しいテスト時フレームワーク「Probabilistic Programs of Thought」を提案する。

原著者： Poorva Garg, Renato Lui Geh, Daniel Israel, Todd Millstein, Kyle Richardson, Guy Van den Broeck

公開日 2026-04-21

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

CC BY 4.0

原著者： Poorva Garg, Renato Lui Geh, Daniel Israel, Todd Millstein, Kyle Richardson, Guy Van den Broeck

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

この論文は、**「AI（大規模言語モデル）がコードや数学の問題を解くとき、一度の失敗で諦めずに、その『失敗した答え』から無数の『新しい可能性』を無料で引き出せる方法」**を提案しています。

この新しい方法を**「確率的思考のプログラム（Probabilistic Programs of Thought: PPoT）」**と呼びます。

難しい専門用語を抜きにして、身近な例え話を使って説明しましょう。

🍳 料理の例え：「レシピの修正」

想像してください。あなたが一流の料理人（AI）に、「美味しいパスタを作ってください」と頼みました。

従来の方法（今の主流）：
料理人が「パスタのレシピ」を一つ書いてくれました。
- 料理：「塩を大さじ 3 杯入れましょう」
- あなた：「えっ、大さじ 3 杯だと塩辛すぎるよ！」と試食して失敗。
- 対策： 料理人に「もう一度、大さじ 3 杯じゃないレシピを書いてください」と頼みます。
- 問題点： 料理人がレシピを書くのは、非常にエネルギー（GPU 計算コスト）を使います。10 回も 20 回も「書き直し」を頼むと、料理人の疲弊とコストが爆発的に増えます。
この論文の新しい方法（PPoT）：
料理人が「パスタのレシピ」を一つ書いてくれました。
- 料理：「塩を大さじ 3 杯入れましょう」
- あなた：「大さじ 3 杯は多いね。でも、料理人が『3 』と書く直前に、頭の中で『2 』や『1』も一瞬考えていたんだな（確率分布）と気づく。」
- 対策： 料理人に「書き直し」を頼まずに、**「そのレシピの『3』という数字だけを、AI が考えていた『1』から『10』までの可能性として変えてみよう」**と、自分たちでシミュレーションします。
- 結果： 料理人（AI）は一度しか動いていませんが、あなたの手元で「大さじ 1 杯版」「大さじ 2 杯版」「大さじ 4 杯版」など、何十通りものレシピが瞬時に作られました。
- メリット： 料理人への負担はゼロ。コストはほぼかかりません。

🔍 この技術がどうやって動くのか？

この論文の核心は、**「AI が出力したコード（答え）を、単なる文字の羅列ではなく、『確率の箱』として捉え直す」**という発想にあります。

AI の思考プロセス：
AI が「3」という数字を出力する瞬間、実は「3」になる確率が 80%、「2」になる確率が 15%、「4」になる確率が 5% といった**「確率の分布」**を持っています。
従来のやり方：
AI はその確率の箱から「3」を一つだけ取り出して、確定させてしまいます。その後、間違っていたら、また最初から箱を開けて「2」を取り出そうとします（これがコストがかかる）。
PPoT のやり方：
一度取り出した「3」を、**「3 になる可能性が高いけど、実は 2 や 4 かもしれない」という「変数（箱）」**として扱います。
その「箱」を、AI の計算機（GPU）を使わずに、普通のパソコン（CPU）で軽く揺さぶって、中から何百もの「もしも」の答えを抽出します。

🎲 なぜこれがすごいのか？

コストが激安：
AI（料理人）を呼び出すのは 1 回だけ。その後の「もしも」のシミュレーションは、普通のパソコンで瞬時に行えます。
精度が向上：
「たまたま 1 回で正解が出る」のを待つ必要がなくなります。「1 回で失敗した答え」から、確率的に正しい答えを「掘り起こす」ことができるため、正解率が大幅に上がります。
応用範囲：
数学の問題、プログラミングのバグ修正、図の作成など、AI が「コード」や「構造化された答え」を出すあらゆる場面で使えます。

💡 まとめ

この論文は、**「AI に『正解』を何回も無理やり書かせようとするのではなく、AI が『一度書いた答え』の中に隠れている『正解のヒント（確率）』を、人間が賢く引き出して利用しよう」**という提案です。

まるで、**「失敗した料理のレシピから、調味料の量だけを微調整して、何十種類も美味しいバリエーションを無料で作り出す魔法」**のような技術なのです。これにより、AI を使う際の莫大なコストを減らしながら、より高い精度を実現できるようになります。

論文「Probabilistic Programs of Thought (PPoT)」の技術的サマリー

この論文は、大規模言語モデル（LLM）によるコード生成や数学的推論タスクにおいて、生成されたプログラム内の確率分布を明示的に活用し、GPU 計算コストを増やすことなく高品質なサンプルを多数生成する新しいフレームワーク**「Probabilistic Programs of Thought (PPoT)」**を提案しています。

以下に、問題定義、手法、主要な貢献、実験結果、および意義について詳細をまとめます。

1. 背景と問題定義

背景

LLM はコード生成や数学的推論（Programs of Thought）において、構造化された出力を生成するために広く利用されています。従来のアプローチでは、モデルにプロンプトを与え、正しいプログラムが得られるまで複数のサンプルを生成・実行・検証する「サンプル - 実行 - 検証」ループ（Best-of-n やビームサーチなど）が一般的です。

課題

この従来の手法には重大なボトルネックがあります。

計算コストの高さ: $n$ 個のプログラムを生成するには、LLM に対して $n$ 回の GPU 集約的な生成（フォワードパス）が必要です。
スケーラビリティの欠如: 大規模モデルや多数のサンプル（ $n$ が大きい場合）を必要とする場合、このプロセスは計算リソース的に実行不可能（prohibitively expensive）になります。
情報の廃棄: 従来の生成プロセスでは、トークン生成時に得られる「次のトークンの確率分布（next-token probabilities）」は、一度サンプリングが完了すると捨てられてしまいます。

2. 提案手法：Probabilistic Programs of Thought (PPoT)

PPoT は、LLM が生成した単一の決定論的プログラム（deterministic program）を、LLM の確率分布を内包する**確率的プログラム（Probabilistic Program）**に変換し、その上で推論を行うことで、追加の GPU 計算なしに多数の代替サンプルを生成する手法です。

核心的なアイデア

LLM を確率的プログラムとして解釈する:
LLM の生成プロセス自体を、トークンごとのカテゴリカル分布からなる確率的プログラムとして定義します。
トークンの確率変数化:
生成されたプログラム内の特定のトークン（数字、演算子、比較演算子など）を、LLM の次トークン確率に基づいた**確率変数（Random Variables）**として扱います。
- 例：return 0 + 2 という出力で、0 が誤っている場合、この 0 を確率変数 $X \sim \text{categorical}(P_M)$ として扱います。
確率的プログラムの構築:
元のプログラムを、これらの確率変数を含む確率的プログラムに変換します。これにより、1 つのプログラムが指数関数的な数の決定論的プログラム（候補）をコンパクトに表現することになります。
効率的なサンプリング:
構築された確率的プログラムから、CPU 上で安価にサンプリングを行います。これにより、LLM への追加の呼び出し（GPU 計算）を一切行わずに、多数の新しいプログラム候補を生成できます。

アルゴリズムの概要

LLM 生成: プロンプトに対して LLM から 1 つのプログラムを生成し、その際の次トークン確率を保持する。
トークン分析: どのトークンを確率変数として扱うか（例：数値、演算子）を決定する。
コンパイル: 選択されたトークンを確率変数に変換し、確率的プログラムを構築する。
再サンプリング: 構築された確率的プログラムから、元の LLM 出力とは異なる（または同じだが確率的にサンプリングされた）多数のプログラムを生成する。
実行・検証: 生成されたすべてのプログラムを実行し、検証器（Verifier）でスコアリングする。

理論的保証

独立性仮定: 再サンプリングされたトークンが、その後のトークンに依存しないという仮定（Assumption 1）の下で、PPoT によって生成されるサンプルの経験分布は、元の LLM 分布に収束することが証明されています。
計算効率: 確率的推論は LLM のフォワードパスに比べて CPU 上で非常に安価に実行可能です。

3. 主要な貢献

PPoT の提案: 構造化出力生成のための新しいデコーディング手法「Probabilistic Programs of Thought」を提案。これにより、LLM 呼び出し回数を増やさずに効率的に多数のサンプルを生成可能にしました。
分布の正当性（Distributional Soundness）: 特定の独立性仮定の下で、PPoT が LLM の分布に対して分布論理的に正当であることを理論的に示しました。
実証的な性能向上: GSM8k（数学的推論）、Plot2Code（コード生成）、CRUXEval（構造化出力生成）の 3 つのベンチマークにおいて、Qwen2.5 シリーズ（0.5B, 3B, 7B）を用いた実験で、LLM 生成回数を増やさずに Pass@k パフォーマンスを最大 7% 向上させることを実証しました。
計算効率の定量的評価: PPoT を使用することで、同等の精度を達成するために必要な追加の LLM サンプル数が大幅に減少することを示しました（例：20 個の LLM サンプルに 20 個の PPoT サンプルを加えることは、約 39 個の追加 LLM サンプルに相当する効果をもたらす）。

4. 実験結果

評価ベンチマーク

GSM8k: 数学的 word problem。
Plot2Code: 科学プロットから matplotlib コードを生成するタスク。
CRUXEval: Python 関数とその出力から、入力値を推論するタスク。

主な結果

精度の向上: どのモデルサイズ（0.5B〜7B）およびタスクにおいても、PPoT を適用することで精度が向上しました。特に、GSM8k において、LLM 生成数 $k=20$ の場合、PPoT サンプルを 5 つ追加するだけで精度が 2〜7% 向上しました。
計算コストの削減:
- 図 5 に示されるように、PPoT のコンパイルとサンプリングにかかる時間は、LLM の推論時間に比べて無視できるほど短く、実質的に「ゼロコスト」で追加サンプルを得ることができます。
- 図 6 に示されるように、PPoT を使用することで、LLM 呼び出し回数を大幅に削減しながら同等の精度を達成できます（例：20 個の LLM サンプル + 20 個の PPoT サンプルは、LLM 単独では約 59 個のサンプルが必要になる精度に相当）。
誤り訂正能力: 図 4 や付録 F の例示のように、LLM が生成したコードにランタイムエラーや論理的ミス（数字の誤り、演算子の誤りなど）があった場合、PPoT は確率分布に基づいて正しい値をサンプリングし、エラーを修正して正解を導き出すことができました。

5. 意義と将来展望

計算リソースの最適化: 大規模モデルの推論コストが懸念される現在、GPU 負荷を増やすことなく推論性能を向上させる画期的なアプローチです。
確率的推論の新たな応用: 生成されたコードを単なるテキストではなく、確率的モデルとして扱うという新しい視点を提供しました。
拡張性: 現在の研究では数字や演算子に限定されていますが、将来的には制御フロー構造やサブ式全体を確率変数として扱うことで、より複雑な確率的推論が可能になると期待されます。
他のタスクへの応用: 期待値の計算や条件付きサンプリングなど、確率的クエリに対する LLM の応答を改善する基盤技術として、コード生成以外の分野でも応用が期待されます。

結論

PPoT は、LLM の生成プロセスに内在する確率的不確実性を、確率的プログラミングの枠組みで明示的に利用することで、**「少ない LLM 呼び出し回数で、より多くの候補を探索し、高い精度を達成する」**ことを可能にしました。これは、LLM 推論の効率化とコスト削減において重要なマイルストーンとなる研究です。