論文の概要: Infeasibility Aware Large Language Models for Combinatorial Optimization

• arxiv url: http://arxiv.org/abs/2604.01455v1
• Date: Wed, 01 Apr 2026 23:02:44 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-03 14:21:10.094379
• Title: Infeasibility Aware Large Language Models for Combinatorial Optimization
• Title（参考訳）: 組合せ最適化のための大規模言語モデルの実現可能性
• Authors: Yakun Wang, Min Chen, Zeguan Wu, Junyu Liu, Sitao Zhang, Zhenwen Shao,
• Abstract要約: 本稿では,認証データセットの構築,教師付き微調整,LLM支援下流探索を併用した不実現性認識フレームワークを提案する。 実験の結果、我々の微調整されたモデルではGPT-5.2よりも30%精度が向上し、一方LLM誘導の暖機は最大で2倍のスピードアップを提供することがわかった。
• 参考スコア（独自算出の注目度）: 12.884852956582762
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Large language models (LLMs) are increasingly explored for NP-hard combinatorial optimization problems, but most existing methods emphasize feasible-instance solution generation and do not explicitly address infeasibility detection. We propose an infeasibility-aware framework that combines certifiable dataset construction, supervised fine-tuning, and LLM-assisted downstream search. For the minor-embedding problem, we introduce a new mathematical programming formulation together with provable zero-phase infeasibility screening, which enables scalable construction of training instances labeled either as feasible with structured certificates or as certifiably infeasible. Using training data generated through this exact optimization pipeline, we show that an 8B-parameter LLM can be fine-tuned to jointly perform solution generation and infeasibility detection. We further utilize LLM outputs as warm starts for downstream local search, providing a practical way to accelerate optimization even when the LLM outputs are imperfect. Experiments show that our fine-tuned model improves overall accuracy by up to 30\% over GPT-5.2; meanwhile LLM-guided warm starts provide up to $2\times$ speedup compared with starting from scratch in downstream local search.
• Abstract（参考訳）: 大規模言語モデル (LLMs) はNPハードな組合せ最適化問題に対して研究が進んでいるが、既存のほとんどの手法は実現不可能なソリューション生成を強調しており、実現不可能な検出に明示的に対処していない。 本稿では,認証データセットの構築,教師付き微調整,LLM支援下流探索を併用した不実現性認識フレームワークを提案する。 そこで本研究では,ゼロフェーズ不実現性スクリーニングと数学プログラミングの新たな定式化を導入し,構造化証明書とラベル付けされたトレーニングインスタンスのスケーラブルな構築を可能にする。 この厳密な最適化パイプラインから生成されたトレーニングデータを用いて、8BパラメータLPMを微調整して、ソリューション生成と不実現性検出を共同で行うことができることを示す。 さらに,LLM出力が不完全である場合でも,下流局所探索の温暖化開始としてLLM出力を有効活用し,最適化を高速化する実用的な方法を提供する。 実験により、我々の微調整モデルでは、GPT-5.2よりも最大で30倍の精度が向上し、一方LLM誘導ウォームは、下流のローカルサーチのスクラッチから始めるよりも最大2倍のスピードアップを提供することが示された。

関連論文リスト

• AsynDBT: Asynchronous Distributed Bilevel Tuning for efficient In-Context Learning with Large Language Models [4.4866154758274375]
  In-context Learning (ICL) は、LLMが入力内で提供される例を使って新しいタスクに適応できる有望なパラダイムとして登場した。 ICLを組み込んだ以前のFLアプローチは、重度のストラグラー問題と、異種非同一データに関連する課題に悩まされてきた。 本稿では,LLMからのフィードバックに基づいて,文脈内学習サンプルの最適化とフラグメントのプロンプトを行う非同期分散バイレベルチューニング(AsynDBT)アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2026-02-06T13:07:49Z)
• Can Prompt Difficulty be Online Predicted for Accelerating RL Finetuning of Reasoning Models? [65.18157595903124]
  本研究では任意のプロンプトの反復的近似評価について検討する。 Model Predictive Prompt Selection (MoPPS)はベイズにおけるリスク予測フレームワークである。 MoPPSは迅速な困難を確実に予測し、ロールアウトを大幅に削減したトレーニングを加速する。
  論文  参考訳（メタデータ） (2025-07-07T03:20:52Z)
• PEARL: Towards Permutation-Resilient LLMs [29.55886726376898]
  大規模言語モデル(LLM)のインコンテキスト学習(ICL)機能により、提供されたデモを使って困難なタスクを実行できる。 ICLはデモの順序に非常に敏感であり、予測の不安定性につながる。 本稿では,この脆弱性を利用してLLaMA-3の80%近い成功率を達成する自然攻撃を設計できることを示す。
  論文  参考訳（メタデータ） (2025-02-20T15:07:02Z)
• Rational Tuning of LLM Cascades via Probabilistic Modeling [0.9208007322096532]
  大規模言語モデル(LLM)の連立性能分布の確率的モデルを提案する。 ベイズ最適化を用いた信頼しきい値の選択と比較すると、マルコフパラメトリックコプラモデルの方がエラーコストのトレードオフに有利である。 異なるLLMの誤差率間の相互作用に関する我々のフレームワークの帰納的仮定は、サンプル効率を高める。
  論文  参考訳（メタデータ） (2025-01-16T07:58:33Z)
• In-context Demonstration Matters: On Prompt Optimization for Pseudo-Supervision Refinement [71.60563181678323]
  大規模言語モデル(LLM)は様々なタスクで大きな成功を収めており、生成品質をさらに向上させるためには微調整が必要である場合もある。 これらの課題に対処する直接的な解決策は、教師なしの下流タスクから高信頼のデータを生成することである。 本稿では,プロンプトと全体的な擬似スーパービジョンを両立させる新しい手法,擬似教師付きデモアライメント・アライメント・アライメント・プロンプト・最適化(PAPO)アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2024-10-04T03:39:28Z)
• Entropy Law: The Story Behind Data Compression and LLM Performance [115.70395740286422]
  モデル性能はトレーニングデータの圧縮比と負の相関関係にあり,トレーニング損失が小さくなるのが普通である。 エントロピー法則の知見に基づいて, 極めて効率的で普遍的なデータ選択法を提案する。 また,モデルトレーニング開始時の潜在的な性能リスクを検出するエントロピー法則の興味深い応用を提案する。
  論文  参考訳（メタデータ） (2024-07-09T08:14:29Z)
• FederatedScope-LLM: A Comprehensive Package for Fine-tuning Large Language Models in Federated Learning [70.38817963253034]
  本稿では, ファインチューニング LLM のこれらの課題について論じ, 本パッケージ FS-LLM を主な貢献として紹介する。 我々は、FLシナリオにおける将来の拡張のために、包括的フェデレーションパラメータ効率の良い微調整アルゴリズムの実装と汎用プログラミングインタフェースを提供する。 本研究では, FS-LLM の有効性を検証し, FL 設定におけるパラメータ効率の高いパラメータ調整アルゴリズムを用いて, 高度な LLM のベンチマークを行う。
  論文  参考訳（メタデータ） (2023-09-01T09:40:36Z)

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

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