acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

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.

Primary area:
learning theory
Keywords:
chain-of-thought, intermediate reasoning, SQ model

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_CZSVOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies the statistical query (SQ) learnability of Boolean functions specified by a DAG with and without intermediate supervision (CoT). The main result states that, analogously to previous results on learning with intermediate supervision, trace supervision makes functions learnable that would otherwise not be. In particular, the paper shows that general DAGs with bounded fan in are SQ-learnable given access to queries that can enquire about functions of the intermediate activations as well. This relies on two natural distributional assumptions that make the topology of the graph discoverable. This allows the authors to give another view of the known exponential gap in the sample complexity of subset parity with and without intermediate supervision.

Critical strengths
  • The work extends a growing body of literature on how CoT not only makes models more powerful, but also makes the learning problem easier. In this realm, the main result adds a welcome generalization of existing results, which mostly consider subset parity.
    • I particularly like the fact that the results abstract away architectural considerations and thus hold beyond
  • I think the problem setup is quite natural and the two main assumptions are well-justified.
  • The results are easy to follow and are understandable. The proofs also seem correct.
Critical weaknesses
  • This is not a big weakness, but I feel like some writing and exposition could be improved. For example, the first part of the Abstract (Lines 11–23) repeats many points twice, and Fig. 1 is never even mentioned in the text (nor are the experiments that produced it).
    • Similarly, the Introduction jumps ahead of the exposition a few times, such as saying that “the learner may query arbitrary bounded functions” on Line 63 without explaining what “querying functions” means.
    • Smaller inconsistencies:
      • “and (3, 1/8, 1/16)” in Cor. 1 comes out of nowhere.
  • Some additional results are promised in the Introduction but never elaborated on. For example, the effects of imperfect/noisy observations are briefly touched upon in the Introduction and never mentioned again. The same holds for propositional compositional reasoning.
  • I am familiar with some existing results on CoT learnability (e.g., the Wies and Kim&Suzuki references), but less so with the standard SQ literature. It would be helpful to understand the inspirations behind the algorithms and the proofs. For example, the algorithm at a high level looks like an exhaustive search over potential parent sets, and I imagine it has some existing analogues. Similarly, I am not sure whether the assumptions made have some precedent in the literature.
    • In general, I believe my assessment of the paper could be better if I understood better how it contrasts with existing (classic) SQ learning literature.
  • Connected to Fig. 1 not being elaborated on in the main text, I am not sure what the experiments are even supposed to show: If they are simply running the enumeration algorithms, they follow the derived complexities by construction, so the agreement is expected.
  • The tree-learning result is unclear to me. The authors provide a CoT-learning algorithm and classify it as “similar to the parity one”, but I don’t see the same exponential gap as in parity. Can such trees not be learned without CoT supervision (I suppose they could be, since conjunctions are not hard to learn)?
Questions for authors
  1. Can these proof techniques or results be used to understand the SQ learnability of more general circuits. I suppose the bounded fan-in requirement narrows the scope to NC classes, but would the results in any way translate to growing-depth circuit families (e.g., NCd\text{NC}^{d})?
  2. On a similar note, would the algorithm of Section 4.1 work without knowing ss (could one loop the algorithm with growing values of ss, for example)?
  3. How easy are the derived results to specialize to specific neural architectures?
Reviewer_z6mTOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper investigates why chain-of-thought (CoT) supervision can make learning easier from a statistical-query perspective. The authors model the underlying computation as a DAG consisting of simple local functions and show that, under certain assumptions, access to intermediate reasoning steps enables efficient recovery of the computation. The paper also provides theoretical examples, including parity, that demonstrate an exponential separation in query complexity between learning with and without CoT.

Critical strengths

I find the research question interesting and potentially important. The paper provides a theoretical perspective on why intermediate supervision can help learning, rather than focusing on a particular model architecture or optimization algorithm. The connection between CoT supervision and learning simpler local computations is intuitive and provides a useful way to think about the benefits of CoT.

Critical weaknesses

My main concern is the applicability of the theoretical framework to practical learning scenarios. While the paper provides several mathematical examples, it is less clear how the assumptions and conclusions translate to realistic CoT supervision in modern language models. More concrete empirical motivation would help readers understand the scope and significance of the theoretical results.

Questions for authors
  1. Could the authors provide a concrete, empirically motivated example where the proposed theoretical framework applies? In particular, it would be helpful to understand how the DAG formulation and its assumptions relate to realistic CoT supervision in language models.

  2. The theoretical guarantees rely on observing intermediate variables and satisfying coverage and separation conditions. How restrictive are these assumptions in practice? For example, how would noisy or incomplete reasoning traces affect the applicability of the conclusions?

Reviewer_JZK4OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper presents a statistical query theory to explain the benefit of chain of thought. Denote X,Z,YX,Z,Y as input, intermediate result, output, respectively. Without CoT, the query can be only functions of (X,Y)(X,Y); with CoT, the query can be functions of (X,Z,Y)(X,Z,Y). This paper consider function class that is induced by a DAG with bounded parent size. By proposing an algorithm that simultaneously constructs a topological order, Theorem 1 shows the query complexity of this algorithm. Example on finite-field multiplication shows the complexity separation between without CoT and with CoT.

Critical strengths
  1. This paper provides a statistical query framework to analyze the efficiency of CoT.
Critical weaknesses
  1. This paper does not provide an AI use statement. According to the ICLR 2027 author guidelines, this section is required.

  2. The experiments are limited to Figure 1. More experiments explanations and results on other tasks (e.g., finite-field multiplication, decision-tree) is helpful.

  3. Although this paper proposes an algorithm under the statistical query framework, it is unclear that how this is reflected in true LLM training with CoT. Also, the complexity separation between CoT and without CoT is only presented under parity and finite-field multiplication task, which limits the generalizability of the complexity separation result.

Questions for authors

Please refer to the weaknesses part.

  1. Could the authors provide further experimental results on other tasks, like finite-field multiplication, decision-tree?

  2. Could the complexity separation between CoT and without CoT be presented under the general setup in this paper, i.e., function class that is induced by a DAG with bounded parent size?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.