- Rating
- 2
- Confidence
- 4
- Informativeness
- 1
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
This paper studies learning with CoT supervision under corrupted observations. They consider two cases: independent corruption across tokens with a known channel, or indepdent corruption with an unknown Huber-type channel. The paper establishes minimax rates using MLE analysis and Massart-type analysis.
Critical strengths
- The writing and presentation is generally quite clear. The paper is well-presented.
- The question of CoT learning under corrupted observations is interesting and well-motivated. It addresses a gap in the literature, to my knowledge.
- Soundness and correctness are solid. The proofs appear to be correct and are generally organized and clearly written (Checked primarily by an AI agent. I also checked certain key steps.).
Critical weaknesses
My main concerns are about the level of novel technical contribution, and about the strength of some of the key assumptions and the formal setting (in particular, the metric being analyzed).
- The final-answer learning under contamination (Setting A; Section 4) reproduces classical noisy-PAC results. This is partially acknowledged (Remark 4.3 mentions Massart-type results and says this is a baseline rather than a new rate), but this should be acknowledged more clearly earlier on. For example, the "final-answer" result of setting A is mentioned under the contributions list.
- While correct, the analysis underlying the main result are relatively standard. For example, Thm5.1(i) is a standard MLE analysis and (ii) is per-token Massart calibration.
- The assumption that tokens are corrupted independently offline after the teacher generates them is unrealistic and too idealized.
- The analysis is limited to finite classes only.
- The prediction error control is for expected fraction of incorrect tokens rather than by the full-sequence accuracy, which doesn't provide a guarantee on the full sequence accuracy or final-answer accuracy. In the extreme case, if , then it is possible to have while the full-sequence or final answer error is 100%. This deviates from the guarantees of prior work in this area which control the full-sequence accuracy (sometimes called "CoT error") or the final-answer accuracy (sometimes "end-to-end error").
- The experiments only show that accuracy falls as rises, not a particular correspondence with the rates established in the theoretical analysis.
Questions for authors
- what is the minimax rate for full-sequence accuracy or final answer accuracy? Can your analysis extend to cover this setting?
- which steps in the proofs of theorems 5.1 and 5.2 do the authors consider new contributions? as mentioned above, the "known-channel" bound looks like standard Bhattacharyya MLE analysis over a finite class (with tensorization) and the unknown channel bound looks like massart-style analysis applied to each token.
- Can the analysis be extended to the case where the corruption channel is not independent across tokens, and if so what do the rates become?
- can the analysis be extended to infinite classes? what is the main obstacle to extending to, e.g., VC classes?
5 comments
Response to Reviewer fA4u (Part 2/3)
W3 / Q3 (correlated corruption). Yes. Independence enters only through ; replacing it by the overlap of the joint channel on the disagreement set gives the general statement.
Theorem 5.6. For a known channel , let be the largest Bhattacharyya overlap of two inputs at Hamming distance and . The channel-aware MLE satisfies , with a matching Assouad lower bound for . If only the per-position marginals are Huber (arbitrary correlation), tokenwise ERM satisfies with , which is tight.
The rates become . Product channel: . Independent blocks, arbitrary within a block: , and if independence is known across blocks, block-level ERM recovers (Remark C.4). Trajectory-level contamination: , no redundancy. Redundancy is thus a property of independence, not of the marginals. This is also our answer on the independence assumption: it is the first-order model of digit replacement and similar post-hoc noise, it yields exact constants, and Theorem 5.6 states what changes when it fails. The extreme form of dependence, noise consumed by the generator, is where polynomial offline rates end (Proposition A.4).
W4 / Q4 (infinite classes; the obstacle). The main text now contains the answer:
Theorem 5.7. Let be the growth function of the rollout class (the number of distinct restrictions of to prompts). With probability , each estimator and error metric of Table 1 satisfies , with the separation of the corresponding row. If candidates differ only in their first state and then apply a shared injective update, and the first-state class has Natarajan dimension , then , and over such classes the worst-case sample complexity for Hamming error is between and .
The upper bound is a double-sample symmetrization over restrictions of the rollout class; conditionally on the prompts, the corruption within each prompt keeps its structure, which is why the separation survives (Proposition A.2). The lower bound is the construction of Theorem 5.2, whose hard class forks early, so channel redundancy survives for such infinite classes. In Setting A the corresponding result (Proposition A.1) uses the VC dimension of the zero–one loss class, the measure of Altabaa et al. (2025), which equals for a binary vocabulary as in Hanneke et al. (2026) and is within a factor of the Natarajan dimension (Ben-David et al., 1995): ERM achieves via relative deviation inequalities (Boucheron et al., 2005), with the matching .
The obstacle the reviewer asks about is now precise (Proposition A.2, Remark A.3). A per-position argument gives a second bound with the dimension of the hardest position, whose loss class is the end-to-end class, and the guarantee is the minimum of the two. For a generic base class of Natarajan dimension , composition gives only : bound (i) then recovers the Setting A rate in the linear regime, and the per-position bound is larger by a factor . Two lower bounds mirror the two upper bounds: a shattering bound and a Fano bound in the local packing number of the rollout class, which shows that when every position is a separate parameter the rate is with no redundancy. Clean CoT theory reaches the base dimension by using each clean prefix as a labeled example (Hanneke et al., 2026; Li, 2026); under corruption the prefixes are latent. What remains open is the growth function of the rollout classes induced by natural base classes, which decides whether redundancy survives for them.
W6 (experiments). The direct test of the rates is the controlled finite-class simulations, now Fig. 2 in the main text: they instantiate estimators (13) and (17) and reproduce the , , scalings up to constants. The LLM experiments are qualitative and labeled so; the new runs without clean prefixes and with real teacher traces are summarized in the General Response and reported in full in App. D.2.2–D.2.3.
Response to Reviewer fA4u (Part 3/3)
Summary of changes. Contributions reorganized around the characterization, with Section 4 as the baseline; Theorems 5.4, 5.6, 5.7 and Corollary 5.5; Propositions A.1, A.2, A.4, C.3 and Remarks A.3, C.4; Fig. 2 in the main text; App. D.2.2–D.2.3. Revised text is in blue. We hope these address the concerns and would be grateful if the reviewer would reconsider the assessment.
References
- Altabaa, A., Montasser, O., and Lafferty, J. CoT information: Improved sample complexity under chain-of-thought supervision. NeurIPS 38, 2025.
- Ben-David, S., Cesa-Bianchi, N., Haussler, D., and Long, P. M. Characterizations of learnability for classes of {0, …, n}-valued functions. Journal of Computer and System Sciences, 50(1):74–86, 1995.
- Boucheron, S., Bousquet, O., and Lugosi, G. Theory of classification: A survey of some recent advances. ESAIM: Probability and Statistics, 9:323–375, 2005.
- Foster, D. J., Block, A., and Misra, D. Is behavior cloning all you need? Understanding horizon in imitation learning. NeurIPS 37, 2024.
- Hanneke, S., Mehalel, I., and Moran, S. Sample complexity of autoregressive reasoning: Chain-of-thought vs. end-to-end. arXiv:2604.12013, 2026.
- Li, Z. The optimal sample complexity of learning autoregressive chain-of-thought. arXiv:2607.07423, 2026.
- Massart, P. and Nédélec, É. Risk bounds for statistical learning. The Annals of Statistics, 34(5):2326–2366, 2006.
- Wu, C., Grama, A., and Szpankowski, W. Information-theoretic limits of online classification with noisy labels. NeurIPS 37, 2024.
Response to Reviewer fA4u (Part 1/3)
We thank the reviewer for the careful reading, including the verification of the proofs, and for questions precise enough to be answered with theorems. Theorems 4.1–5.2 and their proofs are unchanged. Theorems 5.4 and 5.6, Corollary 5.5, and Proposition C.3 extend the same framework, and two arguments go beyond what the finite-class analysis needed: a double-sample symmetrization that keeps the within-prompt structure of the corruption, so that infinite classes retain the separation Γ (Theorem 5.7), and a stopping-time argument for propagating corruption, where the channel input at position t depends on earlier corrupted outputs (Proposition A.4). With them every row of the summary table (Table 1, App. C.5) has matching rates. The realism of the corruption model (W3) is also addressed in the General Response.
W1 (Setting A is classical). Agreed. It is removed from the contributions and presented as the T=1 baseline that fixes γα, citing Massart & Nédélec (2006) and Wu, Grama & Szpankowski (2024), whose Hellinger-gap characterization of noisy online classification gives γα in the Bernoulli case.
W2 / Q2 (what is new in Theorems 5.1–5.2). We agree that the individual tools (a Bhattacharyya analysis of a finite-class MLE, Assouad/Le Cam, a Chernoff bound on a calibrated margin) are classical, and the revision says so. The contribution is the characterization, and two of its features are not delivered by a routine application. (i) The separation. The gap/Massart viewpoint is governed by the worst pair of outputs, which for trajectories is a pair at Hamming distance one and gives 1−ρM; a position-by-position margin argument likewise gives γα with no T. The separation 1−ρMT comes from tensorizing over the disagreement set of each candidate, converting ρMKg(x) into a quantity linear in the Hamming risk by convexity (Lemma C.1, the step where the metric enters), and a lower-bound family whose rollouts disagree at every position. The gain ≍min{T,1/(1−ρM)} is the redundancy phenomenon of the paper. (ii) Uniformity. The optimal Chernoff tilt of the per-position margin yields exactly the Bhattacharyya overlap 2α(1−α) of the pair-swap channel, so channel-agnostic ERM attains the lower bound with the same separation Γα,T. The ratio ΓMC,T/Γα,T of the two guarantees then bounds the price of not knowing the channel; it is a ratio of upper bounds, and whether ERM adapts to a particular C is open (Remark 5.3, App. A.3).
W5 / Q1 (full-sequence and final-answer error). The reviewer is right that Ltok⋆≤ε controls neither metric when T≥1/ε (Remark C.2). The analysis extends:
Consequently, offline corruption introduces no horizon dependence for sequence error, the analogue of the horizon-free behavior-cloning rate of Foster et al. (2024) for clean data, in contrast to propagating corruption, which costs (1−α)−(T−1) (Proposition A.4, matching bounds). Sequence error charges one wrong token as much as T, so the Hamming risk is the metric in which disagreement sets are visible. Final-answer error inherits the redundancy when intermediate states witness final-answer disagreements: Corollary 5.5 gives the separation Γα,k, a gain of order min{k,1/γα} over corrupted final answers alone, and Proposition C.3 shows this is tight over k-witnessed classes. Table 1 (App. C.5) collects the separations. The experiments now report full state-sequence exact match at T=2 separately from shared-position accuracy (App. D.2.2, Fig. 7).