CoT Information: Improved Sample Complexity under Chain-of-Thought Supervision

• URL: http://arxiv.org/abs/2505.15927v1
• Date: Wed, 21 May 2025 18:28:54 GMT
• Title: CoT Information: Improved Sample Complexity under Chain-of-Thought Supervision
• Abstract summary: 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.
• Score: 10.29575414214269
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Learning complex functions that involve multi-step reasoning poses a significant challenge for standard supervised learning from input-output examples. Chain-of-thought (CoT) supervision, which provides intermediate reasoning steps together with the final output, has emerged as a powerful empirical technique, underpinning much of the recent progress in the reasoning capabilities of large language models. This paper develops a statistical theory of learning under CoT supervision. A key characteristic of the CoT setting, in contrast to standard supervision, is the mismatch between the training objective (CoT risk) and the test objective (end-to-end risk). A central part of our analysis, distinguished from prior work, is explicitly linking those two types of risk to achieve sharper sample complexity bounds. This is achieved via the *CoT information measure* $\mathcal{I}_{\mathcal{D}, h_\star}^{\mathrm{CoT}}(\epsilon; \calH)$, which quantifies the additional discriminative power gained from observing the reasoning process. The main theoretical results demonstrate how CoT supervision can yield significantly faster learning rates compared to standard E2E supervision. Specifically, it is shown that the sample complexity required to achieve a target E2E error $\epsilon$ scales as $d/\mathcal{I}_{\mathcal{D}, h_\star}^{\mathrm{CoT}}(\epsilon; \calH)$, where $d$ is a measure of hypothesis class complexity, which can be much faster than standard $d/\epsilon$ rates. Information-theoretic lower bounds in terms of the CoT information are also obtained. Together, these results suggest that CoT information is a fundamental measure of statistical complexity for learning under chain-of-thought supervision.

Related papers

• Revisiting Chain-of-Thought Reasoning under Limited Supervision: Semi-supervised Chain-of-Thought Learning [17.893249958828218]
  We propose a framework that uses unlabeled questions to construct pseudo reasoning supervision.<n>Semi-CoT samples multiple pseudo-CoTs for each unlabeled question, estimates answer-level semantic entropy, and selects low-entropy reasoning chains as reliable pseudo-CoT demonstrations.<n>Pilot experiments on AQuA, SVAMP, GSM8K, and MultiArith show that the entropy gate selects high-precision pseudo-CoTs, with pseudo-answer precision ranging from $91.36%$ to $100%$.
  arXiv  Detail & Related papers  (2026-07-01T22:17:39Z)
• Learning to Reason with Curriculum II: Compositional Generalization [27.242998212645784]
  We show that an autocurriculum-based approach building on Part I of this series achieves better statistical complexity than direct methods.<n>For a setting inspired by supervised fine-tuning (SFT), curriculum facilitates learning from only $2mathcalO(sqrtlog T)$ tokens of supervision.<n>For a setting inspired by reinforcement learning with verifiable rewards (RLVR), we show that curriculum reduces the requirement on the reference model from coverage at the full sequence length $T$ to coverage at a shorter block length $B ll T$.
  arXiv  Detail & Related papers  (2026-06-26T05:09:08Z)
• Transformers Provably Learn to Internalize Chain-of-Thought [65.41010769606844]
  Implicit Chain-of-Thought (ICoT) trains models to internalize intermediate steps within their hidden states.<n>Log-ICoT removes thinking tokens one at a time, reducing the number of stages from linear in $k$ to logarithmic.<n>Experiments on multi-layer transformers confirm the theory and visualize how reasoning is progressively absorbed into deeper layers.
  arXiv  Detail & Related papers  (2026-05-27T15:17:06Z)
• Chain Of Thought Compression: A Theoritical Analysis [24.613200477865572]
  Chain-of-Thought (CoT) has unlocked advanced reasoning abilities of Large Language Models.<n>CoT incurs prohibitive computational costs due to generation of extra tokens.<n>Recent studies show that compressing reasoning steps into latent states, or implicit CoT compression, offers a token-efficient alternative.
  arXiv  Detail & Related papers  (2026-01-29T11:42:03Z)
• Rate optimal learning of equilibria from data [63.14746189846806]
  We close theoretical gaps in Multi-Agent Imitation Learning (MAIL) by characterizing the limits of non-interactive MAIL and presenting the first interactive algorithm with near-optimal sample complexity.<n>For the interactive setting, we introduce a framework that combines reward-free reinforcement learning with interactive MAIL and instantiate it with an algorithm, MAIL-WARM.<n>We provide numerical results that support our theory and illustrate, in environments such as grid worlds, where Behavior Cloning fails to learn.
  arXiv  Detail & Related papers  (2025-10-10T12:28:35Z)
