技術的概要：LLM エージェントを用いた分布認識アルゴリズム設計

問題定義

本論文は、学習対象が予測モデルではなく実行可能なソルバコードであるという点において、古典的学習理論に存在するギャップに対処する。従来の設定では、汎化性能は精度（正しさ）によって測定される。しかし、出力がアルゴリズムである場合、2 つのソルバが展開分布上でともに有効な解を返すにもかかわらず、実行時間に著しい差異が生じ得る。著者らは、実行可能手続きに対しては、汎化性能が解の質と計算コストの両方を包含しなければならないと主張する。

核心的な課題は分布認識プログラム学習である：未知の展開分布 $D$ から得られたサンプルが与えられたとき、学習者は $D$ に特化したソルバコードを返さなければならない。その目標は、単に環境中の問題クラス（例：一般的な SAT や TSP）を解決することではなく、ターゲット領域の特定の構造的規則性に最適化されたアルゴリズムを学習することである。これは、分布情報を持たないことを前提とする最悪ケースアルゴリズム設計と、分布の解析的記述を前提とする平均ケース複雑性の中間に位置する。

手法：ソルバヒントの抽象化

本論文は、サンプルから推論され、特化ソルバコードにコンパイルされる再利用可能な構造であるソルバヒントという中心的な抽象化を導入する。学習プロセスは $S \mapsto \hat{h}_S \mapsto \hat{c}_S = \text{Comp}(\hat{h}_S)$ と因数分解される。ここで：

1. $S$：未知の分布からのインスタンスのサンプル。
2. $\hat{h}_S$：ソルバヒント（例：SAT におけるバックドア集合、グラフにおける潜在分解、またはリソースボトルネックパターン）。
3. $\text{Comp}(\hat{h}_S)$：このヒントを利用するコンパイルされたソルバ。

重要なのは、この枠組みが正しさと学習された計算を分離している点である。正しさは、完全な汎用ソルバへのフォールバックによって保証されることが多い。サンプルは、将来のインスタンスにおける実行時間を削減するために、どの計算ショートカットをコンパイルするかを特定するためにのみ使用される。

LLM 合成パイプライン

著者らは、この枠組みをLLM コードエージェントを用いて具体化する。合成プロセスは、各候補に対して以下の 3 つの連続した段階を含む：

1. 仮説 ($H_c$)：エージェントは、推定される分布則の構造化された自然言語記述を提案する（例：「潜在ブール規則」または「植え付けられたパレット」）。
2. 分析 ($A_c$)：訓練時のプログラムが公開訓練サンプルからヒントを推定し、コンパクトで再利用可能な要約（経験的ヒント）を生成する。
3. ソルバ ($s_c$)：展開時のプログラムが、新しいインスタンスと回復された要約を受け取り、解を生成する。

システムは候補に対するビームサーチを採用する。検証指標（質、最適性、実行時間）に基づいて、候補を反復的に洗練、分岐、または置換する。多様性は、「多様性キー」（広範な説明クラス）を追跡することで維持され、検索が異なる構造的仮説を探索することを保証する。

理論的貢献

本論文は、2 つの領域に対して形式的な保証を提供する：

1. 固定ライブラリ上の実行時間認識 ERM：
   著者らは、ソルバライブラリ $\mathcal{C}$ が固定されている場合、経験的に最速のサンプル整合ソルバが、正しさと実行時間の両面で汎化することを証明する。具体的には、高い確率で、選択されたソルバの実行時間は、ライブラリサイズとサンプル数に依存する項まで、クラス内の最良の正しく分布特化ソルバに近づく。これは、特化がライブラリ内に存在する場合、経験的実行時間最小化が分布特化ソルバを特定するための有効な戦略であることを確立する。

2. 学習可能なヒントによる合成：
   特化が事前に列挙されていないより豊かな設定において、本論文は有限のヒント空間 $\mathcal{H}$ からのヒントの回復をモデル化する。実現可能性の仮定（真の分布が何らかの $h^* \in \mathcal{H}$ に対応する）とマージン条件（真のヒントが統計的に他のものと区別可能である）の下で、本論文は、$O(\frac{1}{\gamma^2} \log \frac{|\mathcal{H}|}{\delta})$ のサンプル数が、高い確率で正しいヒントを回復するのに十分であることを証明する。

   • 具体的な例：本論文は隠れ SAT バックドアモデルの詳細を述べる。ここで、ヒントは、固定されたときに式を扱いやすいクラスに還元する変数の集合である。理論は、顕著性統計量がサンプルからこのバックドアを識別できることを示しており、これによりコンパイルされたソルバは、フォールバックを通じて正しさを維持しつつ、展開分布上で指数関数的な高速化を達成できる。

実験結果

著者らは、7 つの問題クラス（グラフ彩色、MAXSAT、最大独立集合 (MIS)、最小支配集合 (MDS)、パッキング LP、多次元ナップサック (MDKP)、および巡回セールスマン問題 (TSP)）にわたる21 の構造化された組み合わせ最適化ターゲット分布上で、この枠組みを評価した。

主要な性能指標

• 質：合成されたソルバは、平均正規化質 0.971 を達成した。これは、平均ヒューリスティックプールに対して +0.224、最高品質のヒューリスティックに対して +0.098 の改善を表す。
• 実行時間：合成されたソルバは、ベースラインよりも著しく高速であった：
  • 品質最良のヒューリスティックより 336.9 倍 高速。
  • Gurobi（10 秒の時間制限付き）より 342.8 倍 高速。
  • 選択された時間制限付き正確バックエンドより 16.1 倍 高速。
• 外部検証 (PACE 2025)：支配集合問題の公開されたプライベートインスタンスにおいて、合成されたソルバは 100 個のすべてのグラフで有効であり、トップコンペティションソルバ（例：Fontan–Verger, Root）よりも約 2 桁 高速に実行された（ただし、中程度の質のギャップがあり、解のサイズは約 3.3% 大きかった）。

改善のメカニズム

生成されたコードの分析は、利益が計算スケールの変更に由来することを明らかにする。合成されたソルバは、しばしば環境中の指数関数的探索または汎用最適化を、低次で分布固有の計算に置き換える。例としては以下のようなものがある：

• $O^*(2^n)$ の探索を、テンプレート検証と有界修復に置き換える。
• 完全な LP 解決の代わりに、パッキング LP におけるアクティブリソースに密度ソートを使用する。
• TSP における潜在幾何構造を利用して、完全な動的計画法なしに経路を構築する。

意義と主張

本論文は、分布固有の扱いやすさへの構築的な道筋を提供すると主張する。手動設計された道筋に依存する平滑化分析やパラメータ化複雑性とは異なり、この枠組みはサンプルから直接道筋を学習する。

著者らは、学習された対象は、孤立したインスタンスのための調整されたヒューリスティックよりも、展開領域のための特化アルゴリズムに近いと強調する。「ソルバヒント」は、推論コストを償却する分布固有の構造の再利用可能な記述として機能する：サンプルに対する一度の合成コストは、インスタンスあたりのコストが低いソルバをもたらす。

この研究の範囲は控えめである：最悪ケースにおいて環境中の問題クラスを解決することを主張するものではない。代わりに、構造化された分布に対しては、サンプルが再利用可能なショートカットを明らかにし、LLM エージェントが、最先端の汎用ツールよりもはるかに正確かつ劇的に高速なソルバをコンパイルできることを実証する。この枠組みは、展開分布がサンプルを通じてアクセス可能である場合、実行時間は学習可能な性質であることを浮き彫りにする。