論文の概要: Sample Complexity of Autoregressive Reasoning: Chain-of-Thought vs. End-to-End

• arxiv url: http://arxiv.org/abs/2604.12013v2
• Date: Sat, 18 Apr 2026 18:57:54 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-21 13:51:31.093302
• Title: Sample Complexity of Autoregressive Reasoning: Chain-of-Thought vs. End-to-End
• Title（参考訳）: 自己回帰推論のサンプル複雑性--Chain-of-Thought vs. End-to-End
• Authors: Steve Hanneke, Idan Mehalel, Shay Moran,
• Abstract要約: 現代の大きな言語モデルはテキストを自動回帰的に生成し、トークンを一度に1つ生成する。 このようなシステムの学習性を研究するため、Joshiらは次世代発電機のためのPAC学習フレームワークを導入した。 2つの質問に対して、サンプルの複雑性が$Tでどのようにスケールするかの分類を明らかにすることで、ほぼ完全な答えを与える。
• 参考スコア（独自算出の注目度）: 48.8146191570092
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Modern large language models generate text autoregressively, producing tokens one at a time. To study the learnability of such systems, Joshi et al. (COLT 2025) introduced a PAC-learning framework for next-token generators, the primitive underlying autoregressive models. In this framework, an unknown next-token generator maps a sequence of tokens to the next token and is iteratively applied for $T$ steps, producing a chain of tokens whose final token constitutes the model's output. The learning task is to learn the input-output mapping induced by this autoregressive process. Depending on the available supervision, training examples may reveal only the final output (End-to-End supervision) or the entire generated chain (Chain-of-Thought supervision). This raises two natural questions: how the sample complexity depends on the generation length $T$, and how much Chain-of-Thought supervision can reduce this dependence. In this work we give a nearly complete answer to both questions by uncovering a taxonomy of how the sample complexity scales with $T$. For End-to-End learning, we show that the landscape is remarkably rich: subject to mild conditions, essentially any growth rate $r(T)$ between constant and linear can arise as the sample complexity, and combined with the linear upper bound of Joshi et al., this yields an essentially complete characterization. In contrast, under Chain-of-Thought supervision we show that the sample complexity is independent of $T$, demonstrating that access to intermediate reasoning steps can eliminate the dependence on the generation length altogether. Our analysis introduces new combinatorial tools, and as corollaries we resolve several open questions posed by Joshi et al. regarding the dependence of learnability on the generation length and the role of Chain-of-Thought supervision.
• Abstract（参考訳）: 現代の大きな言語モデルはテキストを自動回帰的に生成し、トークンを一度に1つ生成する。 このようなシステムの学習可能性を研究するため、Joshi et al (COLT 2025)は、基本的な自己回帰モデルである次世代ジェネレータのためのPAC学習フレームワークを導入した。 このフレームワークでは、未知の次のトークンジェネレータがトークンのシーケンスを次のトークンにマッピングし、反復的に$T$のステップに適用され、最終的なトークンがモデルの出力を構成するトークンの連鎖を生成する。 学習課題は、この自己回帰プロセスによって誘導される入出力マッピングを学習することである。 利用可能な監視方法によっては、トレーニング例は最終的なアウトプット(End-to-Endの監督)または生成されたチェーン全体(Chain-of-Thoughtの監督)のみを明らかにすることができる。 このことは、サンプルの複雑さが生成長$T$にどのように依存するか、そしてChain-of-Thoughtの監督によってこの依存を減らせるかという2つの自然な疑問を提起する。 この研究では、サンプルの複雑さが$T$でどのようにスケールするかの分類を明らかにすることで、両方の質問にほぼ完全な答えを与える。 端から端までの学習では、ランドスケープは極めて豊かなものであり、基本的には、定数と線形の間の任意の成長率$r(T)$がサンプル複雑性として生じ、Joshiらによる線形上界と組み合わせることで、本質的に完全な特徴付けが得られる。 対照的に、Chain-of-Thoughtの監督下では、サンプルの複雑さが$T$とは独立であることを示し、中間的推論ステップへのアクセスが生成長への依存を完全に排除できることを示した。 本分析では,新たな組み合わせツールを導入し,Joshiらによる学習可能性の世代長依存性とチェーン・オブ・ソート管理の役割について,いくつかのオープンな疑問を整理する。

