Sample Complexity of Autoregressive Reasoning: Chain-of-Thought vs. End-to-End

• URL: http://arxiv.org/abs/2604.12013v2
• Date: Sat, 18 Apr 2026 18:57:54 GMT
• Title: Sample Complexity of Autoregressive Reasoning: Chain-of-Thought vs. End-to-End
• Abstract summary: Modern large language models generate text autoregressively, producing tokens one at a time.<n>To study the learnability of such systems, Joshi et al. introduced a PAC-learning framework for next-token generators.<n>We give a nearly complete answer to two questions by uncovering a taxonomy of how the sample complexity scales with $T.
• Score: 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.

Related papers

• Learn from your own latents and not from tokens: A sample-complexity theory [53.5821824211418]
  We study networks trained to predict their emphown latent representations of related views or masked regions.<n>We show that latent prediction achieves this with a number of samples emphconstant in $L$, up to logarithmic factors.<n>This suggests that explicit stacking such as H-JEPA is largely redundant.
  arXiv  Detail & Related papers  (2026-05-26T22:16:42Z)
• Self-Attention as a Covariance Readout: A Unified View of In-Context Learning and Repetition [8.250374560598495]
  Large language models (LLMs) exhibit two behaviours: in-context learning (ICL) and repetitive generation.<n>In both, the model behaves as though it had summarised the context into a population-level statistic and discarded token-level detail.<n>We ask whether this summarisation and forgetting' can be derived from the attention mechanism itself, and answer in the affirmative.
  arXiv  Detail & Related papers  (2026-05-11T12:33:15Z)
• A Theory of Online Learning with Autoregressive Chain-of-Thought Reasoning [14.292982828097465]
  [Joshi et al., 2025] proposed a PAC model for studying the learnability of the input-output maps arising from this process.<n>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.<n>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.
  arXiv  Detail & Related papers  (2026-05-07T18:21:05Z)
• Multiplex Thinking: Reasoning via Token-wise Branch-and-Merge [87.51901436392427]
  Large language models often solve complex reasoning tasks more effectively with Chain-of-Thought (CoT)<n>Humans, by contrast, often reason softly by maintaining a tractable probability distribution over plausible next steps.<n>We propose Multiplex Thinking, a soft reasoning mechanism that samples K candidate tokens and aggregates their embeddings into a single continuous multiplex token.<n>Multiplex Thinking is self-adaptive: when the model is confident, the multiplex token is nearly discrete and behaves like standard CoT.
  arXiv  Detail & Related papers  (2026-01-13T18:48:00Z)
• Rethinking Thinking Tokens: LLMs as Improvement Operators [80.12087211785949]
  Reasoning training incentivizes LLMs to produce long chains of thought (long CoT), which allows them to explore solution strategies with self-checking.<n>This results in higher accuracy, but inflates context length, token/compute cost, and answer latency.<n>We ask: Can current models leverage their metacognition to provide other combinations on this Pareto frontier?<n>We identify an interesting inference family Parallel-Distill-Refine (PDR), which performs the following: (i) generate diverse drafts in parallel; (ii) distill them into a bounded, textual workspace; and (iii) refine conditioned on this workspace
  arXiv  Detail & Related papers  (2025-10-01T17:08:59Z)
• Why Can't Transformers Learn Multiplication? Reverse-Engineering Reveals Long-Range Dependency Pitfalls [54.57326125204404]
  Language models are increasingly capable, yet still fail at a seemingly simple task of multi-digit multiplication.<n>We study why, by reverse-engineering a model that successfully learns multiplication via emphimplicit chain-of-thought'
  arXiv  Detail & Related papers  (2025-09-30T19:03:26Z)
• CoT Information: Improved Sample Complexity under Chain-of-Thought Supervision [10.29575414214269]
  Chain-of-thought (CoT) supervision provides intermediate reasoning steps together with the final output.<n>This paper develops a statistical theory of learning under CoT supervision.
  arXiv  Detail & Related papers  (2025-05-21T18:28:54Z)
• A Theory of Learning with Autoregressive Chain of Thought [46.4004951842894]
  We formalize the learning problems both when the chain-of-thought is observed and when training only on prompt-answer pairs.<n>We present a simple base class that allows for universal representability and computationally tractable chain-of-thought learning.
  arXiv  Detail & Related papers  (2025-03-11T00:21:32Z)
• The Evolution of Statistical Induction Heads: In-Context Learning Markov Chains [28.41876902994335]
  We introduce a simple Markov Chain sequence modeling task to study how this in-context learning (ICL) capability emerges. Transformers trained on this task form emphstatistical induction heads which compute accurate next-token probabilities. We show how successful learning results from the interaction between the transformer's layers, and uncover evidence that the presence of the simpler unigram solution may delay formation of the final bigram solution.
  arXiv  Detail & Related papers  (2024-02-16T18:28:36Z)
• Auto-Regressive Next-Token Predictors are Universal Learners [17.416520406390415]
  We show that even simple models such as linear next-token predictors can approximate any function efficiently computed by a Turing machine. We also show experimentally that simple next-token predictors, such as linear networks and shallow Multi-Layer Perceptrons (MLPs), display non-trivial performance on text generation and arithmetic tasks.
  arXiv  Detail & Related papers  (2023-09-13T14:15:03Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.