• Reinforced Latent Reasoning for LLM-based Recommendation [83.18146814163308]
  Large Language Models (LLMs) have demonstrated impressive reasoning capabilities in complex problem-solving tasks.<n>Existing methods typically rely on fine-tuning with explicit chain-of-thought (CoT) data.<n>In this work, we explore an alternative approach that shifts from explicit CoT reasoning to compact, information-dense latent reasoning.
  arXiv  Detail & Related papers  (2025-05-25T11:03:45Z)
• When More is Less: Understanding Chain-of-Thought Length in LLMs [51.631483479081645]
  Large Language Models (LLMs) employ Chain-of-Thought (CoT) reasoning to deconstruct complex problems.<n>This paper argues that longer CoTs are often presumed superior, arguing that longer is not always better.
  arXiv  Detail & Related papers  (2025-02-11T05:28:59Z)
• Towards a Sharp Analysis of Offline Policy Learning for $f$-Divergence-Regularized Contextual Bandits [49.96531901205305]
  We analyze $f$-divergence-regularized offline policy learning.<n>For reverse Kullback-Leibler (KL) divergence, we give the first $tildeO(epsilon-1)$ sample complexity under single-policy concentrability.<n>We extend our analysis to dueling bandits, and we believe these results take a significant step toward a comprehensive understanding of $f$-divergence-regularized policy learning.
  arXiv  Detail & Related papers  (2025-02-09T22:14:45Z)
• Unveiling the Mechanisms of Explicit CoT Training: How CoT Enhances Reasoning Generalization [9.191236388401226]
  The integration of explicit Chain-of-Thought (CoT) reasoning into training large language models has advanced their reasoning capabilities, yet the mechanisms by which CoT enhances generalization remain poorly understood.<n>This work investigates (1) textithow CoT training reshapes internal model representations and (2) textitwhy it improves both in-distribution (ID) and out-of-distribution (OOD) reasoning generalization.
  arXiv  Detail & Related papers  (2025-02-07T05:21:13Z)
• From Sparse Dependence to Sparse Attention: Unveiling How Chain-of-Thought Enhances Transformer Sample Efficiency [17.612497960364916]
  Chain-of-thought (CoT) significantly enhances the reasoning performance of large language models (LLM)<n>We demonstrate that CoT can substantially improve sample efficiency even when representation power is sufficient.<n>We show that CoT simplifies the learning process by introducing sparse dependencies among input tokens, and leads to a sparse and interpretable attention.
  arXiv  Detail & Related papers  (2024-10-07T19:45:09Z)
• Training Nonlinear Transformers for Chain-of-Thought Inference: A Theoretical Generalization Analysis [82.51626700527837]
  Chain-of-shift (CoT) is an efficient method that enables the reasoning ability of large language models by augmenting the query using examples with multiple intermediate steps. We show that despite the theoretical success of CoT, it fails to provide an accurate generalization when CoT does.
  arXiv  Detail & Related papers  (2024-10-03T03:12:51Z)
• Unveiling the Statistical Foundations of Chain-of-Thought Prompting Methods [59.779795063072655]
  Chain-of-Thought (CoT) prompting and its variants have gained popularity as effective methods for solving multi-step reasoning problems. We analyze CoT prompting from a statistical estimation perspective, providing a comprehensive characterization of its sample complexity.
  arXiv  Detail & Related papers  (2024-08-25T04:07:18Z)
• On the Provable Advantage of Unsupervised Pretraining [26.065736182939222]
  Unsupervised pretraining is a critical component of modern large-scale machine learning systems. This paper studies a generic framework, where the unsupervised representation learning task is specified by an abstract class of latent variable models. Under a mild ''informative'' condition, our algorithm achieves an excess risk of $tildemathcalO(sqrtmathcalC_Phi/m + sqrtmathcalC_Psi/n)$ for downstream tasks.
  arXiv  Detail & Related papers  (2023-03-02T20:42:05Z)
• A Characterization of Semi-Supervised Adversarially-Robust PAC Learnability [57.502573663108535]
  We study the problem of learning an adversarially robust predictor to test time attacks in the semi-supervised PAC model. We show that there is a significant benefit in semi-supervised robust learning even in the worst-case distribution-free model.
  arXiv  Detail & Related papers  (2022-02-11T03:01:45Z)
• On Function Approximation in Reinforcement Learning: Optimism in the Face of Large State Spaces [208.67848059021915]
  We study the exploration-exploitation tradeoff at the core of reinforcement learning. In particular, we prove that the complexity of the function class $mathcalF$ characterizes the complexity of the function. Our regret bounds are independent of the number of episodes.
  arXiv  Detail & Related papers  (2020-11-09T18:32:22Z)

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.