技術的サマリー：最適化ではなく形式化を：LLM 生成の組合せソルバーにおけるヒューリスティックの罠

問題定義

大規模言語モデル（LLM）は、大規模な探索空間のナビゲーションと長期的な制約にわたるグローバルな整合性の維持に内在する「推論のボトルネック」のため、直接的な自己回帰的推論を通じて複雑な組合せ問題を解くことに苦慮しています。最近の神経記号アプローチは、LLM に実行可能なソルバーを合成させることでこれを緩和しようとしていますが、2 つの重要な設計上の問いは未解決のままです：

1. 表現： LLM はソルバーをどのように表現すべきか？ネイティブなアルゴリズム的アプローチ（Python）は、宣言的モデリング（MiniZinc）やソルバー API 統合（Python + OR-Tools）に優れているか？
2. 最適化： LLM に探索プロセスの能動的な最適化（ヒューリスティック、枝刈り、または境界値などを通じて）を促すべきか、それとも検証済みのバックエンドに対して問題を厳密に形式化させるべきか？

先行研究は、これらの設定を個別に、または問題レベルの集計で評価することが多く、インスタンスレベルの結果を正しさ、スキーマの有効性、忠実度に分解して評価できていません。さらに、効率指向のプロンプトが生成されたソルバーの信頼性に与える影響は、体系的に監査されていません。

手法

著者は、100 の多様な制約充足問題（CSP）と制約最適化問題（COP）を含み、合計 4,577 のパラメータ化インスタンスを含む CP-SynC データセットを拡張したベンチマーク CP-SynC-XL を導入しました。本研究は、3 つのソルバー構築パラダイムにおいて、3 つの最先端 LLM（GPT-5.3-CODEX、GEMINI 3.1 PRO、DEEPSEEK-V3.2）を評価します：

1. ネイティブアルゴリズム的探索（Python）： LLM は標準ライブラリのみを使用してスタンドアロンの Python アルゴリズムを生成し、完全な探索手順（例：分枝限定法、動的計画法）を設計します。
2. Python API による制約モデリング（Python + OR-Tools）： LLM は OR-Tools CP-SAT Python API を使用して変数、制約、目的関数をエンコードし、探索をソルバーに委譲します。
3. 宣言的制約モデリング（MiniZinc + OR-Tools）： LLM は MiniZinc モデルを生成し、それを同じ OR-Tools CP-SAT バックエンドでコンパイルして解きます。

本研究は、正しさのみを要求するベースラインプロンプトと、よりtightな境界値、枝刈り、または探索注釈などの効率指向設計を明示的に要求するヒューリスティックプロンプトを比較する制御された因子実験デザインを採用しています。

評価パイプラインには以下が含まれます：

• 洗練プロトコル： クラッシュ、タイムアウト、フォーマットエラーなどの失敗した実行を LLM にフィードバックする、4 ラウンドの反復的洗練ループ。
• 指標：
  • Provided（提供）： スキーマに準拠した出力を返すインスタンスの割合。
  • Correct（正解）： 提供された出力のうち、参照検証器を通過するものの割合。
  • Fidelity（忠実度）： Correct/Provided の比率（返された解のうち実際に有効なものの割合）。
• コードレベル監査： 特定の失敗モードとコードパターンを特定するための、ベースライン対ヒューリスティックソルバーのペア分析。

主要な貢献

1. CP-SynC-XL ベンチマーク

著者は、条件付き忠実度を測定するために提供された出力と検証済みの正解を分離し、インスタンスレベルで LLM 合成ソルバーを評価するために設計された大規模ベンチマーク（4,577 インスタンス）を導入しました。

2. 表現の分岐

本研究は、基盤となるソルバーバックエンド（OR-Tools CP-SAT）が同一であっても、モデリング表面に基づいてソルバーのパフォーマンスに著しい分岐があることを明らかにしました：

• Python + OR-Tools は、すべての LLM において絶対的な正解率を最も高く達成しました。
• MiniZinc + OR-Tools は、同じバックエンドを有しているにもかかわらず、絶対的なカバレッジが低く（より多くの「解なし」タイムアウト）、ソルバーの能力ではなく、LLM の宣言的表面に対する流暢さにボトルネックがあることを示唆しています。
• ネイティブ Python は、「サイレントな失敗」（検証に失敗するスキーマ有効な解を返す）の割合が最も高く、LLM がゼロから完全かつ健全な探索アルゴリズムを設計することに苦慮していることを示しています。

