論文の概要: Can Transformers Learn to Verify During Backtracking Search?

• arxiv url: http://arxiv.org/abs/2605.22221v1
• Date: Thu, 21 May 2026 09:26:01 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-22 16:35:42.190115
• Title: Can Transformers Learn to Verify During Backtracking Search?
• Title（参考訳）: トランスフォーマーは、バックトラック検索中に検証を学べるか?
• Authors: Yin Jun Phua, Tony Ribeiro, Tuan Nguyen, Katsumi Inoue,
• Abstract要約: バックトラック探索は古典的な制約解決者、プランナー、定理証明者の基礎となる。 最近の変圧器に基づく推論システムは, 探索木を自身の中間ステップで探索する。 累積トレースで訓練されたデコーダのみの変換器は、この要件を2つの方法で満たさないことを示す。
• 参考スコア（独自算出の注目度）: 5.709908922073304
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: Backtracking search underlies classical constraint solvers, planners, and theorem provers. Recent transformer-based reasoning systems explore search trees over their own intermediate steps. A common training recipe fits an autoregressive next-token loss on offline solver traces. The model's input at each step is a cumulative trace of all prior decisions. The optimal continue-or-backtrack predictor depends only on the current search state, since two trajectories reaching the same state admit the same viable continuations. We show that decoder-only transformers trained on cumulative traces fail this requirement in two ways: the trace can scatter state features across many positions (scattered retrieval), and the predictor can condition on the trajectory rather than the state (history entanglement). We address scattered retrieval with localization, a trace-level fix that rewrites each decision block to expose state features locally. We address history entanglement with Selective State Attention (SSA), a fixed attention mask that enforces state-based decisions structurally without modifying training data, objective, or parameters. We focus on reactive verification, after propagation has exposed a contradiction. We test SSA on 3-SAT, graph coloring, Blocks World, and backtracking parsing. On same-state pairs that differ only in prior history, SSA emits identical decisions while a cumulative-trained causal baseline does not. Our contribution is a diagnostic of transformer behavior on serialized trajectory data, paired with a structural fix. Pretrained language models that search over their own reasoning steps may face the same failure. Our analysis opens up inference-time context clearing as a candidate way to apply the same isolation without retraining.
• Abstract（参考訳）: バックトラック探索は古典的な制約解決者、プランナー、定理証明者の基礎となる。 最近の変圧器に基づく推論システムは, 探索木を自身の中間ステップで探索する。 一般的なトレーニングレシピは、オフラインのソルバトレースで自動回帰的な次トーケン損失に適合する。 各ステップにおけるモデルの入力は、すべての事前決定の累積的トレースである。 最適な継続またはバックトラック予測器は、同じ状態に達する2つの軌道が同じ持続性を持つため、現在の探索状態にのみ依存する。 累積トレースで訓練されたデコーダのみの変換器は、多くの位置にわたって状態特徴を散乱させることができ(散乱された検索)、予測器は状態よりも軌道に条件を付けることができる(歴史の絡み合い)。 我々は,各決定ブロックを書き換えて局所的な状態特徴を露呈するトレースレベルの修正であるローカライゼーションによる分散検索に対処する。 SSA(Selective State Attention)は、トレーニングデータや目的、パラメータを変更することなく、状態ベースの決定を構造的に強制する固定された注意マスクである。 伝搬が矛盾を露呈した後は、反応性検証に重点を置いている。 3SAT、グラフカラー、ブロックワールド、バックトラックパーシングでSSAをテストする。 既往歴にのみ異なる同状態対において、SSAは累積学習された因果基底線が存在しないのに対して、同一の決定を出力する。 我々の貢献は、直列化軌道データにおける変圧器の挙動の診断であり、構造的修正と組み合わせている。 独自の推論ステップを探索する事前訓練された言語モデルは、同じ障害に直面します。 我々の分析は、推論時コンテキストクリア化を、再トレーニングせずに同じ分離を適用するための候補方法として開きます。

関連論文リスト

• Rethinking State Tracking in Recurrent Models Through Error Control Dynamics [26.942965240880515]
  本研究では,アフィン再帰ネットワークが状態表現を保存すると,状態分離部分空間の誤りを訂正できないことを示す。 我々は、ロバストな状態追跡がアーキテクチャの理論的表現性だけでなく、エラー制御によって決定されることを証明した。
  論文  参考訳（メタデータ） (2026-05-08T13:59:15Z)
• The UNDO Flip-Flop: A Controlled Probe for Reversible Semantic State Management in State Space Model [0.0]
  状態空間モデル(SSM)は、星のないシーケンシャルタスクと有界階層構造の両方をモデル化する理論的能力を持っていることが示されている。 このギャップを埋めるためにUNDO Flip-Flopタスクを導入します。 我々は,この枠組みの下で一層および二層マンバ-2を評価する。
  論文  参考訳（メタデータ） (2026-04-07T14:23:40Z)
• Two failure modes of deep transformers and how to avoid them: a unified theory of signal propagation at initialisation [8.973965016201822]
  ニューラルネットワークの適切な初期化を見つけることは、スムーズなトレーニングと優れたパフォーマンスを保証するために不可欠である。 トランスフォーマーでは、間違った初期化は、ランク崩壊、すべてのトークンが同様の表現に崩壊するランク崩壊、エントロピー崩壊、高度に集中した注意スコアが不安定になる2つの失敗モードの1つにつながる可能性がある。 ここでは、自己アテンション、層正規化、スキップ接続、勾配を有する深層変圧器による信号伝搬の解析理論を提案する。
  論文  参考訳（メタデータ） (2025-05-30T08:18:23Z)
• (How) Do Language Models Track State? [52.03388573068501]
  トランスフォーマー言語モデル(LM)は、進化する世界の未観測状態を追跡する必要があるように見える振る舞いを示す。 順列を構成するために訓練された、あるいは微調整されたLMにおける状態追跡について検討した。 LMは2つの状態追跡機構のうちの1つを一貫して学習していることを示す。
  論文  参考訳（メタデータ） (2025-03-04T18:31:02Z)
• Semi-DETR: Semi-Supervised Object Detection with Detection Transformers [105.45018934087076]
  半教師付き物体検出(SSOD)におけるDETRに基づくフレームワークの解析 本報告では,第1次変圧器を用いたエンド・ツー・エンド半教師対象検出器であるSemi-DETRについて述べる。 我々の手法は、最先端の手法をクリアマージンで上回る。
  論文  参考訳（メタデータ） (2023-07-16T16:32:14Z)
• Consistent Diffusion Models: Mitigating Sampling Drift by Learning to be Consistent [97.64313409741614]
  本稿では, モデルが生成したデータ上での予測が時間とともに一定であることを示す, 両立性特性を強制することを提案する。 CIFAR-10の条件および非条件生成とAFHQとFFHQのベースライン改良について,本研究の新たな訓練目標が得られた。
  論文  参考訳（メタデータ） (2023-02-17T18:45:04Z)
• Unsupervised Learning of Accurate Siamese Tracking [68.58171095173056]
  分類枝と回帰枝の両方で時間対応を学習できる新しい教師なし追跡フレームワークを提案する。 トラッカーは、トラッカーネットやLaSOTのような大規模データセット上で、教師なしの手法と同等の性能を発揮する。
  論文  参考訳（メタデータ） (2022-04-04T13:39:43Z)

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

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