An Asymptotic Theory of Chain-of-Thought in In-Context Learning

• URL: http://arxiv.org/abs/2606.03217v1
• Date: Tue, 02 Jun 2026 06:23:31 GMT
• Title: An Asymptotic Theory of Chain-of-Thought in In-Context Learning
• Abstract summary: Chain-of-thought (CoT) reasoning has become a widely used mechanism for eliciting multi-step reasoning in large language models.<n>We study a theoretically solvable model of CoT for in-context weight prediction in linear regression.<n>We derive an exact formula for the generalization error as a function of reasoning depth, pretraining data amount, and context length.
• Score: 34.69440744042684
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Chain-of-thought (CoT) reasoning has become a widely used mechanism for eliciting multi-step reasoning in large language models by generating intermediate reasoning steps at inference time. Yet the scaling behavior of generalization with CoT depth remains poorly understood. To address this question, we study a theoretically solvable model of CoT for in-context weight prediction in linear regression, where test-time reasoning is represented as an iterative refinement of the weight-parameter estimate. Using tools from random matrix theory under high-dimensional asymptotics, we derive an exact formula for the generalization error as a function of reasoning depth, pretraining data amount, and context length. Our analysis reveals a sharp phase transition separating exponential and polynomial improvement, saturation, and overthinking, and characterizes how the optimal reasoning depth scales. We further show that deeper reasoning is most effective with sufficiently rich pretraining and in-context information, whereas limited pretraining or context makes longer reasoning prone to error amplification or saturation. We also validate these predictions through experiments on fully learned linear attention and softmax attention models. Our results provide a unified theoretical account of how test-time CoT depth affects generalization.

Related papers

• Why Depth Matters in Parallelizable Sequence Models: A Lie Algebraic View [15.326860959311622]
  We examine the bounds on error and how error scales when models operate outside of their expressivity regimes.<n>Our theory formulates a correspondence between the depth of a sequence model and the tower of Lie algebra extensions.<n>We analytically derive an approximation error bound and show that error diminishes exponentially as the depth increases.
  arXiv  Detail & Related papers  (2026-03-05T16:16:13Z)
• On Multi-Step Theorem Prediction via Non-Parametric Structural Priors [50.16583672681106]
  In this work, we explore training-free theorem prediction through the lens of in-context learning (ICL)<n>We propose Theorem Precedence Graphs, which encode temporal dependencies from historical solution traces as directed graphs, and impose explicit topological constraints that effectively prune the search space during inference.<n>Experiments on the FormalGeo7k benchmark show that our method achieves 89.29% accuracy, substantially outperforming ICL baselines and matching state-of-the-art supervised models.
  arXiv  Detail & Related papers  (2026-03-05T06:08:50Z)
• Conjugate Learning Theory: Uncovering the Mechanisms of Trainability and Generalization in Deep Neural Networks [0.0]
  We develop a conjugate learning theoretical framework based on convex conjugate duality to characterize this learnability property.<n>We demonstrate that training deep neural networks (DNNs) with mini-batch descent (SGD) achieves global optima of empirical risk.<n>We derive deterministic and probabilistic bounds on generalization error based on conditional generalized entropy measures.
  arXiv  Detail & Related papers  (2026-02-18T04:26:55Z)
• How and Why LLMs Generalize: A Fine-Grained Analysis of LLM Reasoning from Cognitive Behaviors to Low-Level Patterns [51.02752099869218]
  Large Language Models (LLMs) display strikingly different generalization behaviors.<n>We introduce a novel benchmark that decomposes reasoning into atomic core skills.<n>We show that RL-tuned models maintain more stable behavioral profiles and resist collapse in reasoning skills, whereas SFT models exhibit sharper drift and overfit to surface patterns.
  arXiv  Detail & Related papers  (2025-12-30T08:16:20Z)
