How does Chain of Thought decompose complex tasks?

Amrut Nadgir; Vijay Balasubramanian; Pratik Chaudhari

Figure 1: Left: Classification error of a vision transformer scales as a power law with the number of classes

m

for semantic groupings (obtained by merging or splitting the original CIFAR-100 superclasses), but is roughly constant for random groupings. The fitted power law (dashed red)

0.036\;m^{0.31}+0.02

corresponds to an intrinsic dimension of

d=6.45

, which is close to the prior estimate of

d=15\pm 5

by Pope et al. (2021) . Random groupings don’t obey the scaling law because they violate our assumption that each class

i

corresponds to a continuous region

\mathcal{A}_{i}

on the input space

\mathcal{X}

. Instead, each class corresponds to a union of disjoint regions. Right: This power-law trend in the test error is also evident in a student-teacher setting where we can vary both the number of classes

m

and the dimensionality of the input space

d

. The lines are power-law fits of the form

a\;m^{2/d}+b

with

a

and

b

fitted to the data and

d

being the actual input dimensionality. Details for both experiments are in Section A.1 .

Figure 2: Illustration of regions

\mathcal{A}_{i}

in the input domain

\mathcal{X}

corresponding to different classes

i

. With fewer classes (left), regions are well-separated (long arrow). As the number of classes increases (right), regions are packed more densely which reduces the distance between them. This reduced margin forces the learned function to change rapidly, requiring a higher Lipschitz constant.

Figure 3: Intrinsic dimension of the sequence (left) and mean entropy of the predicted next-token distribution (right) for Qwen3-32B ( Yang et al., 2025 ) computed using 4,407 samples from GSM8k ( Cobbe et al., 2021 ) (dark blue) with answers that have at least 100 tokens. For WikiText-2 ( Merity et al., 2016 ) (light blue) we use 3,045 samples, which are at least 167 tokens long, The X-axis represents the length of the sequence. For GSM8k we do not include the length of the prompt in the plot (although the model has the prompt in its context when it produces the answer). For WikiText-2, we treat the first 67 tokens as the “prompt” to horizontally align the curves. The “GSM8k Direct” baseline (dashed blue) forces the model to output the answer immediately by adding the text “Only output the answer.” to the prompt (with dimension and entropy computed using the first generated token, i.e., the answer). Left: Intrinsic dimension of the latent space

d

(number of dimensions of principal components analysis that capture 80% of the variance) is similar for both mathematical tasks (GSM8k and GSM8k Direct) relative to a generic baseline (WikiText). The dimensionality

d

is relatively constant with the text length. Section A.2 shows the same result with other, non-linear, dimensionality reduction methods. Right: Mean entropy of predicted next-token is small for GSM8k compared to predicting the answer directly (GSM8k-Direct). This shows that the model is more confident when predicting on human-generated reasoning traces, as compared to predicting the answers directly. The mean entropy of the predicted next token in reasoning traces of GSM8k (dark blue) is lower than that of WikiText (light blue), indicating that a well-trained model (Qwen3-32B) predicts more confidently on the former. Direct prediction of the answer in a reasoning task (GSM8k-Direct) is as unconstrained as predicting the next token in English text (WikiText), as indicated by the similarity of their entropies.

Figure 4: Theoretical reasoning gain as a function of the degree

m

and depth

n

, computed using Eq. 7 . Non-integer values of

m

and

n

are shown for completeness. The dimension is

d=3

and we set

cD^{-1/d}=10^{-12}

for the visualization. The black dashed curve is the boundary above which gain is positive. Gray curves are contours of the number of leaves

N=m^{n}

(answers). The vertical dotted line marks the optimal degree

m^{*}=e^{d/2}\approx 4.5

, which maximizes reasoning gain given a task of a fixed size

N=\text{const.}

Figure 5: Left: A synthetic task where data exhibits a tree structure, see the narrative for a description. Middle: Transformers trained, using the standard next token prediction objective, on such tasks with different degrees and depths of the tree exhibit the smallest error when the degree of the tree is the same at each layer (“structure” equal to 1). Each curve corresponds to a tree of a fixed depth

