{"id":"4dd9e21a-15a3-4e31-ab1a-cd7536cbb3a7","arxiv_id":"2505.15927","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"With chain-of-thought supervision, the PAC sample complexity is roughly d divided by the CoT information, which can be much larger than the target error epsilon.","lead":"This paper defines a quantity called CoT information that measures how much an intermediate reasoning trace helps tell correct rules from incorrect ones, and proves that chain-of-thought supervision can reduce the number of examples needed to learn. It gives a theoretical explanation for why showing a model its work can make it learn faster, with matching lower bounds and small simulations.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The improved CoT sample-complexity rates are only certified under exact realizability of CoT labels; under noise or out-of-class CoT, the paper's own agnostic example shows CoT-ERM can fail, and Result 5 provides no matching upper bound.","rationale":"I read the paper as a theoretical contribution that defines a clean model and proves matching upper/lower bounds within that model. The proofs of Result 1, Result 2, and Result 4 are standard and correct; the CoT information measure is well-defined and the property I >= epsilon is valid. The internal logic is sound. The load-bearing assumption is the exact realizable CoT supervision in Definition 1. The reader identified exactly this as the weakest assumption, and the paper itself acknowledges the agnostic failure in Section 4.2. Because the central theorems are conditional on this assumption, and the paper is transparent about the limitation, the reader's ACCEPT verdict remains appropriate. My concern does not reveal an internal inconsistency or an error in the argument; it is a scope limitation that the reader already weighed. The proposed simulation would test whether the practical benefits survive small annotation noise, but it does not affect the validity of the theoretical statements as written.","tokens_in":37046,"tokens_out":35169,"duration_ms":306849,"concrete_test":"In the iterated linear thresholds setup of Section 6.2, run CoT-consistency and E2E-consistency with a noisy channel Q that flips each CoT token with probability p = 0, 0.01, and 0.05, keeping the final output clean. For each p, measure the sample size needed to reach end-to-end risk epsilon (e.g., epsilon = 0.1) over 500 trials. If the CoT advantage over E2E shrinks from ~5x at p=0 to within 2x at p=0.05, then the improved rates are not robust to annotation noise, confirming that the realizable assumption is load-bearing.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim that CoT supervision improves sample complexity scales as d/I rests on Definition 1, where observed CoT labels are exact deterministic outputs of the ground-truth h* in H. Result 1 and Result 2 guarantee that CoT-consistency achieves end-to-end error epsilon with m = O(log|H|/I) only under this realizability assumption. Section 4.2 shows that when the CoT component is not realizable, CoT-ERM can have zero guarantee: there are distributions with inf_h R^e2e = 0 but inf_h R^CoT = 1, so minimizing CoT risk gives no end-to-end control. Result 5 models noise but is a lower bound; it does not provide an upper bound under noise, and when any pair has infinite CoT information, sup_π E[I] = ∞, making the Fano lower bound vacuous. Thus the practical message that CoT supervision is 'never worse' and the sample-complexity gains are robust is only established for exact, in-class CoT labels, which is the least secure premise for real human-annotated CoT data.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper develops a statistical theory for learning from chain-of-thought (CoT) supervision. It models a CoT hypothesis as a function h: X → Y×Z, defines end-to-end and CoT risks, and introduces the CoT information measure I^CoT_{D,h*}(ε;H) = inf_{h: e2e-error>ε} −log P_D[h_CoT(x)=h*_CoT(x), h_e2e(x)=h*_e2e(x)]. The main results are: Result 1 gives a sample complexity bound (log|H|+log(1/δ))/I^CoT for finite classes under CoT-consistency; Result 2 extends this to infinite classes with VC(LCoT(H)); Result 3 treats the agnostic setting with CoT-ERM at rate VC(LCoT(H))/tilde-I^2; Results 4 and 5 give Le Cam and Fano lower bounds in terms of I; and Section 6 presents simulations on deterministic finite automata and iterated linear thresholds that match the predicted gains. The paper carefully distinguishes realizable and agnostic settings and includes an example showing that CoT-ERM can fail when the CoT component is not realizable.","tokens_in":37264,"tokens_out":16926,"duration_ms":144359,"significance":"If the results hold, the CoT information measure is a valuable new quantity for CoT learning: it is always at least ε, it is monotone in ε and anti-monotone in H, and it appears in both upper bounds and information-theoretic lower bounds. The proofs are based on standard PAC, Le Cam, and Fano arguments and largely appear correct. The paper improves on prior work (notably Joshi et al.) by directly linking CoT risk to end-to-end risk instead of bounding CoT risk and then using the crude inequality R^e2e ≤ R^CoT. The simulations are a strength: they compute I for nontrivial classes and empirically confirm the predicted order-of-magnitude gains. The main caveat, explicitly acknowledged in Sections 4.2 and 7.3, is that the improved rates are proved only for exactly realizable CoT labels; with noisy or out-of-class CoT, CoT-ERM can have zero guarantee and the noisy-channel lower bound (Result 5) has no matching upper bound.","major_comments":[{"comment":"The central improvement rates are proved only under exact realizability of the CoT labels (Definition 1). Section 4.2 shows that when the CoT component is not realizable, CoT-ERM can have inf_{h} R^CoT_D(h)=1 while inf_{h} R^e2e_D(h)=0, so the 'never worse' message does not extend to noisy or out-of-class CoT. The paper already acknowledges this in Section 4.2 and Section 7.3, and Result 5 provides only a lower bound under a noisy channel with no matching upper bound. Please make the realizable-setting scope explicit in the abstract and introduction, and state the missing noisy-channel upper bound as an open problem in Section 7.3.","section":"Abstract; Section 4.2; Result 5"},{"comment":"The proof states I(h*;S) = E_{h~π}[DKL(P_h^⊗m || \\bar P^⊗m)] with \\bar P = E_{h~π}P_h. This equality is not correct: the marginal of S under the prior is the mixture E_{h~π}P_h^⊗m, not the product \\bar P^⊗m. The desired bound still follows by applying convexity of KL in the second argument to write I(h*;S) ≤ E_{h1,h2~π}[DKL(P_h1^⊗m||P_h2^⊗m)] = m E_{h1,h2~π}[DKL(P_h1||P_h2)], so the theorem remains correct, but the displayed line must be corrected. In addition, the 'in particular' implication that the stated m bound yields failure probability at least 1/2 holds only when log M(ε;H,d^e2e_D) ≥ 2 log 2; please state this condition or retain the exact Fano bound.","section":"Appendix D.2 (proof of Result 5)"}],"minor_comments":[{"comment":"The abstract compares 'd/I' with 'd/ε' informally; I is a function of h*, D, ε, and H, and Result 2 has an additive +1 term and logarithmic factors. Please phrase the comparison as 'up to logarithmic factors' and note that it applies in the realizable setting.","section":"Abstract; Section 3.2"},{"comment":"The simulations use a single target hypothesis (e.g., the DFA in Figure 5) and report no error bars or standard errors; reporting averages over multiple targets and providing code would strengthen the empirical claims.","section":"Section 6, Figures 3-4"},{"comment":"The proof introduces h0 without defining it, and the displayed triangle inequality contains repeated and ambiguous terms such as d(A(S),h1) on both sides; please clean up the notation for clarity.","section":"Appendix D.1 (proof of Result 4)"},{"comment":"When any pair of hypotheses has infinite CoT information, sup_π E[I] = ∞ and the displayed implication is vacuous; please add a remark explaining this boundary case and noting that in the fully informative CoT regime (Example 2) one sample can suffice, so a vacuous lower bound is expected.","section":"Result 5"},{"comment":"The paper correctly lists missing agnostic lower bounds as an open problem; the missing upper bound under annotation noise should also be listed there, since Result 5 is only a lower bound.","section":"Section 7.3"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is a solid theoretical contribution and the central claim is defensible. However, the proof of Result 5 contains an incorrect equality in the mutual information step, and the scope of the 'never worse' message needs qualification in the abstract. These are fixable within the manuscript's scope, so I do not recommend rejection. The paper's fit for a statistics/ML journal is good, and the proposed CoT information measure is likely to be influential."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper delivers something real: a CoT information measure I that controls the epsilon-dependence of sample complexity in the realizable setting, with upper bounds of order log|H|/I and VC(LCoT)/I that beat the previous 1/epsilon rates whenever I >> epsilon. The risk-linking lemma (Lemma 2) is the key step and it is clean. The agnostic extension (Result 3) is also honest, with its own excess-risk-based information measure that can be zero when CoT is misaligned. This is a genuine advance over Joshi et al., not a repackaging.\n\nThe lower bounds are a mixed bag. The Le Cam bound (Result 4) is, as the reader notes, partly a restatement of the definition of I: the probability that a bad hypothesis is indistinguishable decays as exp(-mI) by construction. That is not a fatal flaw, since the matching upper bounds are the main contribution and the Fano bound (Result 5) is a real theorem. But calling Result 4 a lower bound that 'validates' I is overselling it slightly. The Fano bound with the noisy channel is a nice addition, and the channel-capacity calculation in the appendix is careful.\n\nThe soft spots are concentrated in what the abstract promises versus what is proven. The headline claim that CoT supervision is 'never worse' and that the gains are robust only holds under exact realizability: CoT labels are assumed to be deterministic outputs of the ground-truth h* in H. The paper is explicit about this, and Section 4.2 gives a sharp example where CoT-ERM has zero guarantee while E2E-ERM works. That is a real limitation for human-annotated traces, which are noisy and often out-of-class. Result 5 models noise but only as a lower bound; there is no matching upper bound showing CoT still helps under noise. The simulations are illustrative but thin: a single target automaton, no error bars, no code. They match the theory, which is good, but they would not convince a skeptic about practical impact.\n\nThe citation pattern is appropriate, and the related-work discussion correctly identifies the difference from Joshi et al. The writing is clear, the proofs are standard and appear correct, and the paper does not overclaim the practical implications in the body (the abstract pushes a bit harder). Overall, the central theoretical contribution holds up. The realizability caveat is real but standard for first theory, and the paper acknowledges it.\n\nThis is a paper for statistical learning theorists, and maybe for LLM practitioners who want a formal sense of when CoT traces help. It deserves a serious referee and, with revisions that strengthen the noisy-setting discussion and simulations, it would be a solid accept. I would bring it to a reading group and would cite it in my own work.","headline":"Genuinely new sample-complexity rates for CoT supervision, correct under exact realizability; the practical robustness story is thinner than the abstract suggests, but the paper deserves a serious referee.","tokens_in":37819,"tokens_out":1617,"would_cite":true,"duration_ms":16953,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q32","68T05"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that chain-of-thought supervision is never worse than input-output learning—and can be far better—with the gain set by a new quantity, the CoT information.","keywords":["chain-of-thought supervision","CoT information","sample complexity","statistical learning theory","PAC learning","hypothesis testing lower bounds","end-to-end risk","VC dimension"],"falsifier":"For a concrete CoT hypothesis class and input distribution, compute $\\mathcal{I}_{\\mathcal{D},h_\\star}^{\\mathrm{CoT}}(\\varepsilon;\\mathcal{H})$; if any learning algorithm achieves end-to-end error $\\varepsilon$ with fewer than about $\\log|\\mathcal{H}|/\\mathcal{I}_{\\mathcal{D},h_\\star}^{\\mathrm{CoT}}(\\varepsilon;\\mathcal{H})$ samples, the claim that this measure governs the $\\varepsilon$-dependence would be falsified.","tokens_in":36838,"feed_emoji":"🧠","tokens_out":11167,"duration_ms":85588,"temperature":0.7,"pith_summary":"This paper develops a statistical theory for learning from chain-of-thought supervision—training examples that include intermediate reasoning steps alongside the final answer. It introduces a quantity, the CoT information, that measures how much extra discriminative power the reasoning trace provides beyond the input-output pair. The central result is that the sample complexity to reach a target end-to-end error $\\varepsilon$ scales like $d$ divided by the CoT information, instead of the standard $d/\\varepsilon$, and the CoT information is always at least $\\varepsilon$. So CoT supervision is never information-theoretically worse than end-to-end supervision, and can be much better when traces reveal the underlying computation. Matching lower bounds argue that the CoT information is the right measure of this advantage.","feed_headline":"CoT supervision can cut sample needs dramatically","feed_subtitle":"A single measure, the CoT information, sets how many reasoning traces you need; the paper proves it.","key_machinery":"The CoT information $\\mathcal{I}_{\\mathcal{D},h_\\star}^{\\mathrm{CoT}}(\\varepsilon;\\mathcal{H})$ is the minimum, over hypotheses $h$ that disagree with the ground truth $h_\\star$ on at least an $\\varepsilon$ fraction of inputs, of the negative log probability that $h$ and $h_\\star$ produce the same output and the same chain-of-thought on a random input. It quantifies how easily reasoning traces separate hypotheses that differ in end-to-end behavior. The main upper bounds flow from a lemma that converts CoT error into end-to-end error: any proper CoT learner that reaches CoT error $\\gamma$ also reaches end-to-end error $\\varepsilon$, with $\\gamma$ tied to $\\mathcal{I}$ by the identity $\\mathcal{I} = -\\log(1-\\gamma)$. Applying this lemma to CoT consistency and CoT-ERM turns standard VC-dimension bounds into sample-complexity bounds with $1/\\mathcal{I}$ in place of $1/\\varepsilon$. The lower bounds reduce learning to binary and multi-way hypothesis testing (LeCam and Fano methods), relating total-variation and KL distances to the CoT information.","core_discovery":"The paper's central claim is that the statistical cost of learning with chain-of-thought supervision is governed by a new measure, the CoT information $\\mathcal{I}_{\\mathcal{D},h_\\star}^{\\mathrm{CoT}}(\\varepsilon;\\mathcal{H})$. For a finite CoT hypothesis class, the CoT consistency rule reaches end-to-end error $\\varepsilon$ with $m = (\\log|\\mathcal{H}| + \\log(1/\\delta)) / \\mathcal{I}_{\\mathcal{D},h_\\star}^{\\mathrm{CoT}}(\\varepsilon;\\mathcal{H})$, and since the measure is always at least $\\varepsilon$, this rate is never worse—and can be much better—than the standard $\\log|\\mathcal{H}|/\\varepsilon$. The $\\varepsilon$-dependence of the rate carries over to infinite classes via the VC dimension of the CoT loss class, and information-theoretic lower bounds show that the same $\\mathcal{I}$ controls the number of samples any algorithm must see. The paper therefore asserts that CoT information, not just the complexity of the CoT loss class, is the fundamental measure of the value of CoT supervision.","pith_inferences":["A practical diagnostic that follows implicitly: estimate the CoT information from a trace dataset and use it to decide whether collecting more CoT annotations is worth more than collecting plain input-output pairs.","The coding-theoretic viewpoint of CoT traces as redundant codewords suggests a testable design principle: maximize the diversity of traces among hypotheses that give different answers, since that is exactly what raises the CoT information.","The transfer-learning variant of the measure gives a quantitative, testable condition for length generalization in automaton-like reasoning: traces on short inputs should already distinguish hypotheses that behave differently on long inputs."],"forward_implications":["In the realizable setting, CoT supervision is information-theoretically never worse than end-to-end supervision because the CoT information is always at least $\\varepsilon$.","The speed-up can be dramatic: in the paper's deterministic-finite-automaton simulations the CoT information predicts roughly a 600-fold reduction in samples for zero error, and the experiments match.","The bound extends to infinite hypothesis classes through the VC dimension of the CoT loss class, so the improvement in $\\varepsilon$-dependence is not an artifact of finite hypothesis spaces.","In the agnostic setting the guarantee depends on an agnostic CoT information measuring how well the data distribution aligns with the class; misaligned CoT annotations can actually destroy the guarantee.","Noise in the observed traces enters the lower bound through a channel capacity factor, giving a quantitative price for imperfect CoT annotations."],"supporting_citations":[{"why":"Supplies the standard PAC rates $d/\\varepsilon$ that form the baseline the CoT rates are compared against.","marker":"(Vapnik, 1982)"},{"why":"Prior CoT learning theory whose CoT-risk bound is refined by linking CoT error to end-to-end error via the CoT information.","marker":"(Joshi et al., 2025)"},{"why":"Reduction to binary hypothesis testing used to prove that no algorithm can beat the $1/\\mathcal{I}$ dependence.","marker":"(LeCam, 1973)"},{"why":"Classic LeCam and Fano lower-bound framework on which the paper's Section 5 lower bounds rely.","marker":"(Yu, 1997)"},{"why":"Source of Fano's inequality used in the packing-based lower bound that scales with the size of the hypothesis space.","marker":"(Cover and Thomas, 2006)"}],"fun_headline_variants":["CoT information measure predicts sample complexity gain","One number, CoT information, sets the learning rate","CoT supervision's sample cost shrinks with CoT information","New statistic, CoT information, governs sample needs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The main rates assume the chain-of-thought traces in the data are exact deterministic outputs of the ground-truth hypothesis in the class, with the paper's own agnostic example showing the guarantee can vanish when that fails.","fun_headline_variants_meta":{"raw":{"variants":["CoT information measure predicts sample complexity gain","One number, CoT information, sets the learning rate","CoT supervision's sample cost shrinks with CoT information","New statistic, CoT information, governs sample needs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000926,"raw_usage":{"total_tokens":4028,"prompt_tokens":1064,"completion_tokens":2964,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":680,"completion_tokens_details":{"reasoning_tokens":2909}},"tokens_in":680,"tokens_out":2964,"duration_ms":19586,"temperature":1.0,"reasoning_tokens":2909,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T15:11:34.421843+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For a concrete CoT hypothesis class and input distribution, compute $\\mathcal{I}_{\\mathcal{D},h_\\star}^{\\mathrm{CoT}}(\\varepsilon;\\mathcal{H})$; if any learning algorithm achieves end-to-end error $\\varepsilon$ with fewer than about $\\log|\\mathcal{H}|/\\mathcal{I}_{\\mathcal{D},h_\\star}^{\\mathrm{CoT}}(\\varepsilon;\\mathcal{H})$ samples, the claim that this measure governs the $\\varepsilon$-dependence would be falsified.","supporting_citations":[],"review_version":1}