• Transformers Provably Learn Chain-of-Thought Reasoning with Length Generalization [53.89723291716722]
  A crucial question about AI reasoning is whether models can extrapolate learned reasoning patterns to solve harder tasks with longer chain-of-thought (CoT)<n>We mathematically prove how the algebraic structure of state-tracking problems governs the degree of extrapolation of the learned CoT.<n>We provide the first optimization guarantee that constant-depth transformers provably learn $mathsfNC1$-complete problems with CoT.
  arXiv  Detail & Related papers  (2025-11-10T18:40:24Z)
• Provable Benefit of Curriculum in Transformer Tree-Reasoning Post-Training [76.12556589212666]
  We show that curriculum post-training avoids the exponential complexity bottleneck.<n>Under outcome-only reward signals, reinforcement learning finetuning achieves high accuracy with sample complexity.<n>We establish guarantees for test-time scaling, where curriculum-aware querying reduces both reward oracle calls and sampling cost from exponential to order.
  arXiv  Detail & Related papers  (2025-11-10T18:29:54Z)
• The Curse of CoT: On the Limitations of Chain-of-Thought in In-Context Learning [56.574829311863446]
  Chain-of-Thought (CoT) prompting has been widely recognized for its ability to enhance reasoning capabilities in large language models (LLMs)<n>We demonstrate that CoT and its reasoning variants consistently underperform direct answering across varying model scales and benchmark complexities.<n>Our analysis uncovers a fundamental hybrid mechanism of explicit-implicit reasoning driving CoT's performance in pattern-based ICL.
  arXiv  Detail & Related papers  (2025-04-07T13:51:06Z)
• Do Larger Language Models Generalize Better? A Scaling Law for Implicit Reasoning at Pretraining Time [73.22651918134808]
  This work shows counterintuitive effects of model size scaling and provides new insights into the relationship between scaling and reasoning in language models (LMs)<n>We pretrain LMs from scratch on a synthetic implicit multihop reasoning environment designed to replicate the structure and distribution of real-world large-scale knowledge graphs.<n>We then assess the LMs' ability to complete the missing edges in the graph, which requires multi-hop reasoning that can be viewed as a simplification of implicit reasoning during real-world pretraining.
  arXiv  Detail & Related papers  (2025-04-04T17:57:22Z)
• In-Context Linear Regression Demystified: Training Dynamics and Mechanistic Interpretability of Multi-Head Softmax Attention [52.159541540613915]
  We study how multi-head softmax attention models are trained to perform in-context learning on linear data.<n>Our results reveal that in-context learning ability emerges from the trained transformer as an aggregated effect of its architecture and the underlying data distribution.
  arXiv  Detail & Related papers  (2025-03-17T02:00:49Z)
• The $\varphi$ Curve: The Shape of Generalization through the Lens of Norm-based Capacity Control [23.293525050286224]
  We consider norm-based capacity measures and develop our study for random features based estimators.<n>We provide a precise characterization of how the estimator's norm concentrates and how it governs the associated test error.<n>This confirms that more classical U-shaped behavior is recovered considering appropriate capacity measures based on models norms rather than size.
  arXiv  Detail & Related papers  (2025-02-03T18:10:40Z)
• Understanding Forgetting in Continual Learning with Linear Regression [21.8755265936716]
  Continual learning, focused on sequentially learning multiple tasks, has gained significant attention recently. We provide a general theoretical analysis of forgetting in the linear regression model via Gradient Descent. We demonstrate that, given a sufficiently large data size, the arrangement of tasks in a sequence, where tasks with larger eigenvalues in their population data covariance matrices are trained later, tends to result in increased forgetting.
  arXiv  Detail & Related papers  (2024-05-27T18:33:37Z)
• Beyond variance reduction: Understanding the true impact of baselines on policy optimization [24.09670734037029]
  We show that learning dynamics are governed by the curvature of the loss function and the noise of the gradient estimates. We present theoretical results showing that, at least for bandit problems, curvature and noise are not sufficient to explain the learning dynamics.
  arXiv  Detail & Related papers  (2020-08-31T17:52:09Z)

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.