技術的概要：LLM に基づくコード生成における不確実性定量化のための RISCOSET

問題定義

大規模言語モデル（LLM）はコード生成にますます利用されるようになっているが、ハルシネーションや有毒・偏った出力の生成という欠点があり、高リスクなアプリケーションへの展開を制限している。コンフォーマル予測（CP）は、分布フリーの保証を伴う不確実性定量化の枠組みを提供するが、これをコードのような構造化生成タスクに適応させることは困難である。

既存のアプローチ、例えばコードに対する PAC（Probably Approximately Correct）予測集合（Khakhar et al., 2023）は、2 つの重要な限界に直面している：

1. 単調性制約: これらはリスクと予測集合のサイズに関する強い単調性の仮定に依存している。これは許容される部分プログラムの空間を制限し、しばしばコードノードを過剰に除去する非最適解をもたらす。
2. 単一ラベル仮定: これらは単一ラベル分類のために設計されている。しかし、コード生成は本質的にマルチラベル問題であり、構文上異なる複数のプログラムが同一の正しい意味論を持つ可能性がある。既存の手法はこの多重性を収容できず、候補空間を著しく制限している。

手法：RISCOSET

著者は、LLM に基づくコード生成のためのリスク制御予測集合を構築する手法としてRISCOSETを提案する。これは、問題をマルチラベル分類タスクとして再定義し、Learn Then Test (LTT) 枠組み（Angelopoulos et al., 2025）を活用するものである。

中核的構成要素

1. マルチラベル再定義と構造化リスク:
   単調性を強制する代わりに、RISCOSET は意味的正しさに基づく構造化リスク関数を定義する。ある入力に対して、拡張ラベル集合 $\tilde{Y}$ から少なくとも 1 つの正しいプログラムを含む予測集合（部分プログラムまたは AST 部分木として表現される）を生成することが目標である。経験的リスクは、予測集合が正しいプログラムの集合と交差しない較正インスタンスの割合として定義される。

2. 部分プログラムの最適化:
   予測集合を生成するために、この手法は生成されたコードの抽象構文木（AST）からノードを剪定する最適化問題を解く。

   • 目的: 残存する部分プログラムの総不確実性（負の対数確率）が閾値 $\lambda$ を超えないことを保証しつつ、可能な限り多くのノードを保持する。
   • 制約: 解は木接続性（親が除去された場合、子も除去されなければならない）および許容される部分木除去の回数制限 ($t_{max}$) を満たさなければならない。重要なのは、この最適化が PAC 手法に見られる厳密な単調性制約を除去し、より大きな実行可能なラベル空間を可能にすることである。

3. 多重仮説検定（LTT）:
   RISCOSET は、リスクを制御する最適なパラメータ $\hat{\lambda}$ を選択するために LTT 枠組みを採用する。

   • $\lambda$ の選択を多重仮説検定問題として扱う。
   • 候補となる $\lambda$ の集合に対して、経験的構造化リスクに基づいて $p$ 値を計算する。
   • 家族ごとの誤差率（FWER）制御アルゴリズムを用いて、リスクがユーザー指定の許容値 $\alpha$ 未満に高確信度 ($1-\delta$) で維持されることを保証する有効なパラメータ集合 $\Lambda_{valid}$ を特定する。

4. 選択的実行戦略:
   コード生成はマルチラベルであるため、較正プロセスには複数の候補プログラムをサンプリングし、テストケース実行を通じて検証する必要があり、計算コストが高い。これを緩和するため、RISCOSET は選択的実行戦略を導入する：

   • 不確実性スコア（例えば、パープレキシティ）を使用して、どのサンプリングされたプログラムのテスト実行が必要かを決定する。
   • 不確実性が低いプログラムは実行なしで正しいものとして受け入れられ、不確実性が高いプログラムは検証される。
   • この戦略は、重要度サンプリングとホエフディングの不等式を用いて誤差の上限を推定し、ラベル誤り率を制御された境界 $\epsilon$ 内に維持しつつ、計算コストを大幅に削減する。

主要な貢献

1. RISCOSET 枠組み: 構造化コード生成への LTT 枠組みの初適用。PAC ベースのアプローチよりも弱い制約を持つマルチラベル問題として予測集合構築を再定義する。
2. 構造化リスク最適化: 制限的な単調性の仮定から解放され、リスク制御の保証を満たしながら保持される情報を最大化する、部分プログラム（AST 部分木）生成のための新規最適化定式化。
3. 効率的な較正: ラベル検証の計算コストとリスク制御のトレードオフをバランスさせる選択的実行戦略。非漸近的誤差境界によって支えられている。
4. 経験的検証: 3 つの LLM（Deepseek-Coder, Qwen2.5-Coder, Llama3.1）と 3 つのデータセット（HumanEval, MBPP, APPS）にわたる包括的な実験により、手法の有効性を実証。

実験結果

著者は、PAC 予測集合アプローチや貪欲な変種を含む最先端のベースラインに対して RISCOSET を評価した。

• ノード除去の削減: RISCOSET は、同じレベルのリスク制御を維持しながら、ベースラインと比較して除去される AST ノードの数を大幅に削減した。例えば、MBPP データセットで $\alpha=0.15$ の場合、この手法は最良の競合他社と比較してコード除去を**24.5%**削減した。
• カバレッジ保証: 構築された予測集合は、一貫して目標境界 ($1-\alpha$) を超えるカバレッジ率を達成し、理論的なリスク制御保証を検証した。
• モデルのスケーラビリティ: この手法は、コード特化モデル（Qwen2.5-Coder）と汎用モデル（Llama3.1）の両方で良好に機能し、より強力な生成モデルほど性能が向上することを示した。
• 選択的実行の効率性: 選択的実行戦略は、テストケース実行を必要とするプログラムの割合を効果的に削減した（例えば、ラベル誤り率 $\epsilon=0.1$ で約 30% のプログラムの実行を回避）一方、カバレッジを目標閾値以上に維持した。

意義と主張

本論文は、構造化コード生成タスクに LTT 枠組みを導入した最初の研究であると主張している。その主な意義は、既存の PAC ベースの手法の限界に対処することにある：

• 強い単調性の仮定の必要性を排除し、候補プログラムの空間を拡大して不要なコード除去を削減する。
• コード生成のマルチラベル性（単一のタスクに対する複数の有効な解）を自然に収容する。
• コードのような構造化ドメインでは成立しない独立性の仮定に依存することなく、生成されたコード集合の正しさに対する厳密な統計的保証を提供する。

著者は、焦点はコード生成にあるが、提案された手法は不確実性定量化が重要な他の構造化予測問題にも適応可能であると結論付けている。較正段階の計算オーバーヘッドを認める一方で、選択的実行戦略がこのコストを効果的に軽減することを強調している。