Why Chain-of-Thought Helps: A Statistical Query Theory of Intermediate Reasoning

Chain-of-thought (CoT) supervision exposes intermediate variables in addition to inputs and final outputs. We develop a statistical-query (SQ) theory of when these intermediate traces make an unknown compositional computation identifiable. The target is a Boolean function computed by an unknown directed acyclic graph (DAG) whose local gates have bounded fan-in. With CoT, queries may depend on the inputs, intermediate variables, and outputs; without CoT, they may depend only on the inputs and outputs. Why can intermediate reasoning steps make a learning problem substantially easier than learning from final answers alone? We address this question in the statistical query framework. Our central observation is that chain-of-thought supervision can expose a hidden compositional structure that is statistically inaccessible at the input-output level. We model this structure as an unknown directed acyclic graph of simple local computations and show that, under natural distributional conditions, a learner can recover an equivalent computation without knowing its connections, local rules, or ordering in advance. The result clarifies when reasoning traces are informative: the relevant local configurations must occur often enough to be observed, and genuine computational dependencies must be distinguishable from spurious ones. Under these conditions, a globally difficult learning problem reduces to a collection of tractable local identification problems. For subset parity, this produces an exponential separation between learning from final answers and learning from intermediate traces, while binary addition illustrates how a long computation can be assembled from simple local steps. More broadly, our results distinguish compact representability from statistical learnability and identify the data distribution and the information exposed by the trace as central determinants of whether chain-of-thought supervision is useful.