論文の概要: SAT-ACT: Learning CDCL Branching from Outcome-Derived Action Preferences
- arxiv url: http://arxiv.org/abs/2610.41290v1
- Date: Fri, 30 Oct 2026 05:52:04 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-11-02 22:05:31.626127
- Title: SAT-ACT: Learning CDCL Branching from Outcome-Derived Action Preferences
- Title（参考訳）: SAT-ACT:アウトカムデリバティブなアクション設定からCDCLブランチを学習する
- Abstract要約: SAT-ACTはCDCL分岐結果から学習するフレームワークである。
SAT-ACTは3つのSATファミリーのCDCL検索コストを一貫して削減し,SATコンペティションベンチマークのPAR-2を改善した。
- 参考スコア（独自算出の注目度）: 25.127064251508074
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Learning-based approaches have increasingly been explored for SAT solving, with particular attention to improving branching decisions in conflict-driven clause learning (CDCL) solvers. These approaches derive branching guidance either from static structural properties of SAT formulas or from dynamic signals obtained through solver feedback and execution traces. However, these forms of supervision provide limited evidence about state-dependent branching effects, while different outcome measures may favor different branching choices. To address these limitations, we propose SAT-ACT, an outcome-derived learning framework for CDCL branching. We design three complementary outcome comparison criteria to extract action preferences from independent branching action rollouts initiated at the same solver state. The criteria identify preferences supported by the outcomes and leave comparisons unresolved when the evidence is insufficient or conflicting, instead of forcing an ordering using a predefined scalar metric. A state-conditioned network learns branching priorities from the extracted preferences and uses them to guide CDCL search directly without online action rollouts. We further introduce non-dominated heuristic action supervision, which retains the solver-selected action as a training target only when it remains non-dominated under these preferences. Solver-level experiments show that SAT-ACT consistently reduces CDCL search costs on three SAT families and improves PAR-2 on the SAT Competition benchmarks.
- Abstract（参考訳）: SAT解決のための学習ベースのアプローチはますます検討され、特に、競合駆動型節学習(CDCL)解決における分岐決定の改善に注意が向けられている。
これらの手法は、SAT公式の静的構造特性や、ソルバフィードバックや実行トレースを通じて得られる動的信号から分岐ガイダンスを導出する。
しかしながら、これらの形態の監督は、州に依存した分岐効果に関する限られた証拠を提供する一方、異なる結果対策は異なる分岐選択を好む可能性がある。
これらの制約に対処するため,CDCL分岐のための結果由来学習フレームワークSAT-ACTを提案する。
そこで本研究では,独立系分岐動作ロールアウトから行動選好を抽出するための3つの相補的な結果比較基準を設計する。
基準は、事前に定義されたスカラー計量を使用した順序付けを強制するのではなく、証拠が不十分または矛盾している場合に、結果によって支持される嗜好を特定し、比較を未解決にしておく。
状態条件付きネットワークは、抽出した好みから分岐優先度を学習し、オンラインアクションロールアウトなしでCDCL検索を直接ガイドする。
さらに,非支配的ヒューリスティック行動監視を導入し,これらの嗜好の下で非支配的である場合にのみ,解決者選択行動がトレーニング対象として維持されることを示した。
ソルバーレベルの実験では、SAT-ACTは3つのSATファミリーのCDCL検索コストを一貫して削減し、SATベンチマークベンチマークのPAR-2を改善している。
関連論文リスト
- Token Utility Is Selection-Conditioned: Coupled Selection of Prompt Context and Response Supervision for Efficient Instruction Tuning [11.796634827510323]
BRIDGEは、共有バリデーション指向のインタラクションサロゲートを通じて選択条件付きトークンユーティリティをキャプチャする。
構造認識プロジェクションは条件応答スコアをコヒーレントな監視スパンに変換する。
BRIDGEは、数学的推論、コード生成、命令フォローにおける全体的な選択方法の比較を導く。
論文 参考訳（メタデータ） (2026-09-19T10:46:58Z) - Multimodal Learning on Low-Quality Data with Conformal Predictive Self-Calibration [72.0672328514289]
マルチモーダル学習は、しばしば低品質データの課題に悩まされる。
コンフォーマル予測自己校正(Conformal Predictive Self-Calibration)と呼ばれる統合フレームワークを提案する。
私たちのフレームワークは、既存の最先端メソッドを一貫して上回ります。
論文 参考訳（メタデータ） (2026-05-05T14:48:52Z) - UCS: Estimating Unseen Coverage for Improved In-Context Learning [24.34094317236037]
Unseen Coverage Selection (UKS) はトレーニングなしのサブセットレベルのカバレッジであり、優れたデモセットは、現在選択されているサブセットによって明らかにされていない潜在クラスタにモデルを公開すべきである、という原則によって以前に動機付けられていた。
UCSはこのアイデアを、モデルに一貫性のある埋め込みから離散潜在クラスタを誘導し、その経験周波数スペクトルからSmoothed Good-contexting estimatorを通して、候補サブセット内の未発見クラスタ数を推定することによって運用する。
Frontier Large Language Models による複数の意図分類と推論ベンチマークの実験により、UCS による強いベースラインの強化により、ICL の精度は最大で 2-6% 向上することが示された。
論文 参考訳（メタデータ） (2026-04-13T20:00:41Z) - Boolean Satisfiability via Imitation Learning [21.853451002559016]
我々は、競合駆動型節学習(CDCL)問題解決のための分岐ポリシーであるImitSATを提案する。
ImitSATは、専門家のKeyTraceから学んだ。
論文 参考訳（メタデータ） (2025-09-29T19:09:37Z) - Circuit-Aware SAT Solving: Guiding CDCL via Conditional Probabilities [8.18310731992061]
回路満足度(CSAT)は電子設計自動化において重要な役割を担っている。
本稿では,新しいサーキット対応SAT解決フレームワークであるCASCADを紹介する。
我々はCASCADが最先端のCNFベースのアプローチと比較して最大10倍の解時間を短縮することを示した。
論文 参考訳（メタデータ） (2025-08-06T09:16:47Z) - A Systematic Examination of Preference Learning through the Lens of Instruction-Following [83.71180850955679]
新たな合成データ生成パイプラインを用いて48,000の命令追従プロンプトを生成する。
合成プロンプトでは、リジェクションサンプリング(RS)とモンテカルロ木探索(MCTS)の2つの選好データセットキュレーション手法を用いる。
実験により、MCTSが生成した選好ペアにおける共有プレフィックスは、限界はあるが一貫した改善をもたらすことが明らかになった。
高コントラストの選好ペアは一般的に低コントラストのペアよりも優れているが、両者を組み合わせることで最高のパフォーマンスが得られることが多い。
論文 参考訳（メタデータ） (2024-12-18T15:38:39Z) - Bidirectional Decoding: Improving Action Chunking via Guided Test-Time Sampling [51.38330727868982]
動作チャンキングが学習者と実証者の間の分岐にどのように影響するかを示す。
動作チャンキングをクローズドループ適応でブリッジするテスト時間推論アルゴリズムである双方向デコーディング(BID)を提案する。
提案手法は、7つのシミュレーションベンチマークと2つの実世界のタスクにまたがって、最先端の2つの生成ポリシーの性能を向上させる。
論文 参考訳（メタデータ） (2024-08-30T15:39:34Z) - Explaining SAT Solving Using Causal Reasoning [30.469229388827443]
本稿では、因果推論を用いて、現代のSATソルバの機能に関する洞察を得るCausalSATを紹介する。
われわれはCausalSATを用いて,これまで「親指のルール」や経験的発見と考えられていた仮説を定量的に検証した。
論文 参考訳（メタデータ） (2023-06-09T22:53:16Z) - Bayes risk CTC: Controllable CTC alignment in Sequence-to-Sequence tasks [63.189632935619535]
予測アライメントの望ましい特性を強制するためにベイズリスクCTC(BRCTC)を提案する。
BRCTCを他の早期排出の選好と組み合わせることで、オンラインモデルの性能・遅延トレードオフが改善される。
論文 参考訳（メタデータ） (2022-10-14T03:55:36Z) - ReAct: Temporal Action Detection with Relational Queries [84.76646044604055]
本研究は,アクションクエリを備えたエンコーダ・デコーダフレームワークを用いて,時間的行動検出(TAD)の進展を図ることを目的とする。
まず,デコーダ内の関係注意機構を提案し,その関係に基づいてクエリ間の関心を誘導する。
最後に、高品質なクエリを区別するために、推論時に各アクションクエリのローカライズ品質を予測することを提案する。
論文 参考訳（メタデータ） (2022-07-14T17:46:37Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。