論文の概要: From Shortcut Learning to Discrete Neural Insertion Sort

• arxiv url: http://arxiv.org/abs/2609.31114v1
• Date: Fri, 25 Sep 2026 11:00:52 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-28 18:27:51.357807
• Title: From Shortcut Learning to Discrete Neural Insertion Sort
• Title（参考訳）: ショートカット学習からニューラルインサーションソートまで
• Abstract要約: 本稿では、ニューラルネットワークをトレーニングし、トレーニング中に見られる入力サイズを超えて一般化するための離散ニューラルネットワーク挿入ソートについて紹介する。 長さ16のシーケンスのみをトレーニングすると、長さ64と128のシーケンスに対して100%のソートシーケンス精度が得られる。 この結果から,離散的な実行は高い長さの一般化をサポートするとともに,忠実なアルゴリズムの実行学習に必要な問題固有の帰納バイアスも強調できることがわかった。
• 参考スコア（独自算出の注目度）: 5.53749098112392
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Neural algorithmic reasoning aims to train neural networks to follow known algorithms and generalize beyond the input sizes seen during training. However, correct final outputs and intermediate supervision do not necessarily show that a model follows the intended execution. We study this problem using insertion sort. Our analysis of the CLRS30 baseline NAR shows that the hint objective is weakly optimized and that hint accuracy remains low. Moreover, many intermediate representations can already be decoded into sorted sequences before the reference insertion-sort execution terminates, suggesting that the model learns a shortcut to the final output. Motivated by these findings, we introduce Discrete Neural Insertion Sort. Our model represents the sequence as a chain, separates scalar exchanges from control-state transitions, and projects node representations back to discrete states after every processor step. When trained only on sequences of length 16, the model achieves $100\%$ sorted-sequence accuracy on sequences of length 64 and 128. However, an ablation shows that discretization and graph structure alone are insufficient: without additional supervision of the global inner-loop state, the model fails even at the training length. Our results show that discrete execution can support strong length generalization, while also highlighting the problem-specific inductive bias required to learn a faithful algorithmic execution.
• Abstract（参考訳）: ニューラルネットワーク推論は、既知のアルゴリズムに従うようにニューラルネットワークをトレーニングし、トレーニング中に見られる入力サイズを超えて一般化することを目的としている。 しかし、正しい最終的な出力と中間的な監督は、必ずしもモデルが意図した実行に従うことを示さない。 我々は挿入ソートを用いてこの問題を研究する。 CLRS30ベースラインNARの解析は、ヒント目標が弱く最適化されており、ヒント精度が低いことを示す。 さらに、参照挿入ソート実行が終了する前に、多くの中間表現をソートシーケンスにデコードすることが可能であり、モデルが最終出力へのショートカットを学ぶことを示唆している。 これらの知見に触発され、離散神経挿入ソートを導入した。 我々のモデルはシーケンスをチェーンとして表現し、スカラー交換を制御状態遷移から分離し、各プロセッサステップ後にノード表現を離散状態に戻す。 長さ16のシーケンスのみに基づいてトレーニングすると、長さ64と128のシーケンスに対して100\%のソートシーケンス精度が得られる。 しかし、アブレーションにより、離散化とグラフ構造だけでは不十分であることが示され、グローバルなインナーループ状態のさらなる監督がなければ、モデルはトレーニング長でも失敗する。 この結果から,離散的な実行は高い長さの一般化をサポートするとともに,忠実なアルゴリズムの実行学習に必要な問題固有の帰納バイアスを浮き彫りにすることができることがわかった。

関連論文リスト

• On the Bias of Next-Token Predictors Toward Systematically Inefficient Reasoning: A Shortest-Path Case Study [4.798155648915794]
  大規模言語モデルにおける推論を改善するための2つの重要な要因について検討する。 我々は、カスタムトークン化器を用いて、質問-トレース-回答三重項に対してデコーダのみの変換器を訓練する。 同じトレーニングの予算で、非効率なトレースで訓練されたモデルは、目に見えないグラフよりも一般化される。
  論文  参考訳（メタデータ） (2025-07-07T18:00:06Z)
• Position as Probability: Self-Supervised Transformers that Think Past Their Training for Length Extrapolation [0.0]
  PRISMは、トランスフォーマーがトレーニング長の10倍まで正確に外挿できる新しい位置符号化機構である。 解析により、PRISMの位置エンコーディングは鋭く解釈可能な内部状態を維持しており、信頼性のある長さ一般化の理論的基礎となっていることが示された。
  論文  参考訳（メタデータ） (2025-06-01T09:20:44Z)
• Towards Better Out-of-Distribution Generalization of Neural Algorithmic Reasoning Tasks [51.8723187709964]
  ニューラルネットワーク推論タスクのOOD一般化について検討する。 目標は、ディープニューラルネットワークを使用して入出力ペアからアルゴリズムを学ぶことである。
  論文  参考訳（メタデータ） (2022-11-01T18:33:20Z)
• A Non-monotonic Self-terminating Language Model [62.93465126911921]
  本稿では,不完全復号アルゴリズムによる非終端列の問題に焦点をあてる。 まず、グリーディ探索、トップ$kのサンプリング、核サンプリングを含む不完全確率復号アルゴリズムを定義する。 次に,単調な終端確率の制約を緩和する非単調な自己終端言語モデルを提案する。
  論文  参考訳（メタデータ） (2022-10-03T00:28:44Z)
• Discovering Non-monotonic Autoregressive Orderings with Variational Inference [67.27561153666211]
  我々は、訓練データから高品質な生成順序を純粋に検出する、教師なし並列化可能な学習装置を開発した。 エンコーダを非因果的注意を持つトランスフォーマーとして実装し、1つのフォワードパスで置換を出力する。 言語モデリングタスクにおける経験的結果から,我々の手法は文脈認識であり,一定の順序と競合する,あるいはより優れた順序を見つけることができる。
  論文  参考訳（メタデータ） (2021-10-27T16:08:09Z)
• Alleviate Exposure Bias in Sequence Prediction \\ with Recurrent Neural Networks [47.52214243454995]
  繰り返しニューラルネットワーク(RNN)を訓練する一般的な戦略は、各ステップで入力として地上の真実を取ることです。 本稿では,RNNの長期的依存関係をよりよく把握するための,完全微分可能なトレーニングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-03-22T06:15:22Z)
• Consistency of a Recurrent Language Model With Respect to Incomplete Decoding [67.54760086239514]
  逐次言語モデルから無限長のシーケンスを受信する問題について検討する。 不整合に対処する2つの対策として、トップkと核サンプリングの一貫性のある変種と、自己終端の繰り返し言語モデルを提案する。
  論文  参考訳（メタデータ） (2020-02-06T19:56:15Z)

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

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