n

and degree 3, i.e.,

3^{n}

leaves. A structure equal to 1.0 corresponds to a tree with a constant degree of

m=3

across layers, while smaller values correspond to trees whose degree is different at different depths. Right: The degree of our synthetic task (x-axis) is positively correlated with the degree of a prefix-tree of tokenized reasoning traces (y-axis). To create the prefix-tree, we trained a byte-pair encoding tokenizer with a vocabulary size of 500 on all possible reasoning traces.

Figure 6: A “thinking” tree corresponding to the one in Fig. 5 (left) with increased depth from 2 to 3 and redundant leaves. Intermediate nodes in this tree are labeled with “Y” instead of “X”. Each leaf in the original tree in Fig. 5 (left) is associated with two leaves in this deeper tree. The identity and negation (

\neg

) operations on the edges are chosen so that the binary values of leaves are consistent between both trees. The two reasoning paths in the thinking tree corresponding to the leaf

x_{5}

in the original tree are highlighted in red. Either path can be used to deduce the correct value of

x_{5}

. The “Thinking Mode” box on the right has examples of chains of thought corresponding to both paths.

Figure 7: Thinking, i.e., using a larger depth than necessary, is detrimental when the degree

m

is below a threshold

m^{*}

and beneficial otherwise. Left: Heatmap values are proportional to the theoretical accuracy gain from thinking with a depth factor

r>1

compared to using

r=1

(CoT without redundancy in the tree). We use a dimension of

d=2

and set

cD^{-1/d}=0.01

for the visualization. Non-integer values of

m

are represented for completeness. The black dashed curve indicates when the thinking gain is zero. The green line indicates the optimal depth factor

r

such that

m_{\text{eff}}=m^{1/r}=m^{*}

. Right: The increase in accuracy from thinking for a transformer trained to solve synthetic reasoning tasks of depth

n=3

. Across different depth factors

r

, thinking is detrimental for smaller degrees and becomes beneficial as the degree increases. Tasks with redundant trees (more leaves than the number of distinct answers) were created using a random many-to-one assignment of paths in the expanded tree. Details are provided in Section A.4 .

Figure 8: Top Left: Test error is minimized at intermediate values of the depth expansion factor

r

across varying degrees

m

. The task is the same as in Fig. 7 (right). Details are provided in Section A.4 . Top Right and Bottom: Test error of Qwen2.5-7B-Instruct ( Yang and others, 2025 ) on the GSM8k ( Cobbe et al., 2021 ) and MATH-500 ( Hendrycks et al., 2021 ; Lightman et al., 2023 ) datasets (top right) and of Deepseek-V3 ( Liu et al., 2025a ) on AIME problems from 2022-2024 ( 1 ) (bottom) is minimized at intermediate reasoning lengths. The error-bars depict the standard error of the mean across 5 replicate experiments. Instructions to the models were varied to elicit different mean reasoning lengths across the dataset. The AIME problems have variable difficulty so there is no single optimal reasoning length across the entire dataset. We therefore ordered the problems according to the mean reasoning length used to solve them (across replicates and prompts), and split them into four groups based on percentile P0-20, P20-47, P47-84 and P83-100 from left to right. This split was chosen to achieve the clearest signal. The most difficult (rightmost condition) does not show a clear optimal reasoning depth, but demonstrates the overthinking phenomenon where increasing reasoning length can degrade performance. See Section A.5 for details.

How does Chain of Thought decompose complex tasks?

Abstract

Figures & tables

Appendix

CoT Reasoning

On the Cost and Benefit of Chain of Thought: A Learning-Theoretic Perspective

When does Chain-of-Thought Help: A Markovian Perspective

Beyond the Commitment Boundary: Probing Epiphenomenal Chain-of-Thought in Large Reasoning Models

Abstract

CoT Reasoning

Explore similar work

On the Cost and Benefit of Chain of Thought: A Learning-Theoretic Perspective

When does Chain-of-Thought Help: A Markovian Perspective

Beyond the Commitment Boundary: Probing Epiphenomenal Chain-of-Thought in Large Reasoning Models