Publication Type

Conference Proceeding Article

Version

acceptedVersion

Publication Date

12-2026

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, the OOD task risk is controlled by the sum of ID subtask risks, scaled by a depth-independent hard-decoding coefficient Bℓ b = O(k) that is independent of the reasoning depth T. A Rademachercomplexity analysis further gives an atomic excess of order O( T/n), rather than linear in T, due to predictor sharing under a uniform capacity control on the shared class, where n denotes training samples per subtask. For autoregressive Next-Token Prediction, the final-task risk is bounded by the best-in-class atomicrisk term plus a Ok T/n term, where k is the number of output tokens per step. A parity-coupled construction gives a matching lower bound on the atomic excess of the pooled atomic ERM when T ≤ n. Experiments on Atom-Task and GSM8K support the theory, showing that CoT enables short-to-long and compositional generalization, while explicit state tracking is crucial.

Discipline

Artificial Intelligence and Robotics

Research Areas

Intelligent Systems and Optimization

Areas of Excellence

Digital transformation

Publication

Proceedings of the 40th Annual Conference on Neural Information Processing Systems (NeurIPS 2026), Sydney, Australia, December 6-13

First Page

1

Last Page

29

City or Country

Sydney,Australia

Additional URL

https://neurips.cc/virtual/2026/poster/154527

Download

Share

COinS