Understanding the Out-of-Distribution Generalization of Chain-of-Thought Reasoning in LLMs

Abstract

Chain-of-Thought (CoT) reasoning substantially improves Large Language Models (LLMs), yet its out-of-distribution (OOD) generalization mechanism remains theoretically underexplored. We study CoT as compositional OOD generalization: the target task lacks complete reasoning trajectories or direct input-output pairs, while training provides only in-distribution (ID) atomic step data. We show that CoT generalizes by repeatedly applying a shared single-step predictor to compose reusable ID transitions. Theoretically, let T denote the number of reasoning steps in the target task, n the number of training samples per sub-task, and k the number of output tokens per step; then the OOD task risk is controlled by the sum of the ID sub-task risks, scaled by a coefficient of order 𝒪(k) that is independent of T, although the summed risk itself may still grow with T. A Rademacher-complexity analysis further shows that the estimation term is of order 𝒪(√(T/n)), rather than linear in T, due to predictor sharing under a uniform capacity control on the shared class. For autoregressive Next-Token Prediction, the final-task risk is bounded by the best-in-class step-level risk scaled by the same coefficient of order 𝒪(k), plus an estimation term of order 𝒪̃(k√(T/n)). A parity-coupled construction further shows that, for the sub-task empirical risk minimizer, the expected final-task risk is at least the best in-class risk plus Ω(√(T/n)) when T≤ n. Experiments on Atom-Task and GSM8K support the theory: CoT enables short-to-long and compositional generalization, while explicit state tracking is crucial. Our code is available at https://github.com/maxliang114514/CoT-OOD.

Certified by Abstention: Distribution-Free Guarantees for Chain-of-Thought Verifiers at Small Calibration Budgets
Arjun Balaji
arXiv7 Oct 2026PreprintCC BY 4.0Full textStatisticsarXiv
The Surprising Expressivity of a Single Neuron with Autoregressive Chain-of-Thought
Roey Magen, Nirmit Joshi, Gal Vardi
arXiv12 Oct 2026PreprintCC BY 4.0Full textStatisticsarXiv
An Asymptotic Theory of Chain-of-Thought in In-Context Learning
Kaito Takanami, Cengiz Pehlevan
arXiv27 Oct 2026PreprintCC BY 4.0Full textStatistics Condensed matterarXiv
How Does Chain-of-Thought Supervision Teach Models to Reason? A Theoretical Analysis
Kaito Takanami, Cengiz Pehlevan
arXiv1 Nov 2026PreprintCC BY 4.0Full textStatistics Condensed matterarXiv
What Does Chain-of-Thought Entropy Measure? A Channel Audit of Scaffolding, Routing, and Content
Marios Papamichalis, Regina Ruane
arXiv1 Sep 2026PreprintCC BY 4.0Full textStatisticsarXiv

Cite

BibTeX RIS

BibTeX

@misc{liang2026understanding,
  title = {{Understanding the Out-of-Distribution Generalization of Chain-of-Thought Reasoning in LLMs}},
  author = {Nuo-Jing Liang and Xiao-Tong Yuan and Pan Zhou},
  howpublished = {arXiv},
  year = {2026},
  month = nov,
  doi = {10.48550/arxiv.2611.06438},
  eprint = {2611.06438},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.06438},
  note = {CC BY 4.0},
}

RIS

TY  - UNPB
TI  - Understanding the Out-of-Distribution Generalization of Chain-of-Thought Reasoning in LLMs
AU  - Nuo-Jing Liang
AU  - Xiao-Tong Yuan
AU  - Pan Zhou
PY  - 2026
DA  - 2026/11/04
PB  - arXiv
DO  - 10.48550/arxiv.2611.06438
UR  - https://arxiv.org/abs/2611.06438
AB  - Chain-of-Thought (CoT) reasoning substantially improves Large Language Models (LLMs), yet its out-of-distribution (OOD) generalization mechanism remains theoretically underexplored. We study CoT as compositional OOD generalization: the target task lacks complete reasoning trajectories or direct input-output pairs, while training provides only in-distribution (ID) atomic step data. We show that CoT generalizes by repeatedly applying a shared single-step predictor to compose reusable ID transitions. Theoretically, let T denote the number of reasoning steps in the target task, n the number of training samples per sub-task, and k the number of output tokens per step; then the OOD task risk is controlled by the sum of the ID sub-task risks, scaled by a coefficient of order 𝒪(k) that is independent of T, although the summed risk itself may still grow with T. A Rademacher-complexity analysis further shows that the estimation term is of order 𝒪(√(T/n)), rather than linear in T, due to predictor sharing under a uniform capacity control on the shared class. For autoregressive Next-Token Prediction, the final-task risk is bounded by the best-in-class step-level risk scaled by the same coefficient of order 𝒪(k), plus an estimation term of order 𝒪̃(k√(T/n)). A parity-coupled construction further shows that, for the sub-task empirical risk minimizer, the expected final-task risk is at least the best in-class risk plus Ω(√(T/n)) when T≤ n. Experiments on Atom-Task and GSM8K support the theory: CoT enables short-to-long and compositional generalization, while explicit state tracking is crucial. Our code is available at https://github.com/maxliang114514/CoT-OOD.
ER  -

Abstract

Related

Cite