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

Nuo-Jing Liang; Xiao-Tong Yuan; Pan Zhou

cs.LGNov 4, 2026

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

Authors: Nuo-Jing Liang, Xiao-Tong Yuan, Pan Zhou

Organizations: School of Intelligence Science and Technology, Nanjing University · Singapore Management University

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 $\mathcal{O}(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 $\mathcal{O}(\sqrt{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 $\mathcal{O}(k)$ , plus an estimation term of order $\widetilde{\mathcal{O}}\big(k\sqrt{T/n}\big)$ . 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 $Ω(\sqrt{T/n})$ when $T\le 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.

Figures & tables

Figure 1: CoT as compositional OOD generalization. Left: without CoT, the model must learn a direct mapping from input

z_{0}

to final answer

\Delta z_{T}

, whose target distribution may be unavailable during training. With CoT, the same predictor is repeatedly applied to in-distribution step distributions, mapping each state

z_{i-1}

to update

\Delta z_{i}

. Right: a two-hop translation example solves an unseen English-to-German query by composing learned English-to-French and French-to-German steps.

Figure 2: Comparison of complete vs. incomplete CoT state recordings.

Figure 3: Each entry is a mean over 3 seeds (42, 2026, 12345). Atom-Task results when varying (a) test depth, (b) training sample size, and (c) inference-time examples; in (b) the horizontal axis is

1/\sqrt{n}

, where

n

is the sample size in units of the full budget (

10\%

20\%

50\%

100\%

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

Symbol	Meaning
$\mathcal{V}$	Vocabulary of size $n_{v}$ .
$\mathrm{hard}(\cdot)$	Operator converting probability distributions to discrete tokens via argmax.
$\mathcal{D},\mathcal{D}_{i}$	Target problem distribution, and data distribution for the $i$ -th reasoning step.
$\Psi,\psi,\psi_{*}$	Hypothesis class for single-step functions, learned single-step function, and ground-truth mapping (not necessarily within $\Psi$ ).
$\bar{\psi}$	State transition mapping, $\bar{\psi}(z):=z[k+1:m]\oplus\mathrm{hard}(\psi(z))$ , representing the input state for the next step.
$\mathcal{G},\mathcal{H},g,h$	Hypothesis classes and functions for the token predictor and representation learner.

Appendix

Table 4: Summary of Main Notations

Table 5

CoT Reasoning

Chain-of-thought (CoT) reasoning studies how language models use intermediate steps, visible or latent, to solve multi-step tasks.

See all 234 papers

May 28, 2025

Learning Composable Chains-of-Thought

A common approach for teaching large language models (LLMs) to reason is to train on chain-of-thought (CoT) traces of in-distribution reasoning problems, but such annotated data is costly to obtain for every problem of interest. We want reasoning models to generalize beyond their training distribution, and ideally to generalize compositionally: combine atomic reasoning skills to solve harder, unseen reasoning tasks. We take a step towards compositional generalization of reasoning skills when addressing a target compositional task that has no labeled CoT data. We find that simply training models on CoT data of atomic tasks leads to limited generalization, but minimally modifying CoT formats of constituent atomic tasks to be composable can lead to improvements. We can train "atomic CoT" models on the atomic tasks with Composable CoT data and combine them with multitask learning or model merging for better zero-shot performance on the target compositional task. Such a combined model can be further bootstrapped on a small amount of compositional data using rejection sampling fine-tuning (RFT). Results on string operations and natural language skill compositions show that training LLMs on Composable CoT outperforms multitask learning and continued fine-tuning baselines within a given training data budget.

Fangcong Yin, Zeyu Leo Liu, Liu Leqi +2

The University of Texas at Austin · Princeton University

LLM Fine-Tuning CoT Reasoning LLM Training Compositional Generalization LLM Reasoning

Ask PDF

Feb 17, 2026

On the Out-of-Distribution Generalization of Reasoning in Multimodal LLMs for Simple Visual Planning Tasks

Integrating reasoning in large language models and large vision-language models has recently led to significant improvement of their capabilities. However, the generalization of reasoning models is still vaguely defined and poorly understood. In this work, we present an evaluation framework to rigorously examine how well chain-of-thought (CoT) approaches generalize on a simple planning task. Specifically, we consider a grid-based navigation task in which a model is provided with a map and must output a sequence of moves that guides a player from a start position to a goal while avoiding obstacles. The versatility of the task and its data allows us to fine-tune model variants using different input representations (visual and textual) and CoT reasoning strategies, and systematically evaluate them under both in-distribution (ID) and out-of-distribution (OOD) test conditions. Our experiments show that, while CoT reasoning improves in-distribution generalization across all representations, out-of-distribution generalization (e.g., to larger maps) remains very limited in most cases when controlling for trivial matches with the ID data. Surprisingly, we find that reasoning traces which combine multiple text formats yield the best (and non-trivial) OOD generalization. Finally, purely text-based models consistently outperform those utilizing image-based inputs, including a recently proposed approach relying on latent space reasoning.

Yannic Neuhaus, Nicolas Flammarion, Matthias Hein +1

Tübingen AI Center – University of Tübingen · EPFL · ELLIS Institute Finland – Aalto University

OOD Generalization Multimodal Reasoning VLM Reasoning Multimodal CoT Reasoning

Ask PDF

Feb 24, 2026

Tool Use Reduces Depth-Induced Collapse in OOD Reasoning

Humans can apply ideas learned in one context to substantially different situations. We call this process of searching for and constructing novel recombinations of learned relationships to solve new problems out-of-distribution (OOD) reasoning. The capacity for large language models (LLMs) to support OOD reasoning underpins proposals for generally intelligent systems. However, this property is challenging to measure because most problems admit many decompositions, some involving shallow subproblems and others involving subproblems that may have been memorized from the training data. This makes it difficult to determine how much compositional reasoning a model must actually perform. Uncertainty about training distributions, how to measure a datapoint's distance from a training distribution, and the exponential number of ways to decompose most tasks make it intractable to robustly measure any modern LLM's OOD-reasoning capacity on standard natural-language tasks. In this work, we introduce a benchmark in which a model progressively solves a Boolean circuit over

GF(2)

from data. This benchmark is both minimal, isolating OOD reasoning from these confounding factors, and general, as any computable function can be represented as a sufficiently large

GF(2)

polynomial. We find that standalone models' next-step accuracy collapses as depth grows. In contrast, tool use through the synthesis and execution of code prevents this collapse in both small and frontier LLMs. These results indicate that synthesizing tools play a crucial role in supporting OOD reasoning.

David Koplow, Tomer Galanti, Tomaso Poggio

Massachusetts Institute of Technology · Texas A&M University

OOD Generalization LLM Tool Use Algorithmic Reasoning

Ask PDF

Abstract

CoT Reasoning

Explore similar work

Learning Composable Chains-of-Thought

On the Out-of-Distribution Generalization of Reasoning in Multimodal LLMs for Simple Visual Planning Tasks

Tool Use Reduces Depth-Induced Collapse in OOD Reasoning