関連論文リスト

• Multiplex Thinking: Reasoning via Token-wise Branch-and-Merge [87.51901436392427]
  大規模言語モデルは、しばしばChain-of-Thought (CoT)でより効果的に複雑な推論タスクを解決する。 対照的に、人間は、しばしば、もっともらしい次のステップに対して、引力のある確率分布を維持することによって、柔らかに理にかなっている。 我々は、K候補トークンをサンプリングし、それらの埋め込みを1つの連続多重化トークンに集約するソフトな推論機構である多重思考を提案する。 モデルは自信を持っていれば、多重化トークンはほぼ独立しており、標準のCoTのように振る舞う。
  論文  参考訳（メタデータ） (2026-01-13T18:48:00Z)
• Rethinking Thinking Tokens: LLMs as Improvement Operators [80.12087211785949]
  推論トレーニングは、LLMに長い思考の連鎖(長いCoT)を生み出す動機を与え、自己チェックによるソリューション戦略を探索することを可能にする。 これにより、精度が高くなりますが、コンテキストの長さ、トークン/計算コスト、応答レイテンシが膨らみます。 現在のモデルはメタ認知を活用して、このParetoフロンティアで他の組み合わせを提供できるのでしょうか? i) 多様なドラフトを並列に生成し、(ii) それらを有界なテキストワークスペースに蒸留し、(iii) このワークスペース上に条件付き精製する。
  論文  参考訳（メタデータ） (2025-10-01T17:08:59Z)
• Why Can't Transformers Learn Multiplication? Reverse-Engineering Reveals Long-Range Dependency Pitfalls [54.57326125204404]
  言語モデルはますます能力が高くなっているが、多桁乗算という一見単純なタスクではまだ失敗している。 直観的連鎖を通して乗法をうまく学習するモデルをリバースエンジニアリングすることでなぜ研究する。
  論文  参考訳（メタデータ） (2025-09-30T19:03:26Z)
• CoT Information: Improved Sample Complexity under Chain-of-Thought Supervision [10.29575414214269]
  チェーン・オブ・思想(CoT)の監督は、最終的なアウトプットとともに中間的推論ステップを提供する。 本稿では,CoT監督下での学習の統計的理論について述べる。
  論文  参考訳（メタデータ） (2025-05-21T18:28:54Z)
• A Theory of Learning with Autoregressive Chain of Thought [46.4004951842894]
  チェーンオブ思考が観察された場合と,即時回答ペアのみをトレーニングする場合の両方において,学習問題を定式化する。 本稿では,普遍的な表現可能性と計算的に抽出可能な連鎖学習を実現するための,シンプルなベースクラスを提案する。
  論文  参考訳（メタデータ） (2025-03-11T00:21:32Z)
• The Evolution of Statistical Induction Heads: In-Context Learning Markov Chains [28.41876902994335]
  In-context Learning (ICL) 機能がどのように出現するかを研究するために,Markov Chain シーケンスモデリングタスクを導入する。 このタスクで訓練されたトランスフォーマーは、正確な次の確率を計算するための統計的誘導ヘッドを形成する。 本研究では, 変圧器層間の相互作用から学習結果が得られたことを示し, より単純なユニグラム解の存在が最終ビッグラム解の形成を遅らせる可能性があることを示す。
  論文  参考訳（メタデータ） (2024-02-16T18:28:36Z)
• Auto-Regressive Next-Token Predictors are Universal Learners [17.416520406390415]
  線形次トーケン予測器のような単純なモデルでさえ、チューリングマシンによって効率的に計算される任意の関数を近似することができることを示す。 また、線形ネットワークや浅層多層パーセプトロン(MLP)のような単純な次世代予測器が、テキスト生成や算術タスクにおいて非自明な性能を示すことを示す。
  論文  参考訳（メタデータ） (2023-09-13T14:15:03Z)

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

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