論文の概要: A Theory of Online Learning with Autoregressive Chain-of-Thought Reasoning

• arxiv url: http://arxiv.org/abs/2605.06819v1
• Date: Thu, 07 May 2026 18:21:05 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-05-11 19:43:38.537812
• Title: A Theory of Online Learning with Autoregressive Chain-of-Thought Reasoning
• Title（参考訳）: 自己回帰連鎖推論を用いたオンライン学習の理論
• Authors: Ilan Doron-Arad, Idan Mehalel, Elchanan Mossel,
• Abstract要約: [Joshiら,2025)は,このプロセスから生じる入力出力マップの学習可能性を研究するためのPACモデルを提案した。 我々は,未知の次点発生器による最終的な出力の誤り境界に着目し,このフレームワークのオンラインアナログを開発する。 我々のゴールは、最適なミスバウンドが生成地平線にどのように依存するかを理解することである。
• 参考スコア（独自算出の注目度）: 14.292982828097465
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Autoregressive generation lies at the heart of the mechanism of large language models. It can be viewed as the repeated application of a next-token generator: starting from an input string (prompt), the generator is applied for $M$ steps, and the last generated token is taken as the final output. [Joshi et al., 2025] proposed a PAC model for studying the learnability of the input-output maps arising from this process. We develop an online analogue of this framework, focusing on the mistake bound of learning the final output induced by an unknown next-token generator. We distinguish between two forms of feedback. In the End-to-End model, after each round the learner observes only the final token produced after $M$ autoregressive steps. In the Chain-of-Thought model, the learner is additionally shown the entire $M$-step trajectory. Our goal is to understand how the optimal mistake bound depends on the generation horizon $M$, and to what extent observing intermediate tokens can reduce this dependence. Our main results show that the online theory of autoregressive learning exhibits a qualitative picture analogous to the statistical one found by [Hanneke et al., 2026], but with a different scale of dependence on the generation horizon. In the End-to-End model, we prove a taxonomy of possible mistake-bound growth rates in the generation horizon $M$: essentially any rate between constant and logarithmic can arise. We further show that this logarithmic ceiling is unavoidable. In the Chain-of-Thought model, we show that access to the full generated trajectory eliminates the dependence on $M$ altogether. We also analyze autoregressive linear threshold classes, and prove optimal mistake bounds, as well as a new lower bound for the statistical setting. Along the way, our results resolve several questions left open by [Joshi et al., 2025].
• Abstract（参考訳）: 自己回帰生成は、大きな言語モデルのメカニズムの中心にある。 入力文字列(prompt)から始めて、ジェネレータが$M$のステップで適用され、最後に生成されたトークンが最終的な出力として扱われる。 [Joshi et al ,2025]は,このプロセスから生じる入力出力マップの学習可能性を研究するためのPACモデルを提案した。 我々は,未知の次点発生器による最終的な出力の誤り境界に着目し,このフレームワークのオンラインアナログを開発する。 私たちは2種類のフィードバックを区別します。 End-to-Endモデルでは、各ラウンドの後、学習者はM$の自己回帰ステップ後に生成される最後のトークンのみを観測する。 Chain-of-Thoughtモデルでは、学習者はさらに$M$-stepの軌跡を示す。 我々のゴールは、最適なミスバウンドが生成地平線にどのように依存するかを理解することである。 本研究の主目的は,オンライン自己回帰学習理論は,[Hanneke et al , 2026] に類似した定性的な画像を示すが,生成地平線への依存度は異なることである。 エンド・ツー・エンドモデルでは、生成地平線におけるミスバウンド成長率の分類をM$で証明する。 さらに、この対数天井は避けられないことを示す。 The Chain-of-Thought model, we show that access to the full generated trajectory makes the rely on $M$。 また, 自己回帰線形しきい値クラスを解析し, 誤差境界を最適に証明し, また, 統計的設定に対する新しい下限を導出する。 その過程で,[Joshi et al , 2025] が残したいくつかの疑問を整理した。

関連論文リスト

• Sample Complexity of Autoregressive Reasoning: Chain-of-Thought vs. End-to-End [48.8146191570092]
  現代の大きな言語モデルはテキストを自動回帰的に生成し、トークンを一度に1つ生成する。 このようなシステムの学習性を研究するため、Joshiらは次世代発電機のためのPAC学習フレームワークを導入した。 2つの質問に対して、サンプルの複雑性が$Tでどのようにスケールするかの分類を明らかにすることで、ほぼ完全な答えを与える。
  論文  参考訳（メタデータ） (2026-04-13T20:00:13Z)
• Continuous Autoregressive Language Models [56.49239051750678]
  我々はCALM(Continuous Autoregressive Language Models)を紹介する。 CALMは高忠実度オートエンコーダを使用して、Kトークンの塊を1つの連続ベクトルに圧縮する。 我々は、堅牢なトレーニング、評価、および制御可能なサンプリングを可能にする包括的可能性のないフレームワークを開発する。
  論文  参考訳（メタデータ） (2025-10-31T17:58:11Z)
• Why Can't Transformers Learn Multiplication? Reverse-Engineering Reveals Long-Range Dependency Pitfalls [54.57326125204404]
  言語モデルはますます能力が高くなっているが、多桁乗算という一見単純なタスクではまだ失敗している。 直観的連鎖を通して乗法をうまく学習するモデルをリバースエンジニアリングすることでなぜ研究する。
  論文  参考訳（メタデータ） (2025-09-30T19:03:26Z)
• Computational-Statistical Tradeoffs at the Next-Token Prediction Barrier: Autoregressive and Imitation Learning under Misspecification [50.717692060500696]
  対数損失を伴う次のトーケン予測は自己回帰シーケンスモデリングの基盤となる。 次トーケン予測は、適度な誤差増幅を表す$C=tilde O(H)$を達成するために堅牢にすることができる。 C=e(log H)1-Omega(1)$。
  論文  参考訳（メタデータ） (2025-02-18T02:52:00Z)
• Promises and Pitfalls of Generative Masked Language Modeling: Theoretical Framework and Practical Guidelines [74.42485647685272]
  GMLM(Generative Masked Language Models)に焦点を当てる。 我々は,マルコフ連鎖の入力として使用されるマスキングにより,データ分布の条件付き確率に適合するモデルを訓練し,モデルからサンプルを抽出する。 我々は,T5モデルを並列デコーディングに適応させ,最小品質の犠牲を伴って機械翻訳における2～3倍の高速化を実現した。
  論文  参考訳（メタデータ） (2024-07-22T18:00:00Z)
• Toward a Theory of Tokenization in LLMs [26.516041872337887]
  本稿では, 簡単なデータ生成プロセスにおいて, 変圧器の挙動を研究することによって, 理論的観点からトークン化について検討する。 変換器によって学習された最も単純なユニグラムモデルでさえ、$ktextth$-order Markovソースから引き出されたシーケンスの確率を最適にモデル化できることを示す。
  論文  参考訳（メタデータ） (2024-04-12T09:01:14Z)

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

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