CoT Information: Improved Sample Complexity under Chain-of-Thought Supervision
Authors: Awni Altabaa
Omar Montasser
John Lafferty
Venue: NeurIPS 2025 spotlight ()
Keywords: chain-of-thought
learning theory
statistical learning theory
PAC learning
sample complexity
Primary area: theory
TL;DR: This paper develops a statistical theory for learning under chain-of-thought supervision.

Abstract: Learning complex functions that involve multi-step reasoning poses a significant challenge for standard supervised learning from input-output examples. Chain-of-thought (CoT) supervision, which augments training data with intermediate reasoning steps to provide a richer learning signal, has driven recent advances in large language model reasoning. This paper develops a statistical theory of learning under CoT supervision. Central to the theory is the *CoT information*, which measures the additional discriminative power offered by the chain-of-thought for distinguishing hypotheses with different end-to-end behaviors. The main theoretical results demonstrate how CoT supervision can yield significantly faster learning rates compared to standard end-to-end supervision, with both upper bounds and information-theoretic lower bounds characterized by the CoT information.

CoT Information: Improved Sample Complexity under Chain-of-Thought Supervision
Awni Altabaa Statistics & Data Science
Omar Montasser Statistics & Data Science
John Lafferty
Statistics & Data Science
Yale University awni tabbaaayaaaaalyae.eo edu
Yale University
Yale University
omar waaa.onttassee@@yle..cmmm
John.laffertyyylll edu
Abstract
Learning complex functions that involve multi-step reasoning poses a significant challenge for standard supervised learning from input-output examples. Chain- of-thought (CoT) supervision, which augments training data with intermediate reasoning steps provide richer learning signal, has driven recent advances in large language model reasoning. This paper develops a statistical theory of learn- ing under CoT supervision. Central to the theory the CoT information, which measures the additional discriminative power offered by the chain-of-though for distinguishing hypotheses with different end-to-end behaviors. The main theoreti- cal results demonstrate how CoT supervision can yield significantly faster learning rates compared to standard end-to-end supervision, with both upper bounds and information-thhorree lower bounds characterized by the CoT information.
Introduction
Chain-of-thoughr (CoT) reasoning has been a driving force behind recent advances in the capa- bilities of large language models. While chain-of- ofothhthtt began as a prompting technique [1-3], CoT-ssuerviieed training is now an important component of the post-training pipeline for large lan- guage models, and has been found to highly effective in recent empirical research [4-6].
This paper proposes concepts in statistical learning theory that are aimed gaining insight into chain-of-thon to-touoo learning. Consider the following concrete example the theoretical framework to be developed. The imput is the sequence "Which is larger, 8.9 or 8. 8.107" and the intended answer y "8. When asked to answer directly, earlier systems (c.g., GPT-4) might respond incorrectly (e.g., 7]. However, newer models trained with chain-of-thought supervision will typically first output a CoT z, represented as a sequence of tokens, enabling the model to arrive the correct answer. For example, the CoT might be, "Compare the numbers as decimals, with 8.9 written as 8.90 and where 8. 10 already has two decimal places. Then compare them digit by digit. The numbers agree the first digit. But larger than in the tenths place, so 8.9 is larger than 8. 10.". At test time, the CoT serves explanation of the answer. During training, however, the CoT plays the role of natural language description of the execution trace of an algorithm step-by-step procedure that to be learned. In this way. CoT used rich, additional supervised learning signal that goes beyond standard input-output ("end-to-end"") supervision.
of-inhof-thought, to ground
The focus of our theory to describe how this additional information impacts the statistical com- plexity of CoT-supervised learning. A key contribution of the paper is to identify quantity that we call the chain-offthouugh information, denoted by IS (e; H)) As we show, the CoT informa- tion characterizes the statistical complexity of CoT-supervised learning and captures the additional discrimination power granted to the learning algorithm by observing the chain-of-thought, In par- ticular, the COT information governs how the end-to-end error of the learned algorithm scales with the number of CoT training examples. Specifically, in the standard setting of PAC learning for bi-
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

