How does Chain of Thought decompose complex tasks?

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.

We explain exactly when and why reasoning before generating the final answer improves the accuracy of large language models (LLMs). This is because of a tree-like structure in the data which decomposes a difficult task into a sequence of simpler sub-tasks. We show that accuracy is maximized when the reasoning tree is "maximally structured" (has an equal degree at each layer). Furthermore, we show that there is an optimal reasoning depth for a task. You cannot improve in accuracy by extending reasoning beyond this depth. These results are supported by experiments that range in scale from training small models to solve synthetic tasks up to using LLMs to solve mathematical reasoning problems. Our results indicate that LLMs should be trained to output highly structured reasoning traces. This is not the case for most reasoning in LLMs, which have been shown to be highly inefficient. We also challenge the prevailing narrative that long reasoning = better. Longer reasoning is, in many cases, just inefficient. Instead of arbitrarily increasing the reasoning length at test-time, we should strive towards using higher quality, structured data.