Many language tasks can be modeled as classification problems where a large language model (LLM) is given a prompt and selects one among many possible answers. We show that the classification error in such problems scales as a power law in the number of classes. This has a dramatic consequence: the prediction error can be reduced substantially by splitting the overall task into a sequence of smaller classification problems, each with the same number of classes ("degree"). This tree-structured decomposition models chain-of-thought (CoT). It has been observed that CoT-based predictors perform better when they "think", i.e., when they develop a deeper tree, thus decomposing the problem into a larger number of steps. We identify a critical threshold for the degree, below which thinking is detrimental, and above which there exists an optimal depth that minimizes the error. It is impossible to surpass this minimal error by increasing the depth of thinking.
Figures & tables
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.036m0.31+0.02 corresponds to an intrinsic dimension of d=6.45 , which is close to the prior estimate of d=15±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 Ai on the input space 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 am2/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 Ai in the input domain 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=mn (answers). The vertical dotted line marks the optimal degree m∗=ed/2≈4.5 , which maximizes reasoning gain given a task of a fixed size N=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., 3n 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 ( ¬ ) 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 x5 in the original tree are highlighted in red. Either path can be used to deduce the correct value of x5 . 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 meff=m1/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.
Appendix figures & tables3 assets
Supplementary material from the paper’s appendix.
Appendix
Figure 9: A repeat of the experiment in Fig. 3 (left) using other dimensionality reduction methods shows constant intrinsic dimension with respect to input length. We used maximum likelihood estimate ( Levina and Bickel, 2004 ) , two-nearest-neighbors ( Facco et al., 2017 ) , Isomap ( Tenenbaum et al., 2000 ) , and Kernel PCA with a radial-basis-function kernel in order from the top left, top right, bottom left and bottom right panels of the figure.
Figure 10: A diagram of the synthetic logical deduction task. Left: The boolean value of the root (shaded dot) is determined by the dot product of a random vector v representing the context, and a fixed reference vector w . The value propagates down the tree according to fixed logical operations (IDENTITY or NOT ¬ ). For example, if 1{v⋅w>0}=1 , then x2=0 and x5=¬x2=1 . Right: Comparison of training targets for reasoning and non-reasoning models. The “Direct” model predicts the final leaf value immediately. The “Reasoning” model must predict the state of every node along the highlighted red path in the tree before predicting the final leaf value.
Figure 11: Diagram of an augmented thinking tree corresponding to the original tree from Fig. 10 . Left: The tree depth is increased from n=2 to rn=3 , creating redundant leaves. The edge operations, identity and negation ( ¬ ) are chosen so that the values of the leaf nodes are consistent with their counterparts on the original tree. The paths to the two leaves corresponding to x5 are highlighted in red. Right: Comparison of training targets. The thinking model can generate multiple valid reasoning traces to deduce the same final answer.
We develop a learning-theoretic framework for understanding Chain of Thought (CoT). We model CoT as the interaction between an answer map and a chain rule that generates intermediate questions autoregressively, and define the reasoning risk of a hypothesis under this interaction. Our first result is a tight canonical decomposition of this risk into two terms with opposing roles: an oracle-trajectory risk (OTR), which captures the benefit of CoT and reduces to a target-domain risk in a domain adaptation problem, and a trajectory-mismatch risk (TMR), which captures the cost of CoT through error accumulation along mismatched reasoning trajectories. We then show that this cost is unavoidable without structure: if any one of the loss, the hypothesis answer map, or the chain rule lacks stability, the TMR can be arbitrarily large even when the OTR is zero and the hypothesis is uniformly close to the ground truth. Conversely, under stability, we prove a tight upper bound on the TMR governed by an exact amplification factor that identifies bounded, linear, and exponential error-growth regimes. Together, these results give a precise theory of when CoT helps, when it hurts, and what controls the transition between the two.
Chain-of-Thought (CoT) prompting is a widely used inference-time technique for improving reasoning, yet its gains are uneven across tasks. We analyze when and why CoT helps by modeling the step-wise reasoning trajectory as a Markov chain. Each intermediate step is a state and the dependence between steps is captured by a transition kernel. Our theory identifies transition alignment, whether instances share a common step-wise transition kernel, as the key determinant of CoT's effectiveness. When transitions are identical across steps, CoT reduces inference-time sample complexity: fewer context sample trajectories suffice to recover the final decision. In contrast, when transitions differ across steps, these gains can vanish. We further quantify how noise in intermediate steps modulates CoT's benefit. Beyond theory, we design synthetic benchmarks that isolate these factors to complement prior results on real-world tasks and to empirically validate our predictions.
Chain-of-thought (CoT) reasoning is the dominant paradigm for inference-time scaling in language models, yet the causal influence of individual steps on the final answer remains poorly understood. In this work, we use answer logits at the end of each reasoning step to estimate each step's causal importance to the final answer and intermediate guesses, shedding light on the answer formation process of several reasoning model families. Across diverse tasks, we find that reasoning typically crosses a commitment boundary, a sharp transition from transient intermediate guesses to a stable, high-confidence answer. This transition often happens in a single step, well before the model's reasoning block ends, and is followed by epiphenomenal CoT steps that leave the final answer probability unaltered. Using attention probes, we show that answer-formation stages can be linearly decoded from the activations of intermediate reasoning steps with high accuracy, showing robust generalization to unseen reasoning tasks. We leverage this property for early-exiting reasoning blocks at the commitment boundary location, reducing the length of CoTs up to 55% with negligible impact on model performance.
Daniel Scalena, Sara Candussio, Luca Bortolussi +3
CLCG, University of Groningen · University of Milano-Bicocca · University of Trieste +1