論文の概要: One-Layer Transformers Provably Learn In-Context K-Nearest Neighbor Prediction with Chain-of-Thought

• arxiv url: http://arxiv.org/abs/2610.16798v1
• Date: Mon, 12 Oct 2026 13:50:42 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-10-18 21:29:55.009531
• Title: One-Layer Transformers Provably Learn In-Context K-Nearest Neighbor Prediction with Chain-of-Thought
• Title（参考訳）: チェーン・オブ・サートによるK-Nearest Neighbor予測の一層変圧器の学習
• Abstract要約: CoT(Chain-of-Thought)は、中間的推論ステップを生成することで、トランスフォーマーが複雑な推論タスクを解くことを可能にする。 私たちは、CoTがトランスフォーマーの学習能力を拡張し、解決が難しいタスクを解決できることを示します。
• 参考スコア（独自算出の注目度）: 7.013604169294101
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Chain-of-Thought (CoT) enables transformers to solve complex reasoning tasks by generating intermediate reasoning steps. Despite strong empirical success, the mechanisms by which such reasoning abilities emerge during training remain poorly understood, particularly from a theoretical perspective. In this work, we study this question in a stylized yet fully analyzable setting: in-context $\mathrm{K}$-nearest-neighbor ($\mathrm{K}$-NN) prediction with a one-layer transformer. Earlier work has demonstrated that one-layer transformers can be trained to perform $1$-NN without CoT (Li et al., 2024a) by having the softmax attention attend to the nearest neighbor in context. However, this result on $1$-NN cannot be extended to $\mathrm{K}$-NN for $K>1$, as softmax attention is much less naturally suited to attending to the 2nd through $K$-th nearest neighbors. We first give a rigorous negative result showing that this limitation already appears on a well-separated class of binary classification tasks for odd $K>1$. We then give an explicit construction of a one-layer transformer, and show that it can solve $\mathrm{K}$-NN via CoT reasoning. We further prove that, under a stylized training setup, gradient descent can recover this construction, thereby showing that transformers can acquire the capability to solve $\mathrm{K}$-NN through training. In addition, we show that the resulting trained model applies to a broader test class than that assumed in the training analysis. Our results shed light on how CoT expands the ability of transformers to learn and solve tasks that are otherwise hard to solve.
• Abstract（参考訳）: CoT(Chain-of-Thought)は、中間的推論ステップを生成することで、トランスフォーマーが複雑な推論タスクを解くことを可能にする。 強い経験的成功にもかかわらず、そのような推論能力が訓練中に現れるメカニズムは、特に理論的な観点からは、よく理解されていないままである。 そこで本研究では,この問題を,一層トランスフォーマーを用いた文中$\mathrm{K}$-nearest-neighbor ($\mathrm{K}$-NN)予測という,完全に解析可能なスタイルで検討する。 初期の研究は、1層トランスフォーマーをCoT(Li et al , 2024a)なしで1ドル-NNで実行できるように訓練できることを実証している。 しかし、この$$-NNでの結果は、$K>1$で$\mathrm{K}$-NNに拡張することはできない。 まず、この制限が奇数$K>1$の2進分類タスクのよく区切られたクラスに既に現れることを示す厳密な負の結果を与える。 次に、一層変換器の明示的な構成を示し、CoT推論により$\mathrm{K}$-NNを解けることを示す。 さらに、スタイリングされたトレーニング設定の下では、勾配降下によりこの構成が回復し、変換器がトレーニングを通じて$\mathrm{K}$-NNを解くことができることを示す。 さらに,得られたトレーニングモデルが,トレーニング分析で想定されるよりも広範なテストクラスに適用可能であることを示す。 私たちの結果は、CoTがトランスフォーマーの学習能力を拡張し、解決が難しいタスクを解決できることに光を当てています。

関連論文リスト

• Transformers Provably Learn to Internalize Chain-of-Thought [65.41010769606844]
  Implicit Chain-of-Thought (ICoT) は、隠れた状態の中で中間段階を内部化するモデルを訓練する。 Log-ICoTはシンキングトークンを一度に削除し、$k$のリニアから対数へのステージ数を削減します。 多層変圧器の実験により理論が確認され、より深い層に段階的に推論がどのように吸収されるかが可視化される。
  論文  参考訳（メタデータ） (2026-05-27T15:17:06Z)
• Closing the Theory-Practice Gap in Spiking Transformers via Effective Dimension [13.891522069967507]
  スパイキングトランスは、ニューロモルフィックハードウェアで38ドルから57ドル(約3,500円)のエネルギー効率を提供しながら、従来のトランスフォーマーと競合する精度を実現している。 本稿では, 自己注意をスパイクするための最初の包括的表現性理論を確立する。
  論文  参考訳（メタデータ） (2026-04-17T07:15:53Z)
• Theoretical limitations of multi-layer Transformer [14.63344366356708]
  マルチ層デコーダのみの変換器に対して,最初の$textitunconditional$lowboundを証明した。 また、ある$textitindistinguishable$$textitde$すべての可能な入力を見つける新しい証明手法も導入します。 我々の新しい通信モデルと証明技術は、トランスの計算能力のさらなる理解に役立つと信じている。
  論文  参考訳（メタデータ） (2024-12-04T02:37:31Z)
• On the Role of Depth and Looping for In-Context Learning with Task Diversity [69.4145579827826]
  多様なタスクを伴う線形回帰のための文脈内学習について検討する。 We show that multilayer Transformer is not robust to even distributional shifts as $O(e-L)$ in Wasserstein distance。
  論文  参考訳（メタデータ） (2024-10-29T03:27:56Z)
• Towards a Theoretical Understanding of the 'Reversal Curse' via Training Dynamics [45.69328374321502]
  自動回帰型大言語モデル(LLM)は、多くの複雑な推論タスクを解くのに優れた能力を示す。 LLM は、2つの文が意味的に同一であっても、推論中に '$B get A$' と結論付けることができない。 2つの自己回帰モデルに対する勾配降下のトレーニング力学を用いて、理論的に逆の呪いを解析する。
  論文  参考訳（メタデータ） (2024-05-07T21:03:51Z)
• Chain of Thought Empowers Transformers to Solve Inherently Serial Problems [57.58801785642868]
  思考の連鎖(CoT)は、算術や記号的推論タスクにおいて、大きな言語モデル(LLM)の精度を向上させるための非常に効果的な方法である。 この研究は、表現性のレンズを通してデコーダのみの変換器に対するCoTのパワーを理論的に理解する。
  論文  参考訳（メタデータ） (2024-02-20T10:11:03Z)

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

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