確率的プログラム・オブ・ソート

arXiv cs.CL / 2026/4/21

📰 ニュースIdeas & Deep AnalysisModels & Research

共有:

要点

この論文は、LLMを用いたコード生成や推論で多数のサンプルが必要な場合に生じる高いGPUコスト（n個のプログラムをサンプリングするのにn回の高コスト生成が必要）という課題に取り組みます。
「probabilistic programs of thought（確率的プログラム・オブ・ソート）」と呼ばれるテスト時の枠組みを提案し、生成されたプログラムに付随する次トークン確率を利用してコンパクトな確率的プログラムを構築します。
確率的プログラムは指数的に多くの決定論的プログラムを表現できるため、少ないLLM生成回数でより多様な候補を得られます。
確率的プログラム内での推論は、LLMを繰り返しサンプリングするより計算が安価なため、追加のGPU計算なし（CPUオーバーヘッドも小さめ）で新しいプログラムをサンプル可能にします。
コード生成・コード理解・数学的推論のベンチマークで、LLM生成回数を減らしながら性能が向上することを報告しています。

概要: LLMは、構造化された出力を生成する必要があるコード生成や数学的推論のタスクで広く用いられています。LLMは、コードについて推論する必要がある場合もあれば、与えられた仕様に対するコードを生成する必要がある場合もあり、あるいは「思考」のためのプログラムを用いて推論する必要があります。コード生成の典型的なアプローチは、モデルにプロンプトを与えて、適切なプログラムが得られるまでサンプルを生成することです。しかし、この過程で言語モデルから $n$ 個のプログラムをサンプリングするには、GPUの計算負荷が大きい生成を $n$ 回行う必要があり、 $n$ の値が大きくなるほど費用が法外に高くなります。本研究では、生成されるプログラムそのものの中にLLMの分布を直接反映させることで、この制約に対処します。提案するのは、少ないLLM生成回数でモデルからより多くのサンプルを得るための、新しいテスト時フレームワークで、これを「確率的プログラム・オブ・ソート」と呼びます。モデルによって生成されたプログラムと、その次トークン確率が与えられたとき、指数関数的に多数の決定論的プログラムをコンパクトに表現する確率的プログラムを構築します。この確率的プログラム上で確率的推論を行うことははるかに安価であるため、当該アプローチでは追加のGPU計算を一切行わず、CPUのオーバーヘッドもわずかで、新しいプログラムをサンプリングできます。本アプローチをコード生成、コード理解、数学的推論のベンチマークに適用し、LLMからの生成回数をより少なくしつつ性能が向上することを報告します。