論文の概要: Formalize, Don't Optimize: The Heuristic Trap in LLM-Generated Combinatorial Solvers

• arxiv url: http://arxiv.org/abs/2605.12421v1
• Date: Tue, 12 May 2026 17:15:45 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-13 21:48:57.045912
• Title: Formalize, Don't Optimize: The Heuristic Trap in LLM-Generated Combinatorial Solvers
• Title（参考訳）: 形式化, 最適化しない - LLM生成のコンビナティブ・ソリューションにおけるヒューリスティックなトラップ
• Authors: Haoyu Wang, Yuliang Song, Tao Li, Zhiwei Deng, Yaqing Wang, Deepak Ramachandran, Eldan Cohen, Dan Roth,
• Abstract要約: 大規模言語モデル(LLM)は直接推論によって複雑な問題を解くのに苦慮しているため、近年のニューロシンボリックシステムは、それを実行可能な解法を合成するためにますます利用している。 我々は,100の問題をベンチマークしたCP-SynC-XL(4,577インスタンス)を導入し,ネイティブアルゴリズム検索(Python),PythonソルバAPI(Python + OR-Tools)による制約モデリング,宣言的制約モデリングという3つのコンストラクションパラダイムを評価した。
• 参考スコア（独自算出の注目度）: 52.23061619664667
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Large Language Models (LLMs) struggle to solve complex combinatorial problems through direct reasoning, so recent neuro-symbolic systems increasingly use them to synthesize executable solvers. A central design question is how the LLM should represent the solver, and whether it should also attempt to optimize search. We introduce CP-SynC-XL, a benchmark of 100 combinatorial problems (4,577 instances), and evaluate three solver-construction paradigms: native algorithmic search (Python), constraint modeling through a Python solver API (Python + OR-Tools), and declarative constraint modeling (MiniZinc + OR-Tools). We find a consistent representational divergence: Python + OR-Tools attains the highest correctness across LLMs, while MiniZinc + OR-Tools has lower absolute coverage despite using the same OR-Tools back-end. Native Python is the most likely to return a schema-valid solution that fails verification, whereas solver-backed paths preserve higher conditional fidelity. On the heuristic axis, prompting for search optimization yields only small median speed-ups (1.03-1.12x) and a strongly bimodal effect: many instances slow down, and correctness drops sharply on a long tail of problems. A paired code-level audit traces these regressions to a recurring heuristic trap. Under an efficiency-oriented prompt, the LLM may replace complete search with local approximations (Python), inject unverified bounds (Python + OR-Tools), or add redundant declarative machinery that overwhelms or over-constrains the model (MiniZinc + OR-Tools). These findings support a conservative design principle for LLM-generated combinatorial solvers: use the LLM primarily to formalize variables, constraints, and objectives for verified solvers, and separately check any LLM-authored search optimization before use.
• Abstract（参考訳）: 大規模言語モデル (LLM) は直接推論によって複雑な組合せ問題を解くのに苦労しているため、近年のニューロシンボリックシステムでは、それを実行可能な解法を合成するためにますます利用している。 中心となる設計上の問題は、LLMがどのようにソルバを表現すべきか、また探索を最適化するべきかどうかである。 我々は,100の組合せ問題(4,577インスタンス)のベンチマークであるCP-SynC-XLを導入し,ネイティブアルゴリズム検索(Python),PythonソルバAPI(Python + OR-Tools),宣言的制約モデリング(MiniZinc + OR-Tools)という3つの問題解決パラダイムを評価した。 Python + OR-Tools は LLM 全体で最高の正しさを達成でき、MiniZinc + OR-Tools は同じ OR-Tools バックエンドを使用しても絶対カバレッジが低い。 ネイティブPythonは、検証に失敗するスキーマ検証ソリューションを返す可能性が高い。 ヒューリスティック軸では、探索最適化の促進は、小さな中央値のスピードアップ(1.03-1.12x)と強いバイモーダル効果(多くのインスタンスが減速し、問題の長い尾で正確性が急激に低下する)しか得られない。 ペア化されたコードレベルの監査は、これらレグレッションを繰り返しヒューリスティックなトラップにトレースする。 効率指向のプロンプトの下では、LLMは完全探索をローカル近似(Python)に置き換えたり、未検証境界(Python + OR-Tools)を注入したり、モデルに圧倒あるいは過剰に拘束する冗長な宣言機械を追加する(MiniZinc + OR-Tools)。 これらの知見は, LLM生成の組合せ解法に対する保守的設計原則を支持し, LLMを用いて変数, 制約, 目的を定式化し, 使用前に LLM が規定する探索最適化を別々に検証する。

関連論文リスト

• Execution-Verified Reinforcement Learning for Optimization Modeling [49.171122807323634]
  実行検証学習フレームワークは、数学的プログラミング解法を決定論的で対話的な検証器として扱う。 NL4OPT, MAMO, IndustryOR, OptiBenchをグロビ, OR-Tools, COPTで行った実験では, EVOMがプロセス管理SFTに適合または優れていた。
  論文  参考訳（メタデータ） (2026-04-01T03:39:11Z)
• Online Prompt Selection for Program Synthesis [14.188804919928591]
  大規模言語モデル(LLM)は、プログラム合成の領域における印象的な機能を示している。 ユーザにとって重要な課題は、LLMがソルバの適切な選択であるかどうか、与えられた合成タスクを呼び出すのに適切なLLM、そしてそれを呼び出す正しい方法であるかどうかを特定することである。 我々は、マルチアームのバンディットアルゴリズムを用いて、どのシンボルソルバ(LLM)を選択し、与えられた報酬関数を最大化するために、即座に組み合わせてデプロイする。
  論文  参考訳（メタデータ） (2025-01-09T13:57:09Z)
• Small Language Models Fine-tuned to Coordinate Larger Language Models improve Complex Reasoning [41.03267013352519]
  大きな言語モデル(LLM)は、印象的な推論能力を示すチェーン・オブ・シントを生成するように促された。 本稿では、分解生成器を用いて複雑な問題をより少ない推論ステップを必要とするサブプロブレムに分解するDaSLaMを紹介する。 本稿では,DaSLaMがスケール関数としての解の能力に制限されないことを示す。
  論文  参考訳（メタデータ） (2023-10-21T15:23:20Z)
• ALGO: Synthesizing Algorithmic Programs with LLM-Generated Oracle Verifiers [60.6418431624873]
  大きな言語モデル(LLM)は、機能記述からコードを実装するのに優れているが、アルゴリズムの問題に悩まされている。 我々は,アルゴリズムプログラムを LLM 生成 Oracle で合成するフレームワーク ALGO を提案し,その生成をガイドし,その正確性を検証する。 実験の結果,ALGOを装着すると,Codexモデルよりも8倍,CodeTよりも2.6倍の1サブミッションパス率が得られることがわかった。
  論文  参考訳（メタデータ） (2023-05-24T00:10:15Z)
• SatLM: Satisfiability-Aided Language Models Using Declarative Prompting [68.40726892904286]
  本研究では,大規模言語モデル (LLM) の推論能力を向上させるために,新しい満足度支援言語モデリング (SatLM) 手法を提案する。 我々はLLMを用いて命令型プログラムではなく宣言型タスク仕様を生成し、既製の自動定理証明器を利用して最終解を導出する。 我々はSATLMを8つの異なるデータセット上で評価し、命令パラダイムにおいてプログラム支援されたLMよりも一貫して優れていることを示す。
  論文  参考訳（メタデータ） (2023-05-16T17:55:51Z)
• Large Language Models are Strong Zero-Shot Retriever [89.16756291653371]
  ゼロショットシナリオにおける大規模検索に大規模言語モデル(LLM)を適用するための簡単な手法を提案する。 我々の手法であるRetriever(LameR)は,LLM以外のニューラルモデルに基づいて構築された言語モデルである。
  論文  参考訳（メタデータ） (2023-04-27T14:45:55Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。