3. ヒューリスティックの罠

本論文は、LLM に探索の最適化を促すことが信頼性の低い結果をもたらす「ヒューリスティックの罠」を特定しました：

• わずかな利益、高いリスク： ヒューリスティックプロンプトはわずかな中央値の速度向上（1.03–1.12 倍）しか生み出さず、強い二峰性の効果を引き起こします。一部のインスタンスは高速化しますが、多くの他のインスタンスは低速化し、正解率は長いテールを持つ問題群で急激に低下します。
• 6 つの失敗モード： コードレベル監査により、ヒューリスティックプロンプトによって引き起こされる 6 つのパラダイム固有の失敗モードが特定されました：
  • 未検証の境界値（Python + OR-Tools）： LLM が定理ではない「tight」な境界値を注入し、実行不可能性を引き起こす。
  • 弱まった伝播（Python + OR-Tools）： ソルバーの伝播エンジンを麻痺させる意味的に等価な書き換え（例：Big-M）。
  • ハードシード（Python + OR-Tools）： ヒューリスティック候補をハード制約に変換し、実行可能領域を除去する。
  • 完全性の喪失（Python）： 完全な探索を不完全な局所探索や反復キャップに置き換える。
  • COP→SAT の崩壊（MiniZinc）： 最適値を誤って仮定し、最適化を充足問題に変換する。
  • 冗長な機構（MiniZinc）： ソルバーの平坦化プロセスを圧倒する過剰な補助制約を追加する。

結果

• 正解率の順位： Python + OR-Tools > Python ≳ MiniZinc + OR-Tools。探索を検証済みのバックエンド（CP-SAT）に委譲することは、ネイティブなアルゴリズム的デザインを大幅に凌駕します。
• 忠実度の順位： MiniZinc + OR-Tools > Python + OR-Tools > Python。解が提供された場合、MiniZinc モデルは最も正解である可能性が高く（条件付き忠実度が最高）、言語の型システムと Well-formedness チェックがソルバー実行前に多くのエンコーディングエラーをフィルタリングするためです。ネイティブ Python は最も忠実度が低く、自信を持って誤った解を返すことがよくあります。
• ヒューリスティックの影響： 強力な LLM（GPT-5.3-CODEX、GEMINI 3.1 PRO）において、ヒューリスティックプロンプトはわずかで一貫性のない利益（±3.6 パーセントポイント）をもたらします。一方、弱い LLM（DEEPSEEK-V3.2）では、ヒューリスティックプロンプトは顕著な劣化を引き起こします（例：Python + OR-Tools において正解率が -7.4 ポイント低下）。
• 失敗分析： 支配的なベースラインの失敗モードは UNSAT（ソルバーが参照検証器が拒否する解を返す）であり、主に自然言語から形式言語への誤翻訳（制約の削除、出力スキーマの誤解釈など）によって引き起こされます。ヒューリスティックプロンプトは、未検証の境界値の導入とモデルの過剰な制約化によってこれを悪化させます。

意義と設計原則

本論文は、LLM 生成の組合せソルバーにおける主要なボトルネックは、基盤となるソルバーの能力ではなく、モデリング表面の流暢さであると主張しています。この知見は、以下の保守的な設計原則を支持します：

「最適化ではなく、形式化を。」

LLM は主に、検証済みのソルバーに対して変数、制約、目的関数を形式化するために使用されるべきです。LLM に探索最適化（ヒューリスティック、境界値、枝刈り戦略など）を生成させる試みは懐疑的に扱うべきです。本論文は、LLM によるいかなる探索最適化も、使用前に独立して検証されなければならないと結論付けています。「ヒューリスティックの罠」は頻繁に、正解率と忠実度の両方を低下させる未検証の境界値やアルゴリズム的置換を導入するためです。最も信頼性の高い戦略は、LLM を形式化インターフェースの近くに保ち、探索についてはソルバーのネイティブな機構に依存することです。