nary classification, the sample complexity scales as m = O in the realizable setting, where d describes the size or complexity of the hypothesis space (e.g,, the VC dimension), and is the target classification error. In contrast, under CoT supervision, we show that the sample complexity scales according to m = =(d/ID. (e; H)). . A case where the chain-of-thougge
highly informa- tive will have P.,, (E: > E, which translates into favorable sample complexity. By establishing information-theorett lower bounds, it is shown that the CoT information thus provides a fundamen- tal measure of the value of this type of non-classical supervision. Because the construction of CoT training sets can be a time-consuming and expensive process, the theoretical framework developed in this paper may ultimately be of practical relevance, contributing to a formal understanding and quantification of the value of chain-of-thought supervision.
The remainder of the paper is organized as follows. Section 2 introduces an abstract model of chain- of-thought supervised learning. together with formal definitions of the learning objective and the key notions of risk, which we will use in our investigation. In Section 3, we motivate and introduce the CoT information measure, establish its fundamental properties, and, as an initial pedagogical result, show that it can be used to capture the improved sample complexity of CoT-supervised learning in the setting of finite-catt cardinalldy hypothesis classes. Section 4 extends this analysis to infinite hypoth- well to the agnostic setting where the data are not assumed to be generated by
esis classes, member of the class. In Section 5, two types of information tthooretic lower bounds are established that, together with the upper bounds, lends further support to considering the CoT information fundamental characterization of the value of thain-of- supervision. Section concludes with summary of further extensions that are presented in the appendix, discussion of related work, and directions for future research that are suggested by the results of this paper.
2 Preliminaries: A Model of Chain-of-Thought Supervised Learning
The standard statistical learning problem formulated as the problem of selecting a distinguished member of a function class F X' + y, mapping from an input space X' to an output space y The learner observes a dataset of input-output examples {(z,, 3:) he)] and seeks to identify the ground truth function f. E F (in the realizable setting) or compete with its closest approximation in F (in the agnostic setting). A learning algorithm in the standard ("end-to-end") setting is a mapping A: (X' x ))* )xx from input-output datasets to predictors.
When the target function class F is highly complex-sus reasoning
functions representing multi-step learningg from input-output examples alone can be statistically intractable. To overcome this difficulty, natural approach is provide the learner with increased supervision through the step-by-step execution of the target function on the input. To formulate this, we assume that each example observed by the learner includes not only the input x and output y, but also an auxiliary observation 2 that represents information about the function's 's execution on I.
A chain-of-thought (CoT) hypothesis class H is family of functions h h: X - y' Z. For each E H. an input I
yields l((z) = (u, =). where y E y is the output and z E is the corresponding COT. We denote the components of h returning only the output as its end-to-end restriction, 1 X' + V, and the component returning only the CoT as its CoT restriction, CCT X' + Z. In the and seeks to learn the underlying end-to-end function. A chain-of of-thought learning algorithm is a mapping A: (X x y x Z)* + yxx from CoT datasets to predictors.
learning setting, the learner observes dataset {(x,, Vi, 2,) [e[mm]
A key example captured by this framework is autoregressive sequence models, generating the CoT sequentially as 2 f Tn, 21, .... -1) until a final output y = f In, 21. 21. Zt(x)) is generated. In this case, the spaces X. Z would correspond to spaces of variable-length sequences over some vocabulary. Sequence models like transformers [8] are an important way to implement such hypothesis classes in a way that allows for CoT supervision. However, the details of any such implementation are not important for our theoretical treatment.
Types of risk. It will be crucial to distinguish between two notions of risk: End-to-end risk and the chain-of-though risk. Let D be a distribution over X. For a reference hypothesis h, E H and a predictor h E (> x 2)xx we define these risks as follows:
Rez0 (h)
PP BND
22 (x) 1 (x)
RCOT(h) IP ZND
[b(x)) + he (x))
2

---

Table 1: A comparison of analysis techniques for studying learning with chain-of ohain-hf-thought.
Method
Hypothesis class
Sample complexity (realizable)
E2E supervision
Finite H.
logl log/7//e
General H
VC(C22
bounding CoT risk
Finite H
log/H//e
General H
VC(C (H))/E
using CoT Information
Finite H.
log HII/II (e; H)
General 7
VC(C VC(C)0((H))/220 (e;
That is, RD (h) the probability that the predictor's end-to-end output is incorrect, whereas (h) is the probability that either the output (=))()) or the CoT CCoT(2) (z) disagrees with h.- A key characteristic of the chain-of-thougle supervised learning setting is that the training objective the COT loss, whereas the testing evaluation metric is the end-to-end risk. This asymmetry has important information-theorett implications, which are a main focus of this work.
2.1 Interlude: The problem of linking the end-to-end and chain-of-thought risks
Before introducing the CoT information measure and our main theoretical result, we first motivate key aspect of the analysis, which is specific to the CoT setting. In CoT learning, the learner observes training examples S = {Ir; V/s he(ml and seeks identify the input-outpui relationship using information from both the output y/s and CoT labels 24. That is, although the CoT error is used as a signal during training, only errors the final output y are penalized at test time. Consequently, to derive sharp statistical rates, it is necessary to link the two risk functions precisely.
To explain, recall that standard statistical learning theory characterizes the statistical complexity of learning from input-output examples without chain-of-thought supervision. For example, focusing on the realizable case for clarity, standard results in PAC learning [c.g.. 9] show that the sample complexity to obtain end-to-end error scales as d/s, where d is complexity measure such log- cardinality or the VC dimension of the end-to-end loss class _ Intuitively, the e-dependence can be understood in terms of the amount of information per sample, (1/E)) samples are required to distinguish between two hypotheses whose outputs disagree on a subset of measure E in the input space. Matching informatioonthhorettie lower bounds validate that these are the optimal learning rates for the standard E2E-superriieed setting.
In the CoT-supervised setting, the learning algorithm potentially has access to more information by observing the CoT, and thus faster rates of convergence are expected, The theoretical challenge lies in capturing this added information as improved rates in the analysis. Standard learning theory results cannot be directly applied to the CoT setting due to the mismatch between the training objec- tive and the evaluation metric. One approach to address this challenge, which is taken by Joshi et al. [10], is to side-step this asymmetry by noting that the end-to-end error is always upper bounded by the CoT error, with Re (h) I RS. (h), and to instead establish a guarantee on the CoT risk, allowing the use of standard results in learning theory. In particular, one can define the CoT loss class for the hypothesis class H. as a function class over X' x y x Z according to
(CoT(H) (CCoT
- (M(x) + (v. =)} h E
Then, appealing to standard results in PAC learning [e.g.. Vapnik's "General Learning" frame- work 9I, one can learn H. to obtain a CoT risk of & with a sample complexity m(z) = O(VC(CCoT (H))/e), which in turn guarantees that the end-to-end risk is also bounded by E.
This method of analysis leads to sample complexity with the same 1/s rate that we see in the end- to-end supervision setting, despite the increased amount of information per sample. In particular, this does not imply improved sample complexity over standard end-to-end supervision in the case of mnite-cardinality classes fc.f. Table 1). In the general case, improved sample complexity hinges on whether or not the inequality VC(CCOT (H)) < VC(L=²*((I) holds, which is priori unclear, even if is possible to construct artificial classes for which this holds [10]. This suboptimality stems from the fact that this approach does not distinguish between the two types of risk and does not explicitly measure the amount of information encoded the of-hhugt-. As a consequence, this approach cannot achieve matching information -hoomattoontthooetie lower bounds. Moreover, it is unclear
3

---

whether it is meaningful to apply this type of analysis to the agnostic setting, where the distribution over imput-outptt-Co examples is not realizable by the CoT hypothesis class.
3 Key Idea: The CoT Information Measure
We now describe a new approach that explicitly accounts for the additional information provided in the CoT supervision for distinguishing between hypotheses with different end-to-end behaviors.
Definition 1 (CoT information). For CoT hypothesis class H. ()' Z) and distribution D over N. we define the CoT information measures as follows:
IB 122) = - log P
(x) = hig hoo ( (12 = 11)x(())
anD
IOT D.h. D. (e; (EA,")
inf
I (h.,h)
where the infimum is over AB ;;; H. h.), the set of hypotheses that disagree with the end-to-end behavior (i.e., output) of h, with probability least E,
AD H,) = h H: P anD
(x22(()) + h (x=) > >E]
The relative COT information between two hypotheses I (h1 h2) quantifies how effectively the observed CoT behavior distinguishes the two hypotheses. In particular, the probability PP (x) h5"T(2) (z). h120())
(x) = he²m(x) E (0, 1) represents the proportion of inputs on which a pair of hy- potheses have matching behavior on both the CoT and the end-to-end output, rendering them indis- tinguishable from these observations. The relative CoT information between a pair of hypotheses is the negative logarithm of this probability; thus, I (h1 h22 takes values in [0, oc).
The CoT information of hypothesis class H. relative to the reference hypothesis h., a function of the error level c, denoted I (c; H). It is defined as the minimal relative CoT information between h, and every alternative hypothesis l E Ag (e; H, h.) which disagrees with h. 's end-to-end output on more than fraction of the inputs. A large ICOT (c; H) thus ensures high distinguishability (via CoT) between h, and any such "bad" alternative.
primary message of this work that the CoT information characterizes the e-dependence of sample complexity in Chain-of- Thainhof-Thought supervised learning by quantifying the informativeness of CoT supervision. The CoT information can be much larger than e, yielding rapid learning under CoT supervision. The intuition is that when two hypotheses differ in terms of their end-to-end behavior, even with small probability, they will typically differ in terms of their computational traces (i.e., CoT) with high probability. Consequently, CoT supervision allows these differing hypotheses to be distinguished far more rapidly than by observing input-output samples alone.
3.1 Properties of the CoT information
The following result outlines key properties of the CoT information measure. Among these, the TCa'l property D.,., (e; H)) 2 E is particularly important. As will be demonstrated, this implies that, in the realizable setting, CoT supervision is never detrimental, information-theorrtiaally The proof of these properties is given in Appendix A.
Lemma 1. Let H C (Y x z)x be CoT hypothesis class. Then the CoT information ICoT (c; H) satisfies the following properties:
1. ICoT (e; H) 2 e.
2. 7CTT DD,. (E; H) is monotonically increasing in E.
3. I (e; H) is monotonically decreasing in H. (under the subset relation).
Before proceeding with bounding sample complexity in terms of CoT information, we note how the measure behaves in extreme boundary conditions. First, let us consider an example where the CoT annotations are entirely independent of the end-to-end behavior. particular, consider a CoT hypothesis class with a product structure H = FCTT x Fele, where FCoT C 2 f C y In this case, we would expect no statistical advantage from observing the CoT-this is captured by the CoT information measure, which coincides with the "end-to-end information" in this case.

---

H Legend
h,
E2E-Cona
CoT-Cone H)
d/m
== (26..) ((d/m)
Increasing Sample
Figure 1: Illustration of the statistical advantage of CoT supervision in terms of the geometry of the CoT consistency rule with respect to end-to-ent error. CoT supervision enables the construction of tighter consistency set when the CoT is informative (i.e., D.h, (e; H) E), which leads to smaller end-to-end error and more sample-efficient learning.
At the other extreme, consider the case where the CoT from any single example reveals the entire target function. For example, let F c y and consider the CoT hypothesis class H (hy x -> (f)) E F}. In this case, ICOT (e; (c; = oc, which corresponds the fact that a single example is sufficient attain zero error. Finally, consider the problem of learning regular language with CoT supervision. Here, we take the output y to indicate whether or not the string æ is in the language, but we let z be the sequence of states visited in a DFA representing the language as processes æ; see Figure 2. Appendix B provides a more detailed discussion of these examples.
3.2 Improved sample complexity via CoT information
To illustrate the main ideas and intuitions underpinning this paper's results, we next prove sample complexity bound for CoT-supereeeed learning with finite hypothesis classes the realizable setting. While other proofs are deferred to the appendix for clarity and brevity, this particular result is proven here due its simplicity and pedagogical value.
The learning rule we consider is the learner returns any hypothesis in which consistent with the sample {(x) Vs 2 He in terms of both outputs and the chain-of- of-thought
consistency, CoT-Cons( (S; H): given a sample S,
Result (Learning with Chain-of-Thought Supervision). Let H C. (2) x 2)x x be a finite CoT hypothesis class. For any distribution over X' x y x realized by some h. E H. the CoT consistency learning rule has sample complexity of
m(e, 8) log H7 + log(1/0)
ICoT (e; H.
That is, for any m 2 mle, 8), with probability at least - 8 over S ~ D", any hypothesis h that is CoT consistent on will have end-to-end risk satisfying R (h) S
Proof. We aim to bound the probability of the "bad event"
(3h E H R > e, RCOT (h) = -}
over the draw of (zi,... Fm D. We highlight that the training loss is the empirical CoT risk, R.oT (h), whereas the test metric is the end-to-end risk Re2e(h))
Fix any h E H with end-to-ens error larger than E, R (h) = PewD[he2ep * c2c(h.) (i.e., h E A (e: H1, h.)). We bound the probability that h is CoT consistent on S, h
CoT-Cons H) {h E H RCoT 0}, as follows
[h CoT-Cons(S:: (S; = P (Vi, h CoT
(x;) 1 CoT
(ot)) (e0)),22(0x))) = - (22h))))zz)
SwDDm
S-DØm
= P
|1 CoT (2) = 11 CoT (CoT(z)) 1220 ) = n²²²()))* m
DDD
(a)
(expl (-ICoT ht))
(8)
exp
(mm- I (e; H))
5

---

10
0.8
CoT Detail Level
(5,
400
((R(A(S..))
0.8
Learning Rult
0.4
CrT-Cous
200
E26-
Kzror Type
0.0
10'
10
10 10
10a
10a
Sumple Size
Figure 2: Simulation results for learning regular languages, where the CoT is the sequence of states z visited by a DFA processing an input string æ. Right. CoT supervision yields a 102 to 10 gain in sample efficiency. Left. This empirical gain aligns with theoretical predictions from the CoT information measure, which for this setup yields a limiting ratio limg TCoT (e; H)/s x 600.
where step (a) is by the definition of the relative CoT information between a pair of hypotheses, and step (b) is by the definition of D... (e; H) and the fact that / E A8 h4).
(E: H. h.) with end-to-end error larger than e, the probability that is in the CoT consistency set is bounded by
Choosing m log PV (1//( implies that for each hypothesis h E A
ZCST (=:31
8
P [h CoT-Cons(S;:H)
S~DOT
[7|]
Applying a union bound over H. yields
3h E H ( c, RoT (h) = 0/ <
P
S~De@
complete the proof.
This result demonstrates that, for CoT learning, the e-dependence of the sample complex- Co'l (s;H)), contrasting with the typical rate of O(1/s). Intuitively, the ratio ity is O1//ZO,
ICOT (c;H)/e 2 1 quantifies the relative value of CoT training example compared with end- to-end training example. Figure 2 previews simulation results exploring CoT information in the context of learning a regular language, where the CoT is the sequence states from the underlying deterministic finite automaton (DFA). Its left panel depicts the ratio I (e; H))e function of
The plot can be interpreted as follows: For this hypothesis class Ht and distribution 'D (uniform), each CoT example roughly 600 times more valuable than a single end-to-end example. The right panel presents empirical learning curves for the CoT-Cons and E2E-Cons rules, illustrating the sta- tistical advantage CoT supervisionan advantage theoretically captured by the CoT information measure. Further simulation results are presented in Appendix C.
4
Guarantees for CoT-Supervised Learning: Upper Bounds
This section extends our exploration of statistical upper bounds to infinite hypothesis classes and the agnostic learning setting, thereby further elucidating the statistical advantage of CoT supervision.
4.1 The realizable setting: Extension to infinite classes
Result 1 established sample complexity bound determined by two key factors: the term 1/IpoT, (e: H), which captures the information per CoT-supervised sample, and the log-cardinality of the class, log (71, which reflects its size or dimension. We now extend this result to infinite classes, replacing the log-cardinality term with the VC dimension of the CoT loss class. As before, the upper bound is achieved by the CoT consistency learning rule.
Result (Learning infinite classes under CoT supervision). Let H C Z)* be a CoT hypothesis class. For any distribution D over Xxy> Z realized by some h, E H. the CoT consistency learning rule has sample complexity of
( TOOT D.K. (E: H,hh) + ( (VCCCCOT(HH)) log
(GTSOT
D.h. (E: +1) +1)+ +1og(116)))
m( =
That is, for any m. 2 ma(e, 8), with probability at least COT consistent on S will have end-to-end risk satisfying R: (h) S
- over S m any hypothesis that

---

The proof is provided in Appendix D.I. The result follows from a lemma that relates the CoT risk of any proper CoT learning rule (i.e., one that returns predictor the hypothesis class) to its performance with respect to the end-to-end error.
4.2
The agnostic setting
The previous results assume that the data distribution D over X' X ) x 2 is realizable by the CoT hypothesis class H. Such an assumption can be stringent, particularly in the presence of noise. This section, therefore, addresses the agnostic setting, where no restriction is made on the distribution; the goal, instead, is to compete with the best hypothesis in the class H. in terms of end-to-en ro-end risk.
In the agnostic setting, a natural learning rule is CoT empirical risk minimization, which selects a hypothesis that minimizes the empirical CoT risk: CoT-ERM H) = arg min Rgg (h).
Recall that CoT supervision never hurts in the realizable setting since ID. (e;H) 2 & for any hypothesis class. The picture is more complicated in the agnostic setting. In particular, CoT super- vision can be harmful or distracting, and discarding the CoT annotation and learning from only the input-output examples can be preferable, as the following example shows. The issue arises when the CoT hypothesis class H is not aligned with the data distribution, especially when H can fit the end-to-end behavior but not the CoT behavior.
Example. Consider a CoT hypothesis class H : x V Z and suppose D is a distribution over X' x y x for which the output component is realizable by H but the CoT component is 0 while
not realizable. In particular, it is casy to construct examples for which inf (2g0(() infAcH ( = 1. Clearly, in such cases, the CoT-ERM learning rule provides no guaranteess whatsoever since COT-ERM(S., S; H) H for any S supported by D. In contrast, E2E-ERM enjoys the standard PAC learning guarantees, with sample complexity O (1/2
(((()((())))
Thus, COT supervised learning the agnostic setting requires a different notion of CoT information, which captures how well-aligned the data distribution is to the hypothesis class, and whether fitting the CoT aligns with fitting the end-to-end behavior. This uses an excess risk variant of the CoT information, detined in the following result, which extends our results to the agnostic setting.
Result 3 (Agnostic learning under CoT supervision). Let H. ( z) be CoT hypothesis class. For any distribution D over X x y x Z, the CoT-ERM learning rule has a sample complexity of
m(e, 8) = ( VCCCCCT (H)) + 1og(1/8)
(E:
where IgoT (E; the agnostic CoT information, defined via excess risks as
ISO (e: == inf {ESOT (h) H. E (h) 2 }
where ( := ( inf (R) and (h) (h) -in R (h) are the excess
CoT and end-to-end risks, respectively. That is, for any m(e, 8). with probability at least - 6 over the draw of S D the excess end-to-end risk is bounded as R8O (h) S infa, (h)(()) + E, where h E CoT- CoT-ERM(S: H).
The proof is presented in Appendix D.2. Note that, unlike in the realizable case, we do not nec- essarily have the lower bound I (e; H) 2 e. For instance, in the motivating example above, ISo (c; H) = 0. However, CoT supervision yields an advantage when the excess CoT risk domi- nates the excess end-to-end risk (i.e., RCOT (h) RCoT Re2e (
5 Information Theoretic Lower Bounds for CoT Supervised Learning
This section establishes cnpemaation-thooeeite lower bounds on sample complexity, further validat- ing the CoT information Ip.,, (e; H) as fundamental measure of statistical complexity for learning with CoT supervision. In general, the statistical complexity of a learning problem depends on sev- eral parameters, including the size or complexity of the hypothesis class (e.g., VC(H) in binary classification) and the emorr parameter (e.g., 1/e or 1/e² for the realizable and agnostic settings, respectively). Different types of lower bounds scale accordingly with one or both of these factors.
Our main focus in this work is the dependence of the sample complexity on the error parameter,
7

---

which corresponds to the amount of information encoded in the CoT supervision for discriminating between hypotheses with different end-to-end behavior.
We begin with a lower bound demonstrating that CoT information DD.,, (e; H) characterizes the dependence of sample complexity. The essence of the result is to lower bound the minimum number of samples required to reliably distinguish a pair of hypotheses with given end-to-end disagreement, reducing the learning problem to a binary hypothesis testing problem [11], and relating the total variation distance between distributions over X x y Z induced by pair of hypotheses to the relative CoT information between them.
Result 4 (Lower bound via COT information). Let H. C ()) x 2)x be CoT hypothesis class and let D be distribution on X. Let I1,.... 2m be an i.i.d sample from D. For any h, E H. and E > 0, if the sample size satisfies
m log(1/6)
D.h. (e:H)
then with probability at least ó, there exists h E H with end-to-end error at least E which is indistin- guishable from h, on the sample. Moreover, the expected error of any algorithm A satisfies
1
sup K.EH pm
R.D. (A(S)) 2
IOOT sup e- -...m....... (e)))..
b,EN 620
This result validates the COT information characterizing the e-dependence of the rate. However, a weakness of two-point methods is that they do not scale with the size of the hypothesis space. The following result addresses this by reducing the learning problem hypotheses, using a packing of the hypothesis space with respect to the end-to-end error. We then use Fano's inequality to lower bound the probability of error in terms of mutual information, and relate this mutual information to the CoT information. To apply Fano's method in this way, we extend the framework allow the observed
that of testing multiple
be stochastic function of the hypothesis COT.
Result 5 (Lower bound via Fano's method), Let H C (Y 2) be a CoT hypothesis class and let 'D be distribution over X. Suppose that rı,..., Fm ~ D. Let Q E P(Y x 2 x 2) be a noisy channel from h(x)) = (y.z) to observations y; Z. Let Cq = max DxL (Q a) b)) be the capacity factor of the channel. The learner observes the noisy sample S = {(x; Th. 2, J= }m Define
the pseudo-metric d (h1, h2) = P. (x)²=())) & (x)], and let (s; H, d' be the E-packing number of H with respect this pseudo-metric. Then, for any algorithm A, we have that
log M (PL, de
m S
2.
CQ
sup, E
[ [SOI(M, h2)] log
h1.22~
implies large error for some h, E H. with high probability, i.e.,
sup H. 8mp
P
Re2e
(A(S)) 2 2 1/2.
Here, Cq is a bound on the capacity of the channel that adds noise to the chain-of-thought. This lower bound relates the probability of large eтror to the CoT information measure, like the previous result, but also scales with the size of the hypothesis space, as measured by its packing number. Ad- ditionally, the result also models noise in the learning process by observing the CoT through a noisy channel. The proofs of both results, along with further discussion, are presented in Appendix E.
6 Discussion and Related Work
6.1 Further explorations
We describe additional results not included in the main paper, and defer to the appendix for details.
Learning with mixed CoT and E2E supervision. In practice, obtaining CoT-annotated examples can costly and labor-intensive process, limiting their quantity, whereas onput-output examples without CoT annotation can be relatively cheap and plentiful. This motivates a need for learning algorithms that can make use of both types of examples. Appendix F.I studies learning from datasets with mix of E2E and CoT supervision.
8

---

CoT learning with inductive priors. Encoding prior knowledge about solution structure is critical for learning complex functions, such as those representing multi-step reasoning processes, particularly from limited data. Appendix F.2 explores chain-of-thought learning with inductive priors.
Transfer learning and -ntt-f--iittribution generalization. Chain-of-thought supervision has signif- icant implications for out-of-distribution generalization, as it guides the learning algorithm toward solutions that exhibit the correct step-by-step reasoning, potentially enabling robust generalization to novel input instances. In Appendix F.,, we define a variant of the CoT Information measure, I DDoaee (e; H), that captures transfer learning under CoT supervision. We also present a result on learning under CoT supervision with distribution shift, supported by experimental simulations.
6.2 Related work
Early usage of the term "chain-of ofhain-of-thought" referred to empirical prompting techniques that condi- tioned large language models to generate a series of intermediate reasoning steps before returning the final answer [1-3, 12]. Such prompting often employs in-context learning, where CoT examples are provided within the model's context before it processes the input [3]. Today, the term chain- of-thought takes a broader meaning, as it now comprises a core component of the training of large language models [4-6].
Several works have sought to theoretically understand the advantages of the Mlain-off-thougee paradigm by analyzing the representational capacity of neural sequence models with and without chain-of-thouge [13-16]. For example, Pérez et al. [13] show that Transformers ing machines by generating CoT tokens, and Merrill and Sabharwal [14] extend this analysis by providing more refined characterization of function classes in terms of the number of CoT steps.
simulate Tur-
While these studies demonstrate the existence of neural network models capable of computing a given function via a specific chain-of-thought they do not address the statistical question of whether such models can be efficiently learned from data. Our work focuses on these statistical learning aspects, direction also pursued by a few recent studies. For example, Malach [17] studies the problem of learning autoregressive next-token prediction on CoT datasets. The core idea of this work is to express CoT function as a composition of 7 (a fixed number) different sequence-domain functions, H = H41 X ... x Hr, where each H4 X x E!-1 + Σ maps the input and CoT generated far (z, 21, ..... 21-1) to the next CoT symbol 22, with the T- CoT symbol serving as the final output. With this formulation, Malach [17] proposes learning each He independently (with independent parameters), enabling the direct application of standard PAC results. While this approach simplifies the analysis, its assumption of independently learned functions at each iteration is notable limitation, which does not accurately reflect real-world settings.
Building on this work, Joshi et al. [10] considers a time-invariant composition of sequence-domain functions, where the function at each iteration remains the same. Their analysis relies on bound- ing the CoT error using standard PAC learning tools based on the VC dimension of the CoT loss class, noting that the CoT error provides an upper bound on the end-to-end error (cf. Section 2.1 and the second row of Table 1). Moreover, Joshi et al. [10] construct a synthetic autoregressive class exhibiting gap between the VC dimension of the end-to-end loss class and CoT loss class, implying a statistical advantage for CoT supervision. While our results also involve the CoT loss class, thus inheriting the advantages of such class complexity differences, the focus of our analysis is on the content of information per CoT-supervised sample. This is represented in the dependence of the sample complexity on the target error e, captured by the CoT' information measure. This provides a more complete description of the statistical advantage of CoT supervision in statistical CoT information rather
learning. We contend that this information-theorest than solely on loss class complexity, identifies a more fundamental source of statistical advantage in CoT-supervised learning. This view is supported by our lower bound results and the close agreement between our theory and simulations.
analysis, centered
We close the discussion of related work by noting that learning with chain-of-though supervision can be framed as a transfer learning problem [e.g., 18-20J, where the "source task" involves learning the mapping + (z, y) that jointly predicts the output y and the auxiliary chain-of- tf-hhught signal 2, while the "target task" is the end-to-end prediction task x + y. When the CoT information is large (i.e., I (E) e), the source distribution allows learning the target task more rapidly than the target distribution itself. This is sometimes referred to as super transfer [21].

---

6.3 Conclusion and future work
This work provides theoretical analysis learning with chain-of-thought (CoT) supervision, in- troducing the CoT information measure to characterize its statistical advantages via both upper and lower bounds. This opens several promising directions for future theoretical study of CoT learning.
The upper bounds obtained in this work are based on analyzing natural but relatively simple learning rules: CoT-consistency in the realizable setting, and CoT-ERM in the agnostic setting. Investigating the optimality of these algorithms and exploring the design of optimal learning strategies remain key open questions. This may be especially relevant in the agnostic setting, where the alignment between the data distribution and the CoT hypothesis class is critical. For instance, future work could explore adaptive learning rules that balance the optimization of the CoT error and end-to-end error to avoid over-optimizing the CoT when the hypothesis class is poorly aligned with the data. While we use the VC dimension of CoT loss class as the measure of complexity or size of the hypothesis class, will also be important to consider other measures of model complexity, including covering numbers, local Radamacher complexities, and one- iee-incussion graphs [22-27].
Furthermore, while our current lower bound results address the realizable setting, establishing cor- responding lower bounds for the agnostic setting remains an important open problem. Additionally, future research could investigate the formulation of different structural conditions, such as low-noise assumptions [28, 29] in the CoT setting, to achieve faster learning rates. Developing more sophis- ticated probabilistic analysis, beyond the standard formulation of agnostic learning, holds promise for more faithfully capturing the complexities of training language models with chain-of-thought reasoning traces, which are often inherently probabilistic.
Acknowledgements
We thank Dana Angluin and Peter Bartlett for helpful comments this work. This research was supported by the funds provided by the National Science Foundation and by DoD OUSD (R&E) under Cooperative Agreement PHY-2229929 (The NSF Al Institute for Artificial and Natural Intel- ligence).
References
[1] Maxwell Nye et al. "Show Your Work: Scratchpads for Intermediate Computation with Lan- guage Models". 2021. arXiv: 2112. 00114 [cs.LG] (cited on pages 1, 9).
[2] Karl Cobbe et al. "Training Verifiers to Solve Math Word Problems". 2021. arXiv: 2110. 14168 [cs. LG] (cited on pages 9).
[3] Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoe Le, Denny Zhou, et al. Sfhain-of-thougeee prompting elicits reasoning in large language models"" In: Advances in neural information processing systems (2022) (cited on pages 1, 9).
[4] Namgyu Ho, Laura Schmid, and Se- Young Yun. "Large Language Models Are Reasoning Teachers". In: Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume I: Long Pupers). 2023 (cited on pages 1)..
[5] Hyung Won Chung et al. "Scaling Instruction-Finetuned Language Models". 2022, arXiv: 2210. 11416 [cs [C] (cited on pages 1, 9).
[6] Long Ouyang et al. "Training language models to follow instructions with human feedback". 2022. arXiv: 2203. 02155 [cs.CL] (cited on pages 1, 9).
[7] Huy A Nguyen, Hayden Stec, Xinying Hou, Sarah Di, and Bruce M McLaren. "Evaluating ChatGPTs decimal skills and feedback generation in a digital learning game". In: European conference on technology enhanced learning. Springer. 2023 (cited on page 1).
[8] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, ukasz Kaiser, and Illia Polosukhin. "Attention all you need". In: Advances in neural infor- mation processing systems (2017) (cited on page 2).
[9] V. Vapnik. "Estimation of Dependencies Based on Empirical Data". Springer-Vetee Verlag, New York, 1982 (cited on page 3).
10

---

[10] Nirmit Joshi, Gal Vardi, Adam Block, Surbhi Goel, Zhiyuan Li, Theodor Misiakiewicz, and Nathan Srebro. "A Theory Learning with Autoregressive Chain of Thought". 2025. arXiv: 2503. 07932 [stat.ME (cited on pages 3, 9, 17).
[11] L. LeCam. "Convergence of Estimates Under Dimensionality Restrictions". In: The Annals of Statistics (Jan. 1, 1973) (cited on pages 8, 23).
[12] Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. "Large language models are zero-shot reasoners", In: Advances in neural information pro- cessing systems (2022) (cited on page 9).
[13] Jorge Pérez, Pablo Barceló, and Javier Marinkovie. "Attention is turing-complete.. In: Jour- nal of Machine Learning Research (2021) (cited on page 9).
[14] William Merrill and Ashish Sabharwal. "The expresssive power of transformers with chain of thought". In: arXiv preprint arXiv:2310.07923 (2023) (cited on page 9).
[15] Guhao Feng, Bohang Zhang. Yuntian Gu. Haotian Ye. Di He, and Liwei Wang. "Towards Revealing the Mystery behind Chain of Thought: Theoretical Perspective". 2023. arXiv: 2305. 15408 [cs. LG] (cited on page 9).
[16] Zhiyuan Li, Hong Liu, Denny Zhou, and Tengyu Ma. "Chain of Thought Empowers Trans- formers to Solve Inherently Serial Problems". 2024. arXiv: 2402. 12875 [cs. LG] (cited on page 9).
[17] Eran Malach. "Auto-Ree Regressive Next- Token Predictors are Universal Learners". 2024. arXiv: 2309. 06979 [cs LG] (cited on page 9).
[18] levgen Redko, Emilie Morvant, Amaury Habrard, Mare Sebban, and Younès Bennani. "Ad- vances in Domain Adaptation Theory". Elsevier, Aug. 23, 2019. 210 pp. Google Books: aM8mDwAAQBAJ (cited on page 9).
[19] Shai Ben-David, John Blitzer, Koby Crammer, Alex Kulesza, Fernando Pereira, and Jennifer Wortman Vaughan. "A theory of learning from different domains". In: Machine learning (2010) (cited on page 9).
[20] Yishay Mansour, Mehryar Mohri, and Afshin Rostamizadeh. "Domain Adaptation: Learning Bounds and Algorithms". In: Conference on Learning Theory (2009) (cited on page 9).
[21] Steve Hanneke and Samory Kpotufe. "On the Value of Target Data in Transfer Learning". In: Advances in Neural Information Processing Systems. Curran Associates, Inc., 2019 (cited on page 9).
[22] Peter Bartlett, Olivier Bousquet, and Shahar Mendelson. "Localized rademacher complexi- ties". In: International Conference on Computational Learning Theory. Springer. 2002 (cited on page 10).
[23] Peter L Bartlett, Olivier Bousquet, and Shahar Mendelson. "Local rademacher complexities". In: Annals of Statistics (2005) (cited on page 10).
[24] Olivier Bousquet, Vladimir Koltchinskii, and Dmitry Panchenko. "Some Local Mcasures of Complexity of Convex Hulls and Generalization Bounds". May 18, 2004. arXiv: math/ 0405340. Pre-published (cited on page 10).
[25] Gabor Lugosi and Marten Wegkamp. "Complexity Regularization via Localized Random Penalties". In: The Annals of Statistics (Aug. 1, 2004). arXiv: math / 0410091 (cited on page 10).
[26] S. Mendelson. "Improving the Sample Complexity Using Global Data". In: IEEE Transac- tions on Information Theory (July 2002) (cited on page 10).
[27] David Haussler, Nick Littlestone, and Manfred K. Warmuth. "Predicting [0.nt-Functions on Randomly Drawn Points", In: Inf. Comput. (1994) (cited on page 10).
[28] Enno Mammen and Alexandre B Tsybakov. "Smooth discrimination analysis". In: The An- nals Statistics (1999) (cited on page 10).

---

[29] Pascal Massart and Elodie Nédélec. "Risk Bounds for Statistical Learning". In: The Annals of Statistics (Oct. 2006) (cited on page 10).
[30] E Mark Gold. "Complexity of Automaton Identification from given Data". In: Information and Control (June 1978) (cited on page 15).
[31]
Dana Angluin. "A Note on the Number of Queries Needed to Identify Regular Languages". In: Information and Control (Oct. 1981) (cited on page 15).
[32] Dana Angluin. "Learning Regular Sets from Queries and Counterexamples" In: Information and Computation (Nov. 1987) (cited on page 15).
[33] Ronald L. Rivest and Robert E. Schapire. "Diversity-Bar -Based Inference of Finite Automata". In: 28th Annual Symposium on Foundations of Computer Science (Sfes 1987). 28th Annual Symposium on Foundations of Computer Science. Los Angeles, CA, USA: IEEE, Oct. 1987 (cited on page 15).
[34] R. L. Rivest and R. E. Schapire. "Inference of Finite Automata Using Homing Sequences", In: Proceedings of the Twenty-Fire Annual ACM Symposium on Theory of Computing STOC '89. The Twenty-First Annual ACM Symposium. Seattle, Washington, United States: ACM Press, 1989 (cited on page 15).
[35] Yoav Freund, Michael Kearns, Dana Ron, Ronitt Rubinfeld, Robert E. Schapire, and Linda Sellie. "Efficient Learning of Typical Finite Automata from Random Walks". In: Proceed- ings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing STOC '93. The Twenty-Fifth Annual ACM Symposium. San Diego, California, United States: ACM Press, 1993 (cited on page 15).
[36] Imre Simon. "Piecewise testable events". In: Automata Theory and Formal Languages: 2nd GI Conference Kaiserslautern, May 20-23, 1975. Springer. 1975 (cited on page 15).
[37] Dana Angluin, James Aspnes, Sarah Eisenstat, and Aryeh Kontorovich. "On the learnability of shuffle ideals". In: The Journal of Machine Learning Research (2013) (cited on page 15).
[38] John E Hoperoft, Rajeev Motwani, and Jeffrey D Ullman. "Introduction to automata theory, languages, and computation" In: Acm Sigact News (2001) (cited on page 16).
[39] Bin Yu. "Assouad, Fano, and Le Cam". In: Festschrift for Lucien Le Cam. Ed. by David Pollard, Erik Torgersen, and Grace L. Yang. New York, NY: Springer New York, 1997 (cited on pages 23,25) 25).
[40] Yury Polyanskiy and Yihong Wu. "Information Theory: From Coding to Learning". Cam- bridge. United Kingdom New York, NY: Cambridge University Press, 2025 (cited on page 23).
[41] T. M. Cover and Joy A. Thomas. "Elements of Information Theory". 2nd ed. Hoboken, N.J: 2006. 748 pp. (cited on page 25).
[42] Ray J Solomonoff. "A formal theory of inductive inference. Part r". In: Information and control (1964) (cited on page 30).
[43] Andrei N Kolmogorov. "Three approaches to the quantitative definition of information". In: Problems of information transmission (1965) (cited on page 30).
12

---

A Proofs of Properties of the CoT Information (Section 3.1)
Lemma (Restatement: Properties of the CoT-information). Let H C (yxZ)* be a CoT hypothesis class.
1. The CoT information is always larger than the "end-to-end information": For any h1, h2 E H. I (h1, h2) 2 P2~D(h/ (x))))(((()))) # h=²²(x)). Moreover,
D.h, (e;H) H) 2 e, Ve E [o, vh, E H.
2. D.h. (+; is monotonically increasing in E:
For any H, h. E H. and e S Eg. I (E1; H) S I (e2:
3. D.h. (e; .) is monotonically decreasing in the hypothesis class: For any hypothesis classes H. C Ht' and he E H. D.h, (e; H) 2 ID.N, (s;
Proof.
Property 1. To prove the first claim, take any h1, h2 E H. and observe that
I (hi, h22 == - llog 0nD [hy MCCorg (ar) = 12 Colll (x)), (xx) = 11220 (xr]
2 - log P
[1120 h)²²0(x))
anD
=llog (1-
P (1120())) 7 hg22n hz)(
anD
> P (M)2(())) # 1/2 (x)
where the final inequality is by the identity log(1 - x) 2 x. We now show the second claim,
IDD.h. (e; H) = min heAg hEAg
I
ICOT (11,) hi)
min
P [he20
& h (x)]
The final inequality follows because nition.
IP anD
(2=20(x) + h:200 (x)] 2 E, wh E (E; h.). by defi-
Property This follows from the fact that (s; is decreasing in For e S E2, have 2020 (51; H. h.) 2 22 (E2) H. h. and hence
( H. h..) == (h : (()=20(ar) + [x))) > }}
IooT. H);; ;= min
TOT ICoT(h, (h, S
min
I (h, h.) = IOOT (62; H).
hEa he HL..)
Property 3. This property similarly follows from the fact that A (2: H, h.) is increasing in H: A (E; h,) C ( (e; h.) for H. S H'. Thus,
I (e: (e: = min
IOOT ICOT(h, (h, 2 min (EAg"(EH
I IOOT (h, h.) =: IO. (e;
hEa (ER.)))) (e.
B Simple Examples of CoT Hypothesis classes and their CoT Information
In this section, we provide a more detailed discussion on the illustrative examples presented in Sec- tion 2. The first two examples represent the two extremes on the informativeness of CoT supervision and serve as sanity checks to confirm that the CoT information captures the expected statistical com- plexity in each case. The next example considers hypothesis class where the CoT supervision includes T independent samples of the input-output function, and shows that the CoT information scales linearly with 7 as expected. Finally, we consider CoT hypothesis classes based on models of computation such as fnite-state machines, where the CoT is taken to be the state trajectory of the computational process.
13

---

Example (Uninformative CoT yields small CoT information). In some cases, the CoT annota- tions may be entirely "independent" from the end-to-end behavior, and hence uninformative for the purposes of learning with respect to the end-to-end error. We will see that the CoT information D.h.. (e; H) captures this. We will model the "independence" between the CoT and the end-to-end behavior via a hypothesis class with a product structure. Let F C y be function class from inputs X' to outputs y and let FCoT C z be function class from inputs X' to the CoT space Z. We consider a CoT hypothesis class H. = FCoT x F where
H ( : x + (o(2), g E If EFF
Let h. = (g.. f.) H. = FCOT F Let f E F be the end-to-end hypothesis with smallest disagreement with f. among hypothesis with end-to-end error least s:
f
arg min JEF
P (f) f(x)] LEWD
IP (f) + f(x)] [())
Let e+ == min(P(f..x)) + f(x) ~ ~ (z) f(x) > E}. By the product-structure definition of H. there exists hypothesis h (g+, f) Ax: H) such that ((h + h(=)]
(x) A (x)) = st. and hence I (e; H. h.) - log(1 st). Thus, there is no statistical advantage in observing the CoT annotations.
Example (Fully Informative CoT yields infinite CoT information). Recall the definition of the CoT information as
I (E: H) == inf {- log [h(2) = hx))) h (e; H.h.)
This can be infinite when vh E (E; H. h.), P2 [h(x)) hx)]] 0. This occurs in the extreme case where single CoT annotation uniquely identifies the end-to-end behavior of the hypothesis (i.e., on every input in the support of 'D, each hypothesis has a unique CoT)). To illustrate this, let Fele y²² be a class of functions from the input space X' to the output space y. Consider the CoT hypothesis class H (hy + (x)) E Fr2e). In this extreme example, a single sample is enough to learn the function perfectly. This is captured by the CoT information since 4h, * ha E H. we have P((n h2(x)) = 0 and hence I (e; H) co.
Example (CoT Information captures i.id. examples in CoT). In this example, we consider a setting where the
represents i.i.d observations from the end-to-end function, toy model that allows us to vary the informativeness of the CoT supervision for fixed end-to-end function class. We will confirm that the CoT information implies the sample complexity rates that we would expect. Consider the CoT hypothesis class H(T) where the CoT encodes T independent observations, defined as follows:
T = ATT (T) (II....,TT) (r)+ + (f(z)).... f(IT))
fE
(T)
Here, F is function class from & to D. and X' = XT, 2 = yT DT.y= D. Let D = D for some
distribution D over X. Fix he = hy. and let h = h E Ag H. h4). We have
ICoT hh), = log IP [h. (x) = h(x)] = log
ME [T] fx(x))== f(x:)
IND
D
2 -ogo - -) = T (- loggl1 - -)) 2 T
This in turn implies that I (e; H) 2 T. That is. one CoT sample is worth T' end-to-end samples, and the CoT sample complexity is smaller by factor of T. This is what we would expect for this example since CoT example consists of T' independent samples.
Example (Learning Regular Languages with State Trajectory CoT). Let H be the class of Finite- State Machines with common state space S and operating over an alphabet Σ. That is, H. (ha 5 T) where T the set of transition functions by the learner is the sequence of states visited by the DFA during its execution: for an input = (I1, (f,,..., E Σ", the CoT of h& CoT can be interpreted as providing the learner with an input-dependent partial observation of the
S The Chain-of-Thought observed
(z1, 2,,), where ž++1 = 5(21, Observing the
14

---

DFA's underlying transition function. Once the learner has identified all components of the transition function (or all components that are necessary to specify the input-output behavior), the learning objective is achieved. We can use this interpretation to lower-bound the CoT information. Let A (m, h2) = ((s, .) E S x Σ 51 (s, x)) o 62(8, J be the set of state-symbol pairs on which h1 and he 's transition functions differ. Then, we have
1
P [ To (x) = Co'll (2), hx") = (x))
a>D
CoTT (x) + h ChoT((rr) (ar)
æ~D
E E [n] 2t + =
E~D [h, visits any (s, a) E A h.)] a~D
Suppose that h,'s transition graph is f-connected in the sense that for every state 8 E S which is reachable by some input supported by D, 36' I l,ag...., ar E such that 8p = where
8141 = 8t (St, at), 81 = Simit. Then, if e.g. D = Unif(E"), 2 e, the above calculation implies that for all o h.s
IP anD
[x) = h (x)) 11t0 h 2e (x)) S 1 |> -(+11)
Thus, the CoT information is lower bounded as
min I CC'T +30 D.K. (e:H) [Σ] ((41)
Note that this bound may be loose since it only counts single trajectory that can be used to distin- guish between the pair of hypotheses. But, its strength is that it lower bounds the CoT information at all error levels E, and hence upper bounds the sample complexity of achieving zero error. A rich literature exists on learning regular languages [e.g. 30-35].
Example (Learning Shuffle Ideals by Observing Computational Trace Finite State Machines). The class of shuffle idcals is simple subclass of regular languages that has been studied in the context of efficient PAC learning [36, 37J. For a string u E Σ", the shuffle ideal generated by u is the language E' u, un ... L',,'" D" consisting of all strings which contain u as subsequence. The class of shuffle ideals of strings of length n can be represented by finite state automata with 1 states. For string u E Σ", it's shuffle ideal is recognized by the finite state machine with the following transition function
(8, a) = 8 1, if a ===aa Us
otherwise.
The acceptance state is s n 1. This finite state machine has a state space with sequential structure, with each state "looking for" a particular symbol. When that symbol is observed, the state progresses to the next. A string is accepted if state n + 1 is reached, signifying that all symbols in the string u are observed in the correct order. Due to the structure of this hypothesis class, each state has exactly one symbol that causes it to progress. Thus, to learn the FSA perfectly, it is enough to learn which symbol each state accepts. In fact, due to the sequential structure of this class of finite- state machines, this information is revealed on single trajectory from positive example. Thus, the CoT information can be bounded in terms of the probability of observing a positive example. In particular, for h, * h E H. we have
P
[hCoT (x) # h COT
(x)]
2
P anD
[M (x) accept].
and hence min. I (e; (e; > P
2e (x) accept].
DND
Example 6 (Turing Machines). It is possible consider learning Turing Machines with CoT- supervision in a manner similar to Example 4. Recall that a Turing machine is specified by transition function 5 : S + S Σ {=1}, mapping the current state s and observed symbol a on the current position in the tape to the next state s'. the symbol to be written 7 and the direction to move the tape d. We may consider Turing machines with chain-of-thought- supervision, where the CoT is the trajectory of states, written symbols, and tape movements: = (11,77,44 di),..,, (Bu(a)) Te(e), du(x))) )) where ((x) the halting time of the Turing machine, and can depend on the input and the instance h,- Similar to the case of DFAs, observing the
15

---

CoT reveals an input-dependent partial specification of the underlying transition function. To lower bound the CoT information, one can consider analogous "connectivity" conditions condition to those discussed in Example 4. For example, one such condition is that for every E S, there exists an input prefix w E E such that the Turing machine h4 lands in state s when reading w and starting at Sinit-
C Simulations
This section presents numerical simulations empirically exploring the CoT information measure for simple CoT hypothesis classes and its ability to predict sample complexity gains from CoT- supervised learning.
C.1 Deterministic finite automata
deterministic finite automaton (DFA), type of finite state machine (FSM), is a foundational model of computation. A DFA defines function from the space of variable-length strings to binary classification: accept or reject. DFAs recognize exactly the class regular languages [38].
CoT learning is often used as a means of providing supervision on the intermediate computation of a reference algorithm to be learned. In the following experiments, we use DFAs as model of computation to study this type of supervision.
2
We consider a CoT hypothesis class H. C (y x 2)x based on deterministic finite automata (DFA). We take the input space to be X = Σ" (or Σ*) for some alphabet E. As with Example 4, the hypothesis class H is the set of all DFAs with state space S operating over the alphabet Σ. The output y = h )x22(()) (a:) is the acceptance or rejection of the string E X Σn and the ohtin-of- z = (Zi,..., kn) = h CoT (x) E S is the sequence states the DFA visits during its execution.
3
1
Recall that a DFA is specified by a transition function 8: SS E S that maps the current state and current symbol to the next step, an initial state Sinic E S. and an acceptance state Saccept E S. The final output of the DFA is 1(2,, Saccept
Figure 3: The transition graph of
h. This DFA is identified with the regular language that checks if the final symbol a one or a zero
In these simulations, we fix the size of the state space and vocabulary Σ, as well as choose an initial state and acceptance state, and generate H as the set of all automata operating on those spaces. We place uniform distribution over the input space D Unif(X)) = ) We then choose ht ~ Unif(H) randomly, plotted to the right, and numerically compute I (h., h) and I (e; H). Figure 4 depicts the simulation results for these DFA experiments.
Value of CoT example E2E example. Figures 4a and 4b depict the ratio between the CoT information I H)) and as a function of e. This ratio can be interpreted as the value of one CoT example compared to an end-to-end example, since the learning rate for E2E-supervision scales like log /1/e whereas the rate for CoT supervision scales like log / (e; H). We clip in this ratio the minimal non-zero end-to-end error =x m (h) Ro (h) # 0}, and denote this clipped value by e+_ This is because to achieve a target error smaller than this critical level, error is
E", we only need O(1/E*) samples, not (11/s) samples. In particular, achieving possible with (1/E") samples. The quantity lim ISA.. He)e* has the special interpretation of the ratio of the number of samples needed to achieve zero error under CoT supervision compared to E2E supervision.
Varying input length. In Figure 4a we vary the input sequence length in the input distribution D. That is, we take D, = Unif(E"), and we compute the CoT information as function of E for that distribution, varying n. We observe that the CoT information increasing relative to E as the input length n increases. An intuitive explanation for this is that longer inputs allow bigger portion of the DFA's state transition map to be explored in a single example. Figure 4c depicts lim;- ICOT (e; H)/et as function of the sequence length n. We see that this increases rapidly with n, suggesting that, for large n, the probability of CoT trajectory agreeing for pair of hypotheses with very different end-to-end behavior is vanishingly small. For 10, see that
16

---

this value is roughly 600. By our theory (e.g.. Result 1), this would suggest 600 improvement in sample complexity for learning with zero target error. (Indeed, this is supported by our numerical simulations on learning with CoT-Cons and E2E-Cons, as depicted in Figures 4e and 4f, which we will discuss further bit later.)
Varying CoT detail level. Now, we consider fixing the input length to n = 10 and instead varying the level of detail in the CoT annotations. We do this by varying the proportion of the state trajectory that is revealed to the learner, denoted by T E [ra]. For each T, we run a simulation where the CoT trajectory revealed the learner is the first T symbols of the state trajectory. As expected, the CoT information monotonically increases with T. In Figure 4b we plot the ratio of CoT information to E as a function of E, varying the level of detail T, and in Figure 4d we plot lim D... (e: Ht) While this is monotonically increasing in T, it hegins to plateau T increases, suggesting that there are diminishing returns when it comes to distinguishing hypotheses via their CoT trajectories- most of the information is revealed in the earlier portions of the COT
Empirical sample complexity of CoT-Cons and E2E-Cons. Next, we directly evaluate the sample complexity of CoT-supervised learning compared to E2E-supereised learning by running simula- tions using the CoT-Cons and E2E-Cons learning rules. We vary the sample size m. randomly draw dataset S.n. of size m, and apply each learning rule to return predictor A(Sm). then com- pute the generalization loss (A(Sm)) of the returned predictor. The CoT-Cons and E2E-Cons learning rules are implemented by constructing the respective consistency sets and returning a pre- dictor uniformly at random. We repeat this for 500 independent trials to estimate the distribution of RB (A(S,..) as a function of the sample size m for each learning rule. Figure 4e depicts the empirical sample complexity. It is computed by computing the empirical average of the loss for each sample size m, and plotting the first sample size at which each target error level æ is attained. Giving a complementary view, Figure 4f plots the empirical probability (over the random draw of the sample Sm) of returning a predictor with zero loss as a function of the sample size m. Across both figures, we see gain in sample efficiency from CoT supervision of the order of 10 103, which agrees with the theoretical predictions via the CoT information, lime- ICn'T (e; H 600.
C.2 Iterated linear thresholds
In practice, common way of implementing CoT supervision is to consider a sequence model class (e.g., transformers) and to train the model to generate the CoT as a sequence token-by-te baken-by-token, before returning the final output. In this section, we consider another CoT hypothesis class that simulates simple form of this autoregressive generation. In particular, that generates tokens as a linear function of a fixed-size window of the history.
consider sequence model class
Fix window size d, and let w E (- 0, 1)d be set of weights over this window. For binary E f0. 13/a/+1 as the function that returns a sequence with the symbol = appended to æ, where = is computed by applying a threshold to the w-weighted linear combination of the prior d symbols,
sequence x (I1, .n) E {0, 1}",, we define the function fw : x ++ (xx,
fw x + (0, E {0, 11.111 ==
Σ w. In-i 2 20
The CoT hypothesis class is defined by iterating fwi T times, taking the produced sequence as the COT,, and the final symbol as the output. That is, H (tr : w (, 1jd), where h. is defined as
h CoT x + (21, (T) he x + 2T
(x, (21...., = (Jw o .... Sw) (x)
times
This represents a simple type of autoregressive COT hypothesis class, similar to the one studied in Joshi et al. [10]. In this section, we carry out a series of numerical simulations to explore what the CoT information says about CoT-supervised learning for such a class. We take the window size to be d 8 and the number of iterations to be T' 16. The experimental results are depicted in Figure
In Figure 5c we plot the CoT information I (e; 70), which depicts the monotonicity in e shown in Lemma 1. We observe that lim D.h. (e; H.) s 0.32 E* ~ 0.05, and
17

---

600
600
124 3.,l6;
100
100
Lengtà
Col Detail
200
0
10
10
10
10
10"
10
10
10
(a) Ratio of CoT Information "clipped"
(b) Ratio of CoT Information to "clipped" varying level detail COT.
varying input length.
lim 23. (#; 24)22. (s; (1:
600
lim Zee (s:H k')/
400
200
10
Length
CoT Detail Level
(c) Ratio of CoT Information to E, by input
(d) Ratio CoT Information e, by level detail in COT.
length
1.0
Empirical Sample Complociy
1000
Learning Rule
CoT-Cous
0.8
800
R2E-Come
600
Ertor Type
EJD Ervor
P(R(A(S.))
0.6
Loumiig Rile
0.4
CoT-Cons
400
200
0.2
Eroer Type
E2E Error
Coll Earoe
10
10-1
10-2
10-1
10
10"
10a
10a
10a
Sample Size m
(e) Empirical Sample Complexity.
(1)
Empirical Learning Curves depicting (A(Sm ~ DD")) S E].
Psm
RR
Figure 4: Numerical experiments for deterministic finite automata CoT hypothesis class.
lime-oo ToT (e; H)/e+
Consequently, our theory would suggest gain sample ef- ficiency from CoT supervision. This matches remarkably well with experimental learning results depicted in Figures 5d to 5f. For example, Figure 5e depicts a roughly fold improvement in sam- ple complexity for CoT-Cons compared E2E-Cons the smallest target error levels.
D Proofs for Section 4: Upper Bounds
D.1 Proof of Result
Result (Restatement: Learning Infinite Classes under CoTT-Supervision). Let H (2) x 2) be a CoT hypothesis class. For any distribution D over x y x Z realized by some h4 E H, the CoT--consistency learning rule has sample complexity of
m(e, 6) = -0(Gro
ID. (E; H) + +1) (VC(CCOT((1)) log ((
D.h. (e; H) +1) + log(1/6))
18

---

(h1, ba)
10
0.0
0.2
0.4
0.6
0.8
1.0
0.1
0.3
0.1
0.5
0.6
(0)y (x))
P(A (
(a) Relativve CoT information between pairs of hypotheses plotted against their end-to-end dis- agreement.
(b) The ratio of pairwise CoT information to end- to-end disagreement, plotted against the end-to- end disagreement.
Ooii-Cons
0.8
FaR-Coue
(e: h*)
Error Type
0.6
CUT Eovoe
0.4
0.2
10
10
10
10a
10a
Sample Size
(c) CoT information ZeoT (e; H) function of
(d) Learning curves with and without CoT super- vision.
1.0
Eispitical Sample Complexity
Rul
0.8
80
RWB--Con
60
Fenor
PLELA(S..)
0.6
Uol Broor
120
0.2
Leatning Rule CrT-Olm
10a
10
10
10
10
10a
Sumple
(e) Empirical sample complexity.
(I) Empirical probability of each learning rule re- turning predictor with error.
Figure 5: Numerical experiments for iterated linear thresholds CoT hypothesis class.
19

---

That is, for any m 2 m(e, 6). we have that with probability at least 1 5 over S ~ Dm,,
4h E CoT-Cons( HH, we have RDx (h) S
The key proving this result will be establish the following lemma, which relates the performance of any proper CoT learner with respect to the CoT error to its performance with respect to the end- to-end error. As before, the intuition is that achieving small CoT error implies very small end-to-end error, because the CoT error measures any algorithmic errors, not only errors in the answer (which might be reachable via incorrect algorithm). This relationship captured by the CoT information.
Recall that a proper learner for H. is defined as a learning algorithm that returns a predictor in the hypothesis class. In general, improper learner may return any predictor, not necessarily in the hypothesis class (and this can have some computational advantages).
Lemma 2 (Relating CoT performance to E2E performance via CoT Information). Any proper CoT- learner A : (X y x 2)" - H which achieves CoT-error & with sample complexity m (c,5) also achieves end-to-end error E with sample complexity m m I mx (r(()),8)), where (0, + (0,1) 1) is defined as
(RoT(()) (h): h A (E; <()) inf {RD
Here, m(= .6 denotes the limit to e from below. Moreover, can be related to the CoT information as follows
I (E; H) D.h. (e: (c)
<e(e)= S min
CoT (e;H),
max
1+ ICoT
Proof. Let A be proper CoT learner for H (i.e., it returns a hypothesis in H) with CoT-error sample complexity m (e, 6). Let m 2 m CoT (7(e), 8) and let
S= (<1 V1, 21), .... (Im. Vm 2m Diid
be an i..d dataset drawn from the distribution D Note that we fold the hypothesis h, into D for notational convenience, and we have yi, - = h. (zx). By the assumption on the CoT-error sample complexity of A, we have that with probability at least 1 - 6, h = A(S) satisfies RCoT(h) s
>() <E)).
To show that ie has end-to-end error smaller than e, we proceed by contradiction. Suppose we are in the event {S R.OT (A(S)) < >{E)} and that (2)(()) > E. This implies h E A H) and hence
(e;
(E) == inf (R (h) h E A (E, H)} s RCO (h) S (()) < MEE)
This yields a contradiction. Thus, on the event {S (ECO((A(S) < >(=)), which occurs with probability at least 1 - 5, we have Rz S This proves the first part of the lemma.
We now proceed to relate y the CoT information. Note that the CoT information can be written in terms of y as follows
{- log P (M(x)) = (v. =)]
ToT D.h, (e; H) = inf NEA
{ 2,8.2
= log
sup kE:
(1 - -1-RO- RCT (1))
= -llog
-
inf heA
RCOT(H) (h)
= -loo - ((5)).
The identity log(1 x) 2 x gives ICoT (e; H) 76). The identity - log(1 -x) 5 r-
gives ICoT D,,, HE) S (1)/(1 7(E)) which can be rearranged to give 7(8) 2 ICOT D.h, (E; 70/(1
ICOT (s; H)). Finally, note that >()) > by definition since RooT (h) 2 Rofe vh.
20

---

Note that the restriction that the CoT-leaming algorithm A is proper was crucial in the proof above. In particular, we used à E H in order to derive the contradiction.
For CoT hypothesis class C (> x Z)* recall that we define the CoT loss class over x y x
Z {0, } as the 0 class
(H) == ( (a. y. - 1(h(z) + (v.2)) h E
The complexity of this loss class will appear in our analysis since we will be analyzing learning algorithms that learn with respect to the CoT loss gCo'T"
We are now ready prove the main result.
Proof of Result 2. By Lemma 2, a CoT learner A with a sample complexity of m CoT 8) with respect to the CoT eπror has sample complexity with respect to the end-to-end error of at most m (E, 6) & m Co'T (>(e)_, (>:()) 6), where defined in the lemma. The CoT-consistency rule enjoys
a sample complexity of
CoT (c, = (= - log(1/e) +og((1/))) mA
For the end-to-end error, this translates to the sample complexity of
m
20 (E, 8) S m
GoT
(7(=),0) 0o 5
1
(VC(CCOT(HH)) (H)) 1og(1/7(E)) log((10)))
7(E)
+ ICOT (c;
(VC(CCOT(H)) llog
+ (6;
+ log(1/6)) )
0
ICOT (5;
ICOT (5:H)
0
+11 (vC(CSOT(H)) (H)) llog TCOT (s;
1
)
1 ICoT (e;H)
+ +1) + -1og((10)))
D.2 Proof of Result 3
Result (Restatement: Agnostic Learning under CoT-Supervision). Let H C (2) x 2)x be a CoT hypothesis class. For any distribution DD over X' ) 2, the CoT-ERM learning rule has sample complexity of
m(e, = (S((CCOT(H)) 1og(1/8)
where the agnostic version of the CoT'' information is defined as follows
ISOT (c: 70) inf {R (h) R h H. R R5 2 ze).
where RCOT = inf RCOT (h), Re == inf Rgx())
(h). That is, for any m 2 mm(e 6), we have that with probability least - å over S Dm,, the excess end-to-end risk is bounded
Yh COT-ERM(S;HH)
have R²20(h) S R.2e +
Our aim is to analyze the performance of the CoT-ERM learning rule, which seeks to minimize the CoT--ennlized eиror. This is a natural learning rule to consider in the CoT-supervised setting, and corresponds to optimization procedures that implemented in practice in CoT learning. Similar to the realizable setting, the key to proving this learning guarantee is to relate the CoT' error of a CoT learner to its end-to-end error. This is established in the following lemma, which is analogue of Lemma 2.
Recall that, for distribution D over X x ) Z and CoT hypothesis class H : X y 2, define the optimal end-to-end and CoT errors achievable by H as
RCOT_ inf RCOT (h), Re20 inf ( hER
KER
21

---

Lemma 3 (Relating CoT performance to E2E performance in the Agnostic Setting). Any agnostic
proper CoT-learner A : (X y 2) - H. which achieves excess CoT-error with sample complexity m A (6.6) also achieves excess end-to-end ertor with sample complexity m A (e, (e,6) S
Co'T (T(E) 8), where Y (0, 1) - (0, 1) is defined as
mA
7(0) T
(e; H) inf { (h) -R. -R.OT: h H. (D) R. 2 E)
Proof. Let A be proper CoT learner for H (i.e., it returns a hypothesis in H) with Co sample complexity m (e, 6). Let m 2 m
CoT
CoT (v(E) 5)) and let
S (01 V/, ,..,... ..... (Tmm Mmn 3m) 3D
be an i.id dataset drawn from the distribution D. By the assumption on the CoT-error sample complexity of A, we have that with probability at least 1 - 6, h = A(S) satisfies (CoT(h) <
R.OTT (EE)
To show that has end-to-end error smaller than E, we proceed by contradiction. Suppose we are in the event {S (S(S)) < RCoT + {E)} and that the end-to-end error is larger than desired
RD (h) R2200 t. This implies (6) == inf (RS (h) RCOT E H. R8: 2 R. +8} S R.D (f) R. <<{))
This yields contradiction. Thus, on the event (S: R (S(()) < RCOT +7(E)), which occurs with probability at least - 8, we must have R (A(S)) S Ro +
We now prove our main result, which follows by similar argument to Result 2.
Proof of Result 3. By Lemma 3, a CoT learner A with a sample complexity of m CoT (c, 8) with respect to the CoT error has sample complexity with respect to the end-to-end error of at most (E, 8) S. m ()Tss 5), where 7E)) [=; H) is the agnostic version of the CoT infor- mation. The CoT-ERM rule enjoys a sample complexity of
m (E, o (VCC(C + log((1/)))
For the end-to-end error, this translates the sample complexity
o) o VC((CCT(HL)) + log(1/8)
ZOOT (s:
E Proofs of Section 5: Lower Bounds
E.1 Proof of Result
We will break down Result into several statements and prove each separately.
Result (First Part of Result 4). Let H C (y x Z) be a CoT hypothesis class and let 'D be distribution on X. Let Jm ~ D be an i.id sample from D. For any h E H and >> 0, have that
m < log(1/8)
D. (e; H)
implies that with probability at least 8, there exists h E H with end-to-end error at least E which is indistinguishuble from ht, on this sample.
Proof. Fix h4 E H and e E [0, 1). Let E arg migninggg I (h,,, (If the infimum
not attained, let 7 be an n-minimizer and take n- - 0.) Then, by definition, we have that h has end-to-end error at least & and ICOT H); = I (h., Tt). Thus, the probability that h and
agree on a random input x with respect to both the CoT and E2E behavior can be expressed as
P z>D
CoT (x)
CoT (x), T, (x) [x)) exp( -CCTT (e; H)).
22

---

Now, we compute the probability that h. and h are indistinguishable on the CoT-annotated sample of m points Ti,.... Zm
Lid D:
[ [m], (x:) 11. (x;)) he (x:)) = (xx))
"m D D
P LND
[hCoT(()) = hr Co'll (x), h220(x)) = n (x²)
exp(-m ID., (c: ()))
This occurs with probability at least 8 when
log(1/0) TCoT D.h. (E: H)
The next lower bound result is based on relating the learning problem to binary hypothesis testing and lower bounding the sample complexity of hypothesis testing via the total variation distance. The basic idea of relating the performance of a statistical estimator the total variation distance is due to LeCam [11]. We also point to Yu [39] for classic reference statistical lower bounds, including Le Cam's s method, as well as Polyanskiy and Wu [40] for modern reference.
Henceforth, for a hypothesis h E H. we will denote by PA. P(X x y x 2) the distribution over ioput-CoT-output tuples where the marginal on X' is the input distribution and the distribution over (y, 2) given is the Dirac measure at h(z).
Result (Second Part of Result 4). Let A x Z) + H be any learning algorithm that
maps a dataset S {21, Mb, 2)) to a predictor h. Suppose there exists h1 h2 E such that P [M/20 (x) + hg2² 2 2e. Assume that 5m (D & (l.,)) (m) the sample size is R~D
upper bounded as
log( 28
ICOT (h1, h2)
Then, we must have
RRD... (A(S 2 88 Moreover, the expected error of any CoT-learning algorithm A is lower-bounded as,
inf P
b. Sth
sup E
[R [RD,,. (A(S))))
P 2 hi M R
1
sup
[ng20 + ho2e (x)) exp(- ICoT(M, h2))
h. ER Smahh
1 sup exp(-m DDh, (e: 7)). h.EH e20
2
Proof. Let us consider the pseudometric on the hypothesis space H. defined by + hg200 (x)],
( h2)
F
[
z>D
which measures the end-to-end disagreement. Note that (2) = (h h.). Moreover, note that de satisfies
d (h1, ha) S d h2) + d22 ha).
Let A (X' x y x 2) + y be any learning algorithm. Assume towards a contradiction that R2 (A(S))
2 E] < 6, vh E H. By assumption, there exists a pair of hypotheses h1, h2
S~PP
such that - (1, h2) > 2E. Consider the event that the predictor returned by A close he in end-to-end behavior. & == (dd A(S)) < æ}. We will consider the probability of this event when the data generated by h1 and fgg By the assumption on the performance of the algorithm.
we have that the probability of this event under h2 is bounded as
P Smp8m
18 A(S)) $] 2
23

---

On the other hand, under S ~ Pha note that by the triangle inequality of d we have
d ( ((.)) = d A(S) 2 22 (hi, h2)
22 (1)))
2
2 $6
where the first bound by the assumption on h1, h2 and the second is by the assumption on the performance of the learning algorithm A. This then implies that
TiD (ho. A(S)) < S.
By the definition of the total variation distance, this then implies that the total variation distance between pm and p&m must be at least h1 TV (P Pm = sup Ph (A) P (A) 2 Phi Ph
(E) pm (E) 2 28. b2
Thus, to derive contradiction, we will relate the total variation distance the relative CoT infor- mation and choose m small enough such that TV (P pi variation distance as follows:
< 1 - 28. We compute the total
TV (Ph) p@m)
Σ
Pha (Zimm Viom 21:m)
Pho (2i1mm: Flim Z1:m)
Σ D(Fim)
Σ
[1 Z1:m) = h1(x1m)} - 11 21:m) h2 h2(21m))
2 2imm
(a)
Σ
D (Fimm) (1 (f1sm) * ha (2((1m)))
Zim
P
Ei E [m] (xxs)) + (x)))
Fi.m Dim
=
P
hh (I) = (1)
R~D
1 exp( I (h2 h2))
To step (a), note that the function
Afh1, h2 (Iim F1:ms 21:m) = 1 (311m 21:m) hr (21:m)) 1 (11:m 21:m) he hz(x1mm))
takes the value 1 either if 1x)m (y1 21mm) and h2 (x) + (Nom Z1mm) or if log (x (Nim, zism) and hy (mm) A (Nism 2. Thus, in the sum Emamoiii we only need to consider values of yimm 31sm that agree with at least one of h1, 112.
To guarantee that TV (Phy Ph2) <
25, it is enough to have
log( 1
m ICoT(hi, (h1,h2)
This proves the first statement.
The second statement, in terms of the expected error, be proven by analogous argument and related to the CoT information via the above calculation of the TV distance. In particular, fix any h1, h2 H. and consider the predictor returned by the algorithm h = A(S). Convert this predictor randomized test follows
h1
W.D.
G (12
To
(A + (ha.h) Uh
l12
w.p.
(N. +) hb)
Under hi, we can lower bound the expected error via the triangle inequality as follows
de2e h)) do (h1, h) + d (12
E pm
c (2 hn)]
d 122)
E Sup2
< E
12 (h, (h,
Sup
24

---

where we used the fact that dh1, h) + + (h2, h) 2 d h2). Similarly, under h2, we have
d (h2, h)
E
(h, [oa) =dy d (1)
E
E
D (h, (h,
2e
S S
Sm Sm
d (h1 h) + dz (h2, h)
Sm Smpm
Now, consider the prior π = [6 + )(g)) and let h ~ n. Then, we have
sup K.EH P.
E
d (A(S),
2
E
E Smup
(A(S),
k.))
1
E
D
22
(A(S),
+
E Smppo
[d (A(S), (12))
2
20
122001 (h1, h22)
P SmPR
h + h1
+
P Sm
h + 102
d (h1,
(1-TY TV (Prg Phen))
2
where the last inequality follows from the minimum average probability of error in binary hypothesis testing (or, equivalently, the supremum representation of the total variation distance). Now, using the previous calculation of the total variation distance in terms of the CoT information, we have
sup E h. EH Smpp..
[ (A(S),,.)]
sup hI
I. ZND
[M]
+ 12
11220(1) (x)] exp(p- CoT T h2))
sup
sup <>0
P anD
[ + h 2 (x)] exp(- m IpoT(h.,1))
h. hEA heA (e:H)
sup sup E expp -m m
inf
I (h,, IpoT(h,,h))
E. e>0
(e (c:H)
(
sup 8 exp(-m- m ID (e;H)). h.Ew
6>0
In step (a) we used the fact that
IP
[h.20 (x) + 1220 (x)] 2 e, vh E h e o H), and in step (b)
we used the definition of the CoT information ICOT (E; == inf Anf (e:00 I h,).
E.2 Proof of Result 5
The next upper bound will use iitormation-thhoreee tools to establish lower bound that scales with the size of the hypothesis space. As with the previous lower bound result, the strategy will be to reduce the learning problem into a hypothesis testing problem. However, unlike the previous results, which considered binary hypothesis testing, here we will consider a reduction to multiple hypothesis testing. The main idea is to test between a finite collection of hypotheses whose minimum end-to-end disagreement e. If we can show that is impossible to reliably distinguish between these hypotheses with given sample size, then this implies that the best learning algorithm must at least incur an end-to-end error proportional to E.
To state our result, we begin by recalling the definition of an e-packing.
Definition. Let X be set and let d be (psendo A subset {u1,..., C % is called an E-packing of X with respect to d if mingz d(x,,, 2,) 2 E. The packing number is defined as the size of the maximun packing, M[; X, d) max(m : E-packing of X of size m).
The main information-theoreee tool we will use will be Fano's inequality [39, 41], stated below.
Lemma (Fano's Inequality). Let W (n]) Then,
X
Y
W be a Markov chain, and assume W
() + +ho
> 1 1(X;Y) + log?
P. :. W + W 21-
log M
log M
25

---

Similar to the previous section, for h E H. we will denote by PA the distribution on X' x ) x Z induced by the hypothesis As before, the marginal over X' is D for all Ph. However, unlike the previous section, Ph (y.= is not a Dirac measure since to first passes through the noisy channel Q. The distribution Ph. is defined as
(=) D(x) Quy, h(x)).
We are now ready prove the result.
Result (Restatement of Result 5). Let H ()' 2) be Coll hypothesis class and let DD be distribution over X. Suppose that Il,...,Imy Zm ~ D. Let Q E P( x Z y x ) be a noisy
channel from h(x) = (y,2) to observations y, Let CQ = max DxL (Q( a) 6)) be the capacity factor of the chamnel. The learner observes the noisy sample S = { Wi, 3,),, Define (h1,
the pseudo-ment metric d h22 = Ps [2(20()) + hr²=(z)], and let M(; H. d be the E-packing
number of HH with respect to this pseudo-metric. Then, for any algorithm A observing the CoT- supervised sample of size m, the probability of having large end-to- ervor is lower bounded as
m. ...CQ sup A1 Ag log M (H,, (H,
[T I h2)] + log
P h. E. S-Ph. mm
sup
R (A(S))
2
Proof. Let H'' = [hl..... hm C H be an E-packing of H with respect the end-to-end dis- tance (22, h2) = PEwD P (x) + (x)). where M = M(e; H. dz²)) Consider the prior this packing,
distributed uniformly
hMr)) }). For any learning algorithm
A : (X' x y x 2)' + H. consider the modified algorithm A' : (X x y 2)" + H! which projects A onto the packing H'. That is,
A'(S) arg min de (A(S), hE?t'
The test error of A' can be related to the test error of A via the geometry of H under the pseudometric d In particular, letting h = A(S) and = ASS),, we have that for all h E H',
de S dz (h, h) + ( S 2d (h, h). where used dz (h, h) S ( h), vh H', which follows by the definition of h as the projection h onto H'. Thus, we have that, for any E H', dz h) 2 = d h) 2 2/2. Also, note that h + h delo h)) 2 Thus, we have,
h h
(h. h) 2 = S c dh h) 2 8/2
By Fano's inequality, we can lower bound P[h + M) which in turn implies the following lower bound on the probability of A having large an-to-end enror,
( A(S)) 2 s/2] by Sn p.
P
P h. M.r Sn pmm
(h., 2c]
P
1h4 + A())
h, NT Sm Smm
2 1(::; log 2
log M Ms; H. doze)
2 SUPxEP(H) I(h.; S) + log
log Me; Hl dofo)
The first two inequalities are just restating the implications above, the third inequality is Fano's inequality, and the last inequality simply uses I(h,;S) < sup, I(h,; That is, we bound the mutual information under the uniform prior over the packing, x Uni((H'). by the supremum of the mutual information over all priors (i.e., the capacity).
Now, compute the mutual information [(h,; and relate it to the CoT information. First, let P = E. [Px] denote the mixture of P/. under æ, and note that
bER
[h,,, S) = EE [De. (P
ppm)] <
E
[DL
h
h2 [
m-
EE hy 12g
Dea. (Ph, (/
hmm
hs Jigro
26

---

where the inequality follows from the convexity of the KL divergence in the second argument and Jensen's inequality, and the last equality is by the chain rule for the KL divergence.
Now, let us compute the KI. divergence between the distributions induced by a pair of hypotheses and relate it the relative CoT information between them. For convenience, let us fold in the output into the CoT and use a bold z to denote z = =3,
Pr. (I, 2)
log D(x)Q(z (x)))) D(r)Q(= (12()))
DxL. (Pri P122)
E P,
log
E 3, Pk1
Phu (xt, 2)
Q h1 (1))))
Σ Q(z h1 (z) log
anD
Q(= h2(x))
==EXX2
Q(= h1 (1))
1 (2) = h2(2)}
Σ
Q(= (x)) log
anD
Q( h2(z))
=Eyx2
Q( (x))
IE wnD
11h((z) # h2(l))
E
Q(= h1 h1(x)) log
Q(z ha(x))
=Eyx2
(
(1) h2(x))
E
Q(2 (1)) log
Q(=
11 (x:)
a>D
Q(2 h2(z))
#EVx2
Q(2 x12)
E z>D
((h1(1) # h2((x))
max
Σ xEyx2
Q( 21) log
x 2
Q(2 z22)
( Cq
p [r)(2) * h2(2)l anD
(9) Cq log RnD
p [ (a) h2(2:)
@ Cq I (11, h22)
Step (a) follows by noting that Σ, Q(z b (I)) log Q h2(m)) 0 when (1 h2(xx). Steps
Q1+) kilw)
(b) and (c) are simply bounding the KI. divergence between the observations under two different hypotheses that differ by the capacity of the channel, Co max;, ... DxL (Q(- x ==) #2)). Step (d) uses the identity z S - log(1 - I), and step (d) is the definition of the relative CoT information between two hypotheses.
Plugging this into the previous bound proves the result.
sup
P Tm
RS
(A(())))
(A(S))
2 2.
PP h.T h. S
[ (hi, 2 E/2]
h, EHEEH
p&
m Co sup
E hi hgrwi
CooT(hi, h2)] + log 2
log M (H, 1220 E)
In particular, this result implies that when
log M (H, d=20,)
m <
2. Co
sup, 1,.
E [IOOT (11, + log 2
the probability that the error more than e/2 is at least 1/2,
1 2
sup P H.
Ro (A(S)
2
S-P pm
2
2
Now, let us discuss the role of the noisy channel in the setting of this result. The noisy channel models noise in the learning process. For example, errors in human-created CoT annotations, errors
27

---

in the output labels, or any other type of noise. For simplicity, let consider symmetric channel over y parameterized by an eтror level and defined as
Q 2) (1 e) 8x te. Unif(y) 2).
We can compute the channel capacity factor Co for this channel. Let * y. Y Z be two different symbols to be transmitted through the channel, and suppose the error level is non-zero, E (0, 1]. For convenience, denote ()/ 2| N. Da. (Q(-) x))1Q(-1 y))
E log Q(= | x) Q(= y)
Q(x x))
Q(y x)
Q(2 x))
= [( x>) log
+ Quy x)) log
+
Σ
Q(z x log
Q
y))
Q3y y))
Q(z y)
1 e+ e
e + e/N
e/N
e/N N
log
log
log
N
e/N
1 e-eN
e/N
xte,*ty
1 e e
1 1-
C
1 - - e-e
log
log
N
e/N
N
c/N
N(1-e)
= (1 e) log
1
Intuitively, this is a decreasing function in the error level e, decreasing towards 0 as e - 1. This corresponds to the fact that it harder distinguish between hypotheses when the observations more noisy. For e = 1/100 and (y x 2 = 1, 000, the capacity factor is approximately Co s 11.39.
15
10
g
5
0
10
10-3
10
10-1
10a
e
Figure 6: Capacity factor of Q function of error level for |) x 2| 1,000
Other Topics
F.1
Learning with Mixed Supervision
In many situations, CoT training examples may be difficult or expensive obtain, for example. because they require manual human annotation. On the other hand, input-output examples without CoT annotation might be much more readily available. such cases, one might have a dataset that includes large number of end-to-end input-output examples and a small number of CoT-annotated examples. What types of learning guarantees can we establish in such a setting?
The following result, an extension of Result 1, analyzes the sample complexity of the consistency rule when applied me2e end-to-end examples and mcoT CoT examples.
Result 6 (Learning with Mixed Datasets), Lei H C (2 2) be a finite CoT hypothesis class, and let D be distribution over X. Consider i..d dataset, S Seze U Scots consisting of meze
28

---

input-output examples and Moot Col-annotated examples
Seze {(1, 222 1,,00z, 220
) : [(a, 222 ,hx
CC'T
"1,ht (x; NEm
D. Suppose the number of end-lo-end examples is 7 times the number of CoT examples, so Mele -y- and let meot = m. Then, the e2e- Consissnsyyyycy rule has sample complexity with respect the end-to-ena error of
where u muze" 210 ..... Meor
m(c, 8) = log |7| + log(1/5)
8 I Too D.h, (e;H))
That is, for m 2 m(e, 8). with probability at least 1 over the draw of S Seze U Scot.
Yh E HH such that Rg R (h) 0, we have Re2 (h) S E.
Proof. We would like to bound the probability of the bad event
Eh H. RDx (h) > E, Rig Be2n/CoT (h) = 0}
over x420 ..... moze 21
m D. Fix any h E H with end-to-end error R8 (h) (x) # e2e (2e(h, (x)) e (i.e,, h E Apo(es H. h.)). We bound the probability that h
cut
P
aND
consistent with S = Seze U Scot, E CoT-Cons( S: H) = {h E H: Re2e/CoT (h) = 0}, as follows
P S= SeaulSee
COT-Cons H)]
P [Vi [meze], h (x; n 2,22(1 [1:200] Size
P VV [mcot]. ht CoT (2;
h CoT (I h 22200 (z("t()))
P 20 (z₂) (x²) maze
I [ CoT (x) (hooT(T2 (zz), 1020 (x;) (x))(x))
Moot
(0)
5 (1 8) m)me (exp (-ISoT (h h1)) Moos
exp Meze 8) (exp (-ICoT (h,, hi)) Meot
2 exp (- E) exp (-Moot ICTT (e; H))
TC'' cxp (-Me20 E Moot D.h. (E: H)),
where step (a) applies Ref > & (since e (e; for the first factor and uses the
definition of TCoT for the second factor, step (b) is the identity log(1-x) -r for x E (0, 1), and step (c) is by the definition of ICoT (e; H) and the fact that h A (e; H, h.).
Now, we write meze = Meot = and set m
log +ogg((1)) 7-+2233 (e:7)) This guarantees that the
probability that any fixed hypothesis with error larger than 6 is consistent with S = Saze U Scot is at most
IP US2
[h E CoT-Cons(S: (S:H)) <
H
Applying a union bound over H. then shows that
Eh H: Roo > e, RS Re2e/CoT (h) = =0] 6.
IP S=S.p.US.oo
F.2
CoT Learning with Inductive Priors
Encoding prior knowledge about solution structure is critical for learning complex functions, such as those representing multi-step reasoning processes, particularly from limited data. This is especially relevant in chain-of-thoo of-ohhugttthhtttthh settings, which are often applied to learning such reasoning processes.
29

---

The chain-of- tfotthtttttttthhh trajectories can be viewed as additional supervision for the intermediate steps of an algorithm, helping to align the learner to the ground-truth algorithm, which may otherwise be very difficult to learn if only input-output examples are observed.
key idea in learning algorithms is the so-called Minimum Description Length (MDL) principle. This encodes prior or an inductive bias in the learner that favors hypotheses that have small description length (e.g., thought of the length of program code or the size of Turing machine's state space). This is also related to the notion of algorithmic complexity in algorithmic information theory [42, 43].
In this section, we consider a minimum description length type of learning rule for the chain-of- thought setting. This also provides an extension of Result to CoT hypothesis classes that are countably infinite.
For prior p over hypothesis class H. we define the chain-of-thought MDL rule corresponding to the prior p as
MDL, GOT (S:
arg max p(h).
(1)
hECoT-Cons(S:H))
That is, given a CoT dataset S. MDL p p among hypotheses that are CoT-consistent with S. One way to define such a prior p over H. is through a prefix-free description language d H + {0, 1} which maps hypothesis to a bitstring description. The prior can then be defined as p(h) = 2 2-14()) in which case MDLCoT(SS) (S; H) arg angne [d(h) selects the minimum- -dchritttdtsiitttoonn CoT-consistent hypothesis.
GoT (S; H) selects the hypothesis that maximizes the prior
The following result provides learning guarantee for MDL GoT in terms of the likelihood of h, under the prior p and the CoT-information metric DD.. (e; H)).
Result 7 (Learning with Chain-or of- Thought and MDL). Let H. be a countable autoregressive hypoth- esis class and consider prior p over H. Let be an i..dd dataset of m examples drawn from distribution D over X. Then, with probability at least 18 over the draw of S, any CoT-consistent hypothesis h E CoT-Cons(S; H) has its end-to-end error bounded by
(h) Sen == inf {e :>>0 ICTT (e; H) 2
log(1/p(h)) + log(1/8)
This in turn implies a sample complexity with respect to the end-to-end error for the autoregressive MDL rule MDL CoT of
log p(h.) + log
m(e, 8) = -0
D.h. (E; H)
That is, for m 2 m(e, 8), with probability at least 1 over S = =(x1 (II,..., am Hid D,
wh E C H)) we have Ro (h) Se.
Proof. Following the argument in the proof of Result 1, for any fixed h E H and any En > 0, the probability that h is CoT-consistent on S, f E CoT-Cons( (S; H) = (h H. end-to-end error Rg (h) > Eh, is bounded by
RoT RCoT(h) = 0} yet has
IP D~7mm
RCOT (h) = 0, R (h) > En s exp(-m I (h,, h)) < exp( (pp ToT (ENS 70).
For each h E H. will target end-to-end error Ey in prior-dependent manner such that
RC (h) 0,
Ro (h) en < 8p((h).
S~1am
This occurs if sy is chosen such that
exp(-m: m -CTT (E)) < 6p(h)
CoT D.A. (EN: H)) H) > log(1/p(h)) + log(1/5)
30

---

Thus, we define the target error E/ for h as
log(1/p(A)) + log
Coll = inf 0: D.N. (e; H)
m
Note that this can viewed in terms of the generalized inverse (ID,h, (: H)) where the general- ized inverse of a function f defined as (x) = inf f(v) > x}. This is well-defined since I H-) an increasing function by Lemma 1.
hyppehhssstentthptttsssisss Now, by union bound, we have that the probability that any CoT-consistent hypothesis exceeds its target end-to-end error is bounded by
3h E H: RS
RCoT (h) = 0, Ro (h) > Eh
SwD@m m
P [h E CoT-Cons(S;;))) (S) sn]
NER
8p(h) 5.
NEW
Since h, E CoT-Cons H). we have that p(h.) s p(MDL, (ST; H.) by definition of MDL CoT This, in turn, implies that
2 log(1/p(h..) + log(1/6)
RD (MDI,p CoT (S; < inf 0: ICOT I (s;
with probability at least - 5. Noting the property that f(x) 2 y inverses, we obtain a sample complexity
f (y) for generalized
1og p(h. + log
m(e, 00
D.h, (8; (8; H)
Corollary 1. If the prior p is defined as p(h) = Id(h)) terms of a prefix-free description lan- guage d - [0, satisfying Kraft's 's inequality Σn 2 Id(hh) < 1, then the sample complexity of autoregressive MDL rule MDL, CoT satisfies
[d(h,)] log 1 D.h. [E (e;
m)e,))= 0
One advantage of such MDL-style analysis is obtaining sample complexity that is instance- dependent (i.e., -ependdent).. In the standard end-to-end setting, we obtain sample complexity of (ooog((/p(h.))//ee In the CoT setting, we obtain an instance- -deendded description the sample complexity in both the numerator and denominator through the CoT information I (e; H).
F.3 Transfer Learning & Out-of-Distribution Generalization Under CoT Supervision
In many applications where chain-of- of-thhught learning is applied, nut-of-distributiin generalization is a key aspect. This type of generalization requires compositional reasoning abilities, for example, learning a of generally applicable atomic skills that can be recombined to generalize system- atically to novel combinations of known elements. Of particular interest is learning from simple problem instances and generalizing to larger and more complex instances. This is sometimes re- ferred to as length- genrrrzzznaiiiiionnn when the notion of increased complexity corresponds to longer inputs.
Chain-of-thir oftthoughttthttttt learning has important implications for this type of generalization. In particular, it allows direct supervision on the "atomic skills" and how to combine them to solve problems. This can, in principle, enable systematic generalization by transforming the learning problem from one of learning input-output patterns to one of learning general principles that can be applied beyond the training distribution.
31

---

In this section, we explore how the CoT information measure can be extended to analyze generaliza- tion under distribution shift.
The following generalized definition of CoT information captures the amount of information re- vealed about the end-to-end behavior a test distribution Duest from observing CoT-annotated sample drawn from a training distribution De..
Definition 2 (Relative CoT Information Between Pair of Distributions). For a CoT hypothesis class H. C (Y' z)², we define the relative CoT-Information between a distribution Dir and D rest as
{ log IP DIDD
ICoT Du (e; (;H,,
inf hE HEADO Dencs (s:H,b.)
[NCoI(
(x) -oooTT (1), (x) - (x))
where the infimuum is A (e; H. N.), the set of hypotheses that disagree with h4 's end-to-end behavior (i.e., output) on the test distribution with probability greater than E,
Droat
Ale c2 Prent (E; H,) == { h ( E
H:
P I.-Dsest
(1220() + h 222e (x)] >E]
Unlike the in-distribution setting (where Drest = Drd,, I ily hold for arbitrary CoT hypothesis classes and pairs of distributions. However, we do have
- (e; 11, 2 & does not necessar-
I Drom (E; H.,
inf hEAg Peen (c:H,h.)
(R):
With strong CoT supervision on a sufficiently diverse training distribution, we would expect the relative CoT information be large.
Analogous results to those presented in the main text in terms of the (standard) CoT information also apply in the transfer learning setting via the relative CoT information measure between two distributions defined above. For example, in the finite hypothesis class case, we have the following analogue of Result 1.
Result 8 (Transfer Learning with Chain-of Thoun-of-Thought Supervision). For any finite CoT class H and distributions Dir (training) and Drest (test) over X,, the CoT consistency rule has sample complexity with respect to the Drest Dues--end-lo-end error of
log 77 + log(1/0)
mlg,
TCoT Drr Draas (E; H,h,) h.)
That is, for m 2 m(E, 8), we have that with probability at least 1 - 8 over S = (zI,.... Tm Lid Lid
Dtn.
vh E CoT-Cons (S;H), we have Rele (h) S
Proof. Fix any h E H with end-to-end error under Drost larger than e, i.e., Ro (h) > E (so h E Alle
(s; H, h. )). We bound the probability that h is CoT-consistent on S, h E CoT-Cons H.
Drem
(h E H: RCoT (h) = 0}. as follows
(CnnCoonSSS:ai P [h E CoT-Cons( (S: H0) = P (oTT = 1. CaT ( = M.2 -x:)))))) S-Dem
S-D@m
P ZND
[A (x) = 11 CoT (x:), h (x)) = (x=))
I exp (-m I P
-Duos (E; H, h.)))
where we use the definition of the relative CoT information and the fact that h E 2g20 Diea (e; H. h-).
Choosing m 2 m(E 5) in the theorem statement guarantees that
3h E H: Ro (h) > c,
RCOT RCoT(h) =0] 5
SND
32

---

10
6
3.5
-u (s; h")
Training Length
(6: (...))))
3.0
Test Length
2.5
2.0
2
7Mt
1.5
1.0
1.0
0.8
0.6
0.4
0.2
0.0
1.0
0.8
0.6
0.1
0.2
0.0
(a) CoT
D (e; H4 h.) with fixed test distribution at length L = 5, and varying the training distribu-
(b) DD - (, M, ht) with fixed training distri-
bution at length L = 5, and varying the test distribu- tion.
tion.
Figure 7: Simulations exploring
I DDr Dront (c; kw)
An analogous result also holds for the infinite hypothesis class setting. Example 7 Gength--Generalization in Finite-State Machines), Example 4 shows that
min ZD. (e; H) 2 | (C+1)
<>0
for the class of finite-state machines when h, 's transition graph is f-connected and D is uniform distribution over inputs length In fact, the same line of reasoning shows that
min TCo' ES0 Du,+D (E; h,, 2 | (e+1)
for any distribution Dust (i.e., of arbitrary length). The chain-of-thougle annotations allow each component the FSM's transition function to be identified and hence enable generalization to arbitrary test distributions.
Figure depicts simulation results with the DFA example presented Appendix C, exploring the relative CoT information between a pair of distributions, ICoT DD (e; H. h,) as defined above. Fig- ure 7a depicts the CoT information for a fixed test-distribution, varying the input length in the train- ing distribution, showing that the CoT information curves increasing with the input length. This suggests that longer, more complex inputs reveal more information about the underlying hypothesis and its input-output behavior. On the other hand, Figure 7b depicts the CoT information for fixed training distribution, with input length L = 5, varying the test distribution. We see that the CoT in- formation remains relatively large, for longer and complex test inputs. This suggests that, under CoT supervision, the observations reveal enough about the hypothesis to identify its behavior beyond the training distribution.
33

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect paper's contributions and scope?
Question:
Answer: [Yes]
Justification: The claims are theoretical, and correspond to specific results whose proofs are included either in the main text or in the appendix.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
o
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Limitations, relationship to related work, and directions for future work are discussed in the final section of the paper.
Guidelines:
о The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
6 The authors are encouraged to create separate "Limitations" section their paper.
The paper should point any strong assumptions and how robust the results are violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The au- thors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might be used reliably provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to ad- dress problems of privacy and fairesss.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best
34

---

judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: The assumptions for each theoretical result are part of the result statement, and complete proof' are included.
Guidelines:
5 The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theo- rems.
The proofs can either appear in the main paper the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition.
Inversely, any informal proof provided the core of the paper should be comple- mented by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
The paper includes empirical simulation results exploring the proposed the- oretical quantities. The simulation section in the appendix includes details on the experi- mental set up, and code for reproducing the results will be made available.
Justification:
Guidelines:
The answer NA means that the paper does include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or the contribution it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, other means that are appropriate to the research performed.
specific model and empirical evaluation.
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
35

---

(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g.. a large language model), then there should either be way to access this model for reproducing the results way to re- produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case au- thors welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification:
The paper is mainly theoretical, but does include few empirical simulation results. The code will be made publicly available.
Guidelines:
o The answer NA means that paper does not include experiments requiring code.
o Please see the NeurIPS code and data submission guidelines (https://nips.c cc/ public/guuides//odeSuumu (osco for more details.
o
While we encourage the release of code and data, we understand that this might not be possible, so No an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: //nips.cc..c//////o////// cttccc//ppucc http:p/ppupccess/////ppppooaaash Caaeeees/oooSSmmeeeeeeee is wwwiisssssoooosoo onPolicy) for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Question:
Answer: [NA]
Justification: There are no data splits, hyperparameters, etc.
Guidelines:
The answer NA means that the paper does not include experiments.
36

---

The experimental setting should be presented in the core of the paper to level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined other appropri- ate information about the statistical significance of the experiments?
Answer: [Yes]
Justification:
The empirical learning curves are estimated from several trials and include confidence intervals.
Guidelines:
The answer NA means that the paper does include experiments.
o The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, imitialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK report I-sigma error bars, but one should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative етrог rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [NA]
Justification:
The simulations are simple and require modest computational resources.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
37

---

9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics attps://neurips: /ttpa//aiiiiiiia///.e/././pppppa
Answer: [Yes]
Justification: This work is theoretical in nature and conforms with the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Due the theoretical nature of this work, we find such discussion to be unnecessary.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
o The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: No data models will be released part of this work.
38

---

Guidelines:
0 The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by re- quiring that users adhere to usage guidelines restrictions access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [NA]
Justification: No external assets were used as part of this work.
Guidelines:
o The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
0 The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
assets are released, the license, copyright information, and terms use in the pack- age should be provided. For popular datasets, paperswi paperswithcode thcode. com/co/caaaooooo ddtaasess has
curated licenses for some datasets. Their licensing guide can help determine the cense of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documenta- tion provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.
Guidelines:
The answer NA means that the paper does release new assets.
9 Researchers should communicate the details of the dataset/code/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
o The paper should discuss whether and how consent was obtained from people whose asset is used.
39

---

о At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the pa- per include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
This paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, cura- tion, other labor should be paid at least the minimum wage the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
This paper does involve crowdsourcing nor research with human subjects.
Guidelines:
o The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equiva- lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification:
The paper methods do not involve LLMs.
Guidelines:
o The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
40

---

o Please refer to our LLM policy for what should or should be described.
41


Reviews:
[{"review_id": "ckdMIFctdf", "reviewer": "Reviewer_zRps", "summary": "This paper proposes a theoretical framework for understanding the statistical benefits of chain-of-thought (cot) supervision. The authors introduce a the concept of cot Information, which quantifies how cot annotations can help distinguish between different hypothese classes more effectively than standard input-output supervision. They show that cot supervision can significantly reduce sample complexity, sometimes requiring far fewer examples to reach the same accuracy. The paper provides both tight upper and lower bounds using this newly proposed information measure. Theoretical results are extended to agnostic settings and infinite hypothesis classes. The authors also include case studies, such as regular languages with state trajectories as cot , where cot supervision yields up to 600x gains in sample efficiency. The work positions itself as going beyond prior studies that focused on VC dimension or structural assumptions without explicitly modeling the information gain from chain-of-thought.", "questions": "I thank the authors for their novel contribution. Cot information measure is central to the paper, but for much of the non-theory community, it’s unclear how one could estimate or approximate it in practice. If we have a dataset with cot annotations, is there a way to tell whether the cots are informative under your framework? Even a heuristic or proxy would help bridge the gap between the theory and practical applications.", "limitations": "The authors addressed some of the work's limitation in the conclusion section.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength: To my eyes, the core idea of cot information proposed in the paper is novel and interesting. The paper presents a new perspective to measure how helpful chain-of-thought supervision can be for machine learning. The idea of cot information captures how much more easily a model can learn when given reasoning steps, not just final answers. To my eyes, the theoretical results are also correctly constructed to show cot can need far fewer examples, and this is true in both clean and noisy data settings. The idea that cot supervision helps learning because it adds information per example is well motivated and explained. The paper also gives clear examples and simulations that match the theory and make the results easier to understand. The overall presentation is clear and careful, and I think the community will benefit from this paper a lot.\n\nWeakness: Primarily this paper can be deemed lack of experimental diversity: Simulations are instructive but limited in scope; broader tasks (e.g., toy tasks in NLP or vision) would strengthen the case. However, this is not crucial for the topic of this particular conference submission, which focuses on theoretical foundation for LLM prompting techniques.", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thorough and thoughtful review. We are glad you found the core idea of CoT information to be a novel and interesting contribution, with a clear and well-motivated presentation.\n\n**Question about estimating or approximating the CoT Information in practice**\n\n> *I thank the authors for their novel contribution. Cot information measure is central to the paper, but for much of the non-theory community, it’s unclear how one could estimate or approximate it in practice. If we have a dataset with cot annotations, is there a way to tell whether the cots are informative under your framework? Even a heuristic or proxy would help bridge the gap between the theory and practical applications.*\n\nThank you for your kind words and for this important question. We have given this some thought and have a few preliminary ideas that we are interested in exploring further in future work.\n\nFirst, note that the CoT Information is defined in terms of the infimum of a particular negative log probability within some constraint set. Thus, one approach to estimate or approximate this quantity for specific model classes and tasks is to relate this to a constrained optimization problem, which can be approximated by optimizing the Lagrangian corresponding to the parametric model class. For example, suppose one has a parametric model class, like a neural network, $f_\\theta: \\mathcal{X} \\to \\Delta(\\mathcal{Y} \\times \\mathcal{Z})$ parametrizing a probability distribution over CoT and output given the input. For example, $f_\\theta$ could be a Transformer network that outputs a sequence composed of the CoT followed by the output. We may then seek to estimate the CoT information as the solution to the following optimization problem over the parameters of the model $\\theta$:\n$$\\min_\\theta \\max_{\\lambda} -\\frac{1}{n}\\sum_{i} \\log f_\\theta(y_i, z_i | x_i) + \\lambda \\cdot (\\epsilon - \\frac{1}{n} \\sum_i f^{e2e}_{\\theta}(y_i | x_i))$$\n\nThis optimization problem can be approximated via standard gradient-based optimization methods. Here, ${(x_i, y_i, z_i)}_{i}$ is a dataset that includes CoT annotations.\n\nWe also note that, as per section 5 on information-theoretic lower bounds, the CoT information can also be related to a mutual information between the joint probability distributions over $(x, y, z)$ induced by different hypotheses. Thus, another approach would be to try to estimate this mutual information."}, {"review_id": "ZAJQom1ajv", "reviewer": "Reviewer_QDtR", "summary": "This paper develops a statistical learning theory framework to analyse the benefits of CoT supervision, introducing a quantity called **CoT information** that quantifies how much additional signal CoT annotations provide for distinguishing correct from incorrect models. The authors show that, unlike standard supervision, which minimises end-to-end loss, CoT-supervised training minimises a richer loss that includes both intermediate reasoning steps and final answers, leading to potentially much lower sample complexity. Through both upper and lower bounds, the paper demonstrates that informative CoT traces can significantly accelerate learning and provide theoretical guarantees in both realisable and agnostic settings.", "questions": "1. The paper shows that an \"informative\" CoT is beneficial. This raises a practical question: what structural properties can make a CoT informative? Have the authors investigate this?\n2. In the agnostic setting, the authors admit that CoT supervision can hurt if the hypothesis class poorly fits the CoT traces. How practical is it to design hypothesis classes that jointly fit outputs and reasoning traces?\n3. Do the bounds extend to stochastic CoT annotations, such as those from RLHF-annotated intermediate steps or from uncertain model generations?", "limitations": "See Weakness.", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- The paper is exceptionally clear and well-organised.\n- CoT prompting and fine-tuning can enhance the LLM performance significantly through empirical results [1,2]; however, it is still unknown why CoT can lead to the performance gain. This paper tried to theoretically understand an important but challenging problem, which is significant.\n\nWeaknesses\n- The primary weakness is that the empirical validation, while effective for illustrating the theory, is confined to symbolic tasks (e.g., learning finite automata). While this is a standard practice for theoretical papers, the work would have been even more compelling if it included a small-scale experiment with a neural model (e.g., a small transformer). Such an experiment would help bridge the gap between the theoretical framework and current LLM practices, showcasing how these insights apply to the very models that motivated the research.\n\nNote: I can't validate the theoretical correctness as my primary expertise is not in statistical learning theory. :)\n\n[1] Wei, J., Wang, X., Schuurmans, D., Bosma, M., Xia, F., Chi, E., ... & Zhou, D. (2022). Chain-of-thought prompting elicits reasoning in large language models. Advances in neural information processing systems, 35, 24824-24837.\n[2] Shao, Z., Wang, P., Zhu, Q., Xu, R., Song, J., Bi, X., ... & Guo, D. (2024). Deepseekmath: Pushing the limits of mathematical reasoning in open language models. arXiv preprint arXiv:2402.03300.", "was_revised": true, "final_justification": "My concerns have been addressed, and I would like to maintain my original score.", "rebuttal": "Thank you very much for your thoughtful and constructive review. We appreciate your positive feedback on the presentation and clarity of the paper, as well as the importance of the theoretical contributions to understanding the emerging CoT paradigm.\n\n---\n\n**Questions**\n\nThank you for your interesting questions.\n\n> The paper shows that an \"informative\" CoT is beneficial. This raises a practical question: what structural properties can make a CoT informative? Have the authors investigate this?\n\nIntuitively, the CoT is informative when observing it helps to identify the underlying end-to-end input-output relationship. The exact properties needed for this to hold depend on the underlying task and hypothesis class. For example, in the case of identifying finite state automata (see Fig 2 and Appendix C), the CoT corresponds to observing the state trajectory of the automata, which helps to identify its transition function, ultimately identifying the end-to-end behavior at a much more rapid rate. However, this precise rate can depend on properties of the transition function of $h_\\star$ (e.g., a more highly-connected transition graph can be learned more quickly).\n\n> In the agnostic setting, the authors admit that CoT supervision can hurt if the hypothesis class poorly fits the CoT traces. How practical is it to design hypothesis classes that jointly fit outputs and reasoning traces?\n\nThe reason that CoT supervision can be harmful in the agnostic setting (at least for CoT-ERM) is that the agnostic setting makes no assumptions whatsoever about the data and whether it aligns at all with the hypothesis class. Thus, it is not surprising that CoT supervision is not necessarily helpful. For example, in the general case, the agnostic setting does not preclude extreme cases where the hypothesis class perfectly captures the end-to-end function but cannot express the CoT trajectory at all. Thus, in order to make sense of the agnostic setting in CoT-supervised learning, we must make structural assumptions that quantify how well-aligned the hypothesis class is to the data distribution in terms of both the CoT and the final output. This is captured by Result 3. \n\nIntuitively, to design hypothesis classes that jointly fit the outputs and reasoning traces, the reasoning traces must actually correspond to ``intermediate steps'' in the underlying model. In other words, models within the hypothesis class that fit the reasoning traces are better at predicting the final output than models that do not fit the reasoning traces.\n\n> Do the bounds extend to stochastic CoT annotations, such as those from RLHF-annotated intermediate steps or from uncertain model generations?\n\nAs stated, the results in the paper mainly apply to the deterministic setting. This is partly because we use a PAC-like framework, where hypothesis classes and function outputs are typically deterministic. However, we believe that analogous results would hold in the stochastic setting. A hint towards this is the information-theoretic analysis in Section 5 and Appendix E, where hypotheses in the CoT hypothesis class are stochastic."}, {"review_id": "a1CcG5vxWz", "reviewer": "Reviewer_T4Cn", "summary": "This paper focuses on the statistical theory of learning under CoT supervision. It introduces an abstract model of CoT supervised learning, a CoT information measure, covering both finite-cardinality hypothesis classes and infinite hypothesis classes, as well as the agnostic setting. Two types of information-theoretic lower bounds are established, along with their corresponding upper bounds.", "questions": "- The paper models CoT supervision z as an intermediate variable between input x and output y, which is a relatively general modeling approach. Are the derived conclusions applicable to general problems with intermediate supervision? Are there more specific modeling methods for CoT itself?", "limitations": "Yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths\n- S1: The paper addresses a very important problem in CoT theoretical research, providing a detailed analysis of sample complexity under specific CoT problems, which contributes to understanding the underlying mechanisms of CoT.\n- S2: The paper provides detailed derivation proofs, covering cases from simple to complex.\nWeaknesses\n- W1: The paper lacks a specific analysis of its differences from related work, making it difficult to effectively gauge its novelty. It's recommended to add a detailed comparative analysis with existing work and a specific description of the paper's innovative points.\n- W2: There's a lack of discussion on the practical applications of the paper's theory, despite some application-oriented theoretical analysis being added in Section 6. Adding insights on how the theory guides practical applications or points of application for solving real-world problems would significantly increase the paper's utility.\n- W3: Possibly due to it being a theoretical paper, it contains a large number of symbols, many of which lack detailed explanations (e.g., line 31). This makes it less user-friendly, especially for readers unfamiliar with the relevant theories.", "was_revised": true, "final_justification": "Thanks for the response, my main concerns have been addressed.", "rebuttal": "We thank the reviewer for their thoughtful and constructive feedback. We are especially grateful for the recognition of the importance of our work in advancing the theoretical understanding of chain-of-thought supervision (S1), as well as the acknowledgment of the rigor and completeness of our proofs across a range of settings (S2). We appreciate the opportunity to clarify the relationship of our contributions to prior work, further articulate their practical implications, and improve the accessibility of our exposition. Below, we address each of the reviewer's concerns in detail.\n\n---\n\n**W1: Connection to related work**\n\n> W1: The paper lacks a specific analysis of its differences from related work, making it difficult to effectively gauge its novelty. It's recommended to add a detailed comparative analysis with existing work and a specific description of the paper's innovative points.\n\nWe'd like to point you to the related work section within the discussion (Section 6.2), which discusses related work and positions our contributions within the literature. We'd also like to point you to Section 2.1 and Table 1, where we motivate how our analytical approach differs from prior approaches.\n\nThe most closely related pieces of work are Malach (2024) [citation 16] and Joshi et al. (2025) [citation 10]. \n- Malach (2024): This work studies the problem of learning autoregressive next-token prediction on CoT datasets. The core idea of this work is to express a CoT function as a composition of $T$ (a fixed number) different sequence-domain functions and learns each function independently. Since the function at each step is assumed to be independent, this enables the direct application of standard PAC learning results independently at each step. While this approach simplifies the analysis, its assumption of independently learned functions at each iteration is a notable limitation, which does not accurately reflect real-world settings and can limit sample efficiency gains from CoT supervision.\n- More recently, Joshi et al. (2025) studied a modification of Malach (2024)'s setting where the composition of sequence-domain functions is assumed to be time-invariant. Their analysis relies on bounding the *CoT error* (rather than end-to-end error) using standard PAC learning tools based on the VC dimension of the CoT loss class, noting that the CoT error provides an upper bound on the end-to-end error. The main contribution of Joshi et al. (2025) is bounding the VC dimension of the CoT loss class in terms of $T$ and the VC dimension of the iterated sequence-domain function class.\n\nIn our work, we take a different analytical approach, focusing on quantifying the information content per CoT-supervised sample. In particular, this appears through the $\\epsilon$-dependence of the rate, replacing the $1/\\epsilon$ rate of Malach (2024) and Joshi et al. (2025) with the potentially much faster $1/\\mathcal{I}^{\\mathrm{CoT}}(\\epsilon)$ rate.\n\nIn addition to the above discussion, we will use the additional content page allowed in the final version of the paper to expand on the discussion of the related work.\n\n---\n\n**W2: Discussion of practical applications of the theory developed in the paper**\n\n> W2: There's a lack of discussion on the practical applications of the paper's theory, despite some application-oriented theoretical analysis being added in Section 6. Adding insights on how the theory guides practical applications or points of application for solving real-world problems would significantly increase the paper's utility.\n\nWhile the main goal of this work is to develop a theoretical understanding of the statistical aspects of CoT-supervised learning, we agree on the importance of including a discussion of the practical applications and implications of this theory. Below, we will summarize and point to sections of the paper that pertain to these practical considerations, some of which were deferred to the appendix due to space constraints.\n\n- In Figure 2 in the main paper and Appendix C, we present simulation results where we 1) explicitly compute the CoT information, and 2) empirically evaluate the sample complexity of learning with and without CoT supervision. We show that our theory accurately predicts the gains in sample complexity.\n- Related to this question, we would like to point you to our response to review `zRps` where we discuss further extensions that enable the extension of such empirical exploration to more complex parametric model classes such as neural networks (e.g., Transformers).\n- In Appendix F.1, we study the problem of learning with mixed end-to-end and CoT supervision. This exploration is directly motivated by practical considerations: namely,  the fact that obtaining CoT-annotated examples is often costly and labor-intensive, which limits their availability. Thus, in certain practical scenarios, one might have a large number of end-to-end annotated samples together with a small number of CoT-annotated samples. The results of Appendix F.1 show that our theoretical framework allows us to analyze such scenarios.\n- In Appendix F.3, we study the important practical problem of distribution-shift and out-of-distribution generalization. We present an extension of the framework described in the main paper that enables the analysis of these problems. Our results show that CoT-supervision can enable greater domain adaptation and out-of-distribution generalization compared to end-to-end supervision. This provides a possible theoretical explanation to empirical observations on CoT-supervision improving OOD generalization (e.g., Stechly, Valmeekam, and Kambhampati, 2024; Y. Zhou et al., 2024)\n\nTo address your concern, we will include an expanded discussion of practical applications and implications in the final version of the paper.\n\n---\n\n**W3: Large number of symbols**\n\n> W3: Possibly due to it being a theoretical paper, it contains a large number of symbols, many of which lack detailed explanations (e.g., line 31). This makes it less user-friendly, especially for readers unfamiliar with the relevant theories.\n\nIndeed, due to being a theoretical paper tackling a newly developed area of analysis within statistical learning theory, some new notation and symbols are necessary. That said, we made a conscious effort to choose notation that supports clarity and readability, and we welcome any suggestions you may have for improvement.\n\nCan you clarify what you mean by your comment on line 31? We would be happy to make refinements based on your feedback. This line in the introduction introduces the central quantity in this work, the \"Chain-of-Thought Information\", which characterizes the statistical complexity of CoT-supervised learning. As this is the introduction section, our intention here is to merely give a *preview* of the main results to be developed in the paper rather than being a formal description. The formal description is provided in Definition 1 within Section 3.\n\nWe will make refinements to the presentation to include more exposition and explanation of different notation as it is introduced, as well as to provide intuition and recall/reference definitions where appropriate.\n\n---\n\nThank you again for your review and helpful feedback. We hope we were able to address your main concerns and look forward to further discussion."}]

Author rebuttal:

Meta-review: Chain-of-thought concept is very important in the current foundation model's training and inference. In this paper, CoT information is proposed, and, based on this information, a CoT supervision theory is developed. The obtained results can reflect the current development of CoT in practice, and reviewers also admit the merits of this paper. Some concerns (CoT explanations or estimation) were proposed in the initial reviews, yet the authors addressed them during the rebuttal.

Given that this topic is very timely and important, I recommend accepting this paper.
Decision: Accept (spotlight)