acceptodds
Under review as a conference paper at ICLR 2027

Minimax Learning from Corrupted Chain-of-Thought Supervision

Abstract

Chain-of-thought (CoT) supervision has been used to train reasoning models, but the intermediate reasoning steps and final answers provided for training can be corrupted. We study learning from corrupted outputs of a deterministic autoregressive teacher model that belongs to a finite candidate class. We establish matching upper and lower bounds on the number of prompt-level training examples needed to achieve a target clean prediction error, in the worst case over classes of a given size. For final-answer supervision, we consider Huber contamination: with probability , each answer is replaced by a draw from an arbitrary unknown distribution. We show that empirical risk minimization (ERM) is minimax optimal and characterize how the contamination probability increases the required sample size. For full-CoT supervision, tokens are corrupted independently after the teacher generates the complete sequence, and prediction error is measured by the expected fraction of incorrect tokens. When the token corruption probabilities are known and distinct clean tokens induce distinct observation distributions, maximum likelihood is minimax optimal. Its sample complexity is governed by the distinguishability of the corrupted observations, accumulated over the token positions on which candidate rollouts disagree. For unknown Huber token contamination with probability , minimizing token disagreements between candidate-generated sequences and observed sequences remains minimax optimal, without knowing either the corruption probabilities or . These results quantify the statistical cost of corrupted supervision and show that channel knowledge can sharpen guarantees for particular corruption mechanisms, although it is unnecessary for optimal worst-case performance.

Primary area:
learning theory
Keywords:
Contamination, Reasoning, Minimax Rates

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_fA4uOpenReview ↗
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 T≥1/ϵT \geq 1/\epsilon, then it is possible to have Ltok≤ϵL_{tok} \le \epsilon 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 α\alpha 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
AuthorsOpenReview ↗

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 Γ\Gamma (Theorem 5.7), and a stopping-time argument for propagating corruption, where the channel input at position tt 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=1T=1 baseline that fixes γα\gamma_\alpha, citing Massart & Nédélec (2006) and Wu, Grama & Szpankowski (2024), whose Hellinger-gap characterization of noisy online classification gives γα\gamma_\alpha 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−ρM1-\rho_M; a position-by-position margin argument likewise gives γα\gamma_\alpha with no TT. The separation 1−ρMT1-\rho_M^T comes from tensorizing over the disagreement set of each candidate, converting ρMKg(x)\rho_M^{K_g(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)}\asymp\min\{T,1/(1-\rho_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−α)2\sqrt{\alpha(1-\alpha)} of the pair-swap channel, so channel-agnostic ERM attains the lower bound with the same separation Γα,T\Gamma_{\alpha,T}. The ratio ΓMC,T/Γα,T\Gamma_{M_C,T}/\Gamma_{\alpha,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 CC is open (Remark 5.3, App. A.3).

W5 / Q1 (full-sequence and final-answer error). The reviewer is right that Ltok⋆≤εL^\star_{\mathrm{tok}}\le\varepsilon controls neither metric when T≥1/εT\ge1/\varepsilon (Remark C.2). The analysis extends:

Theorem 5.4. With Lseq⋆(g)=Pr⁡X(g(X)≠R⋆(X))≥LFA⋆(g)L^\star_{\mathrm{seq}}(g)=\Pr_X(g(X)\neq R^\star(X))\ge L^\star_{\mathrm{FA}}(g), the same estimators satisfy Pr⁡(Lseq⋆>ε)≤∣Π1:T∣(1−ε(1−ρM))n\Pr(L^\star_{\mathrm{seq}}>\varepsilon)\le|\Pi_{1:T}|(1-\varepsilon(1-\rho_M))^n for a known channel and ≤∣Π1:T∣(1−εγα)n\le|\Pi_{1:T}|(1-\varepsilon\gamma_\alpha)^n for the unknown Huber family. For both metrics the worst-case sample complexities are Θ((log⁡N+log⁡(1/δ))/(ε(1−ρM)))\Theta\big((\log N+\log(1/\delta))/(\varepsilon(1-\rho_M))\big) and Θ((log⁡N+log⁡(1/δ))/(εγα))\Theta\big((\log N+\log(1/\delta))/(\varepsilon\gamma_\alpha)\big). Proof: replace the chord step by Kg(x)≥1K_g(x)\ge1 on {g(x)≠R⋆(x)}\{g(x)\neq R^\star(x)\}; for the lower bound, use rollouts that differ only in the final token.

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)(1-\alpha)^{-(T-1)} (Proposition A.4, matching bounds). Sequence error charges one wrong token as much as TT, 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\Gamma_{\alpha,k}, a gain of order min⁡{k,1/γα}\min\{k,1/\gamma_\alpha\} over corrupted final answers alone, and Proposition C.3 shows this is tight over kk-witnessed classes. Table 1 (App. C.5) collects the separations. The experiments now report full state-sequence exact match at T=2T=2 separately from shared-position accuracy (App. D.2.2, Fig. 7).

AuthorsOpenReview ↗

Response to Reviewer fA4u (Part 2/3)

W3 / Q3 (correlated corruption). Yes. Independence enters only through BC=∏tBCt\mathrm{BC}=\prod_t\mathrm{BC}_t; replacing it by the overlap of the joint channel on the disagreement set gives the general statement.

Theorem 5.6. For a known channel W:ΣT→Δ(ΣT)W:\Sigma^T\to\Delta(\Sigma^T), let ρW(k)\rho_W(k) be the largest Bhattacharyya overlap of two inputs at Hamming distance kk and ΓW:=min⁡1≤k≤TTk(1−ρW(k))\Gamma_W:=\min_{1\le k\le T}\frac Tk(1-\rho_W(k)). The channel-aware MLE satisfies Pr⁡(Ltok⋆>ε)≤∣Π1:T∣(1−εΓW)n\Pr(L^\star_{\mathrm{tok}}>\varepsilon)\le|\Pi_{1:T}|(1-\varepsilon\Gamma_W)^n, with a matching Assouad lower bound for ε≤k⋆/(64T)\varepsilon\le k^\star/(64T). If only the per-position marginals are Huber (arbitrary correlation), tokenwise ERM satisfies Pr⁡(Ltok⋆>ε)≤∣Π1:T∣(1−c2εγα)n\Pr(L^\star_{\mathrm{tok}}>\varepsilon)\le|\Pi_{1:T}|(1-c_2\varepsilon\gamma_\alpha)^n with c2=1−e−1/2c_2=1-e^{-1/2}, which is tight.

The rates become log⁡(N/δ)/(εΓW)\log(N/\delta)/(\varepsilon\Gamma_W). Product channel: ΓW=1−ρMT\Gamma_W=1-\rho_M^T. Independent blocks, arbitrary within a block: ΓW=1−ρblkB\Gamma_W=1-\rho_{\mathrm{blk}}^B, and if independence is known across blocks, block-level ERM recovers Γα,B\Gamma_{\alpha,B} (Remark C.4). Trajectory-level contamination: ΓW=γα\Gamma_W=\gamma_\alpha, 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 S(m)S(m) be the growth function of the rollout class (the number of distinct restrictions of Π1:T\Pi_{1:T} to mm prompts). With probability 1−δ1-\delta, each estimator and error metric of Table 1 satisfies L(g^)≲(log⁡S(2n)+log⁡(1/δ))/(nΓ)L(\widehat g)\lesssim(\log S(2n)+\log(1/\delta))/(n\Gamma), with Γ\Gamma 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 d1d_1, then log⁡S(m)≤d1log⁡(2m∣Σ∣2)\log S(m)\le d_1\log(2m|\Sigma|^2), and over such classes the worst-case sample complexity for Hamming error is between c(d1+log⁡(1/δ))/(εΓ)c(d_1+\log(1/\delta))/(\varepsilon\Gamma) and C(d1log⁡(d1∣Σ∣/(εΓ))+log⁡(1/δ))/(εΓ)C(d_1\log(d_1|\Sigma|/(\varepsilon\Gamma))+\log(1/\delta))/(\varepsilon\Gamma).

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 Γ\Gamma 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 dd of the zero–one loss class, the measure of Altabaa et al. (2025), which equals VC(ΠT)\mathrm{VC}(\Pi_T) for a binary vocabulary as in Hanneke et al. (2026) and is within a log⁡∣Σ∣\log|\Sigma| factor of the Natarajan dimension (Ben-David et al., 1995): ERM achieves LFA⋆≤24(dlog⁡(2en/d)+log⁡(8/δ))/(nγα)L^\star_{\mathrm{FA}}\le24(d\log(2en/d)+\log(8/\delta))/(n\gamma_\alpha) via relative deviation inequalities (Boucheron et al., 2005), with the matching Ω((d+log⁡(1/δ))/(εγα))\Omega((d+\log(1/\delta))/(\varepsilon\gamma_\alpha)).

The obstacle the reviewer asks about is now precise (Proposition A.2, Remark A.3). A per-position argument gives a second bound O~(dˉ/(nγα))\tilde O(\bar d/(n\gamma_\alpha)) with dˉ\bar d 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 dd, composition gives only log⁡S≲dTlog⁡n\log S\lesssim dT\log n: bound (i) then recovers the Setting A rate O~(d/(nγα))\tilde O(d/(n\gamma_\alpha)) in the linear regime, and the per-position bound is larger by a factor TT. Two lower bounds mirror the two upper bounds: a shattering bound D/(εΓα,T)D/(\varepsilon\Gamma_{\alpha,T}) 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 D/(εγα)D/(\varepsilon\gamma_\alpha) 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 1/γα1/\gamma_\alpha, 1/ΓM,T1/\Gamma_{M,T}, 1/Γα,T1/\Gamma_{\alpha,T} 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.

AuthorsOpenReview ↗

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.
Reviewer_8CozOpenReview ↗
Rating
2
Confidence
2
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

This paper analyzes the sample complexity of uncovering a true hidden deterministic chain-of-thought (CoT) generator's continuations from either full CoT examples or just the last token, given a finite list of possible CoT generators. The bounds use the number of data points, the number of tokens in a CoT, the allowed prediction error, and the probability the learned predictor exceeds that error. Expected Risk Minimization is shown to be worst-case optimal at learning to predict the true CoT generator.

Critical strengths

The mathematical statement is clear, well presented, and the results are far-reaching. This is a solid theory paper.

Critical weaknesses

The motivation is quite unclear to me. I am having trouble imagining a scenario where you are trying to produce CoT by copying the CoT of another model, and you are trying to figure out which CoT generator you are copying out of a finite set of possibilities, and also for some reason you add noise token-wise to each model's CoT. Perhaps Huber contamination is sufficiently flexible (with the arbitrary corruption matrix C) that you could use it to model CoT cloning from a more accurate model to a less accurate one, or something like this?

Questions for authors

What is the motivation for the mathematical setup?

  • Why multiple possible generators that you need to distinguish between?
  • Why Huber contamination, specifically?
  • Why corrupt the CoT? (And why do so uniformly across token positions?)
  • And so on
4 comments

We thank the reviewer for the review and for the generous assessment of the results. All questions concern the motivation of the setup; we answer them in the order of the review. The General Response gives the scenario with supporting literature, Fig. 3 (App. A.1) traces it, and App. D.2.3 runs it with public DeepSeek-R1 traces.

"Producing CoT by copying the CoT of another model." This is the dominant recipe for training reasoning models (e.g. distillation): a teacher (a stronger model, or human solvers) generates traces, the traces are stored, and a student is fine-tuned on the stored corpus without further access to the teacher, as in the DeepSeek-R1 distilled models, Sky-T1, s1, and OpenThoughts. The stored traces are imperfect: answer-filtered traces keep wrong intermediate steps, the strongest open recipes apply no verification, human-written solution sets keep label errors, and stored corpora can be poisoned. Our question is how many such corrupted traces suffice to recover the teacher's clean behavior.

"Which generator out of a finite set" (why multiple generators). The set of candidates is the hypothesis class of learning theory, not a claim about the world: the student does not know the teacher and selects among the behaviors it can represent, so "figuring out which generator produced the data" is learning. A finite class enters only through log⁡∣Π∣\log|\Pi|, which plays the role of a dimension, as in the statistical theory of CoT learning (Joshi et al., 2025; Altabaa et al., 2025) and of behavior cloning (Foster et al., 2024); the worst case over classes of size NN isolates the cost of corruption from the complexity of the class. The revision extends every rate to infinite classes through the growth function of the rollout class (Theorem 5.7).

"Adding noise token-wise to each model's CoT." We do not add noise to the candidates. The noise is in the data: the teacher's trace is corrupted once, when it is stored, and each candidate is scored by how well its own clean rollout explains the stored, corrupted trace.

"Cloning from a more accurate model to a less accurate one." This is close to our setting, with one distinction. The more accurate model is the teacher, whose stored traces the student learns from, and Huber contamination models errors in those stored traces, not the gap in capacity between teacher and student. In our analysis, the teacher's behavior on the prompt distribution is representable by the student (realizability), and the student is less accurate only because it sees finitely many corrupted traces, which is what the rates quantify. A capacity gap, in which the student cannot represent the teacher, is the non-realizable case: the target becomes the best predictor in the student's class, and calibration then holds up to a factor 1/(1−2α)1/(1-2\alpha) (App. A.3).

Why Huber contamination, specifically? (1−α)I+αC(1-\alpha)I+\alpha C with arbitrary CC means exactly that each token is kept with probability at least 1−α1-\alpha and is otherwise replaced by an arbitrary, possibly token-dependent law. This is the flexibility the reviewer has in mind, the classical contamination model of robust statistics (Huber, 1964), and the weakest assumption under which the noise need not be known. α<1/2\alpha<1/2 is necessary, since swapping two values half the time makes them indistinguishable, and the lower bounds show that γα=1−2α(1−α)\gamma_\alpha=1-2\sqrt{\alpha(1-\alpha)} is its exact price.

Why corrupt the CoT, and why uniformly across positions? The CoT is corrupted because the stored trace is what the data pipeline produces and modifies (filtering, rewriting, transcription, editing). Uniform channels are for simplicity of statement; position-dependent channels follow with ρM\rho_M replaced by max⁡tρMt\max_t\rho_{M_t}, and Theorem 5.6 handles correlated corruption. Independence across positions describes corruption applied to stored traces, as opposed to errors made by the teacher during generation and consumed by its later steps. The two regimes behave oppositely for a learner with a fixed corpus: recovering the clean trajectory is horizon-free in ours (Theorem 5.4) and exponentially hard in TT under propagation (Proposition A.4), so ours is the regime in which the question has a quantitative answer.

With this setup, the answers are sharp: the whole clean trajectory can be recovered at the cost of a single corrupted token (Theorem 5.4), and corrupted intermediate steps help final-answer accuracy, by a factor that is tight in both directions, when they witness final-answer disagreements (Corollary 5.5, Proposition C.3). Section 1 now opens with the plain-language scenario, Section 3 states the Huber family in the retention form and clarifies realizability, and Section 4 is marked as a baseline. We hope this addresses the motivation concern and would be glad to clarify further.

References

  • Altabaa, A., Montasser, O., and Lafferty, J. CoT information: Improved sample complexity under chain-of-thought supervision. NeurIPS 38, 2025.
  • Foster, D. J., Block, A., and Misra, D. Is behavior cloning all you need? Understanding horizon in imitation learning. NeurIPS 37, 2024.
  • Huber, P. J. Robust estimation of a location parameter. The Annals of Mathematical Statistics, 35(1):73–101, 1964.
  • Joshi, N., Vardi, G., Block, A., Goel, S., Li, Z., Misiakiewicz, T., and Srebro, N. A theory of learning with autoregressive chain of thought. arXiv:2503.07932, 2025.

Thank you for your response.

The stored traces are imperfect: answer-filtered traces keep wrong intermediate steps, the strongest open recipes apply no verification, human-written solution sets keep label errors, and stored corpora can be poisoned.

Only the last of these (corpora poisoning, depending on the kind) bears on my concern. The difference is between errors made by the teacher model and errors introduced by corrupting the output of the teacher model. This paper addresses the second.

Below is an excerpt (with citations removed) of the new motivation section in the paper, where this same equivocation happens several times. I'll insert annotations: [T] for content about the teacher and [C] for CoT corruption.

The stored traces are corrupted after generation, and the corruption is retained: solutions filtered only by their final answer [questionably C, discussed below] regularly reach a correct answer through incorrect intermediate steps [T]; the strongest open recipes apply no verification at all, because answer filtering did not improve downstream performance [T]; human-written solution sets keep errors after quality control … [T]; and stored corpora can be poisoned cheaply [C].

The CoT is corrupted because the stored trace is what the data pipeline produces and modifies (filtering, rewriting, transcription, editing).

Filtering does not corrupt the CoT, but it could change the conditional distribution of the CoT given the question. But this paper models the teachers as deterministic, so this framework precludes thinking of filtering as CoT corruption. Rewriting, editing, and transcription are all things one does on purpose; only errors in carrying them out would be corruption. They are not "corruption" in and of themselves, so the problem at hand is not to figure out what was originally written, but to infer the composite process of the teacher's CoT generation followed by the correct rewriting. Modeling the rewriting step as independent noise would at best cause you to lose the rewriting, and at worst leave you unable to identify the teacher model (for instance, transcription might cause all the tokens to be changed).

From my review:

I am having trouble imagining a scenario where you are trying to produce CoT by copying the CoT of another model, and you are trying to figure out which CoT generator you are copying out of a finite set of possibilities, and also for some reason you add noise token-wise to each model's CoT.

I think you interpreted me as being skeptical about the disjunction of these properties of a scenario, rather than what I meant, which was the conjunction.

In summary, I think the motivation is misleading about the nature of the math, making it seem to be more applicable than it is, and the underlying applicability is low. Theory, to me, is about throwing away complexity to make it easier to reason about the core essence of a situation, or at least preserving enough to keep some property of interest invariant. But this paper seems to be using theory in a way that throws away the core structure of the problem. In all likelihood, I just feed the output of my teacher model into my student model and take a gradient update, and at this point digital processors are pretty good at not randomly flipping bits along the way.

I will keep my score at a 2.

We thank the reviewer for the careful follow-up; the distinction between errors made by the teacher [T] and corruption of its output [C] is a sharper way to state the scope than ours, and we accept the point about rewriting and transcription: carried out correctly, they are not corruption, and we will remove them from the list of sources.

We would add one observation on [T]. What determines the rate is not who made an error but whether later steps consume it. The evidence of Lightman et al. that the reviewer marks [T], solutions that reach a correct final answer through incorrect intermediate steps, is evidence of errors that were not consumed: had they propagated, the answer would be wrong. Relative to the teacher's underlying computation, such local slips are static in our sense, whereas errors that do propagate are covered by Proposition A.4, where offline learning is exponentially harder. Our model therefore covers part of [T] as well as [C], though with idealizations, chiefly independence across positions and a deterministic underlying computation, that we will state explicitly.

We agree that the motivation should make this scope precise, and we will revise it to separate [T] and [C], to state which kinds of teacher error are static and which propagate, and to present the applicability of the independent model accordingly.

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

The paper asks how much corrupted supervision is needed to be able to learn a teacher in the CoT learning setting. The setting: realizable learning on finite next-token predictor class with per-token noise applied after the clean trajectory is generated. The main contribution: a matching worst-case sample-complexity characterization under independent token corruption. Specifically:

  1. For final-answer supervision under conditional Huber contamination with α<1/2\alpha<1/2, ERM achieves the classical bounded-noise rate, written using the separation γα=1−2α(1−α)\gamma_\alpha=1-2\sqrt{\alpha(1-\alpha)}.
  2. For full trajectories corruption where the loss is the expected fraction of incorrect tokens. For a known channel with distinct rows, maximum likelihood achieves sample complexity Θ((log⁡N+log⁡(1/δ))/[ϵ(1−ρMT)])\Theta((\log N+\log(1/\delta))/[\epsilon(1-\rho_M^T)]), where ρM\rho_M is the largest Bhattacharyya overlap between distinct rows. For unknown Huber channels with α<1/2\alpha<1/2, tokenwise ERM achieves the corresponding worst-channel rate without knowing the channel or contamination level. These matching rates take a worst case over classes of size at most NN.
Critical strengths

The question makes sense, and the paper gives clean baselines toward understanding when the teacher can be identified under can noisy intermediate supervision. Two strengths that stood out to me:

  1. The lower bounds show that the resulting separation factor is necessary even for randomized, improper learners.
  2. The unknown-channel result is stronger than just showing that the corrupted loss has the correct population minimizer. It also shows that ordinary tokenwise ERM attains the optimal worst-case dependence on contamination and horizon, without estimating either the channel or its noise level.
Critical weaknesses
  1. This is a subjective matter, but I am having a hard time convincing myself that the proposed independent-token corruption model is the right way to think about noise in the CoT learning setting. The precedent for the Huber contamination model from binary classification is present, but the instantiation as independent-token corruption is not that well motivated to me. I think a better model is that in: https://arxiv.org/pdf/2606.30923, where noise in previous steps is consumed by the teacher, rather than as an independent corruption at each step. I am curious how the authors motivate the noise model considered in this paper.

  2. As an extension of the above criticism, the contribution is largely a result about noisy vector prediction, and its significance for autoregressive learning remains unclear. Once the rollout class is formed, the proofs apply to arbitrary maps from prompts to token vectors; the lower-bound models ignore their prefixes and repeat a single label. Hellinger-based characterizations of finite-class noisy prediction already appear in: https://www.proceedings.com/content/079/079017-3618open.pdf (although that work studies online classification rather than the product-channel Hamming problem here). The paper should present its contribution around the sharp product-channel specialization.

  3. Experiments: Appendix D.2.1 states that both objectives receive clean teacher-forcing prefixes. This reveals clean intermediate states that the theoretical learner never observes, and the objectives differ from the rollout-based estimators being analyzed. The authors acknowledge this, but it prevents Figure 2 from validating recovery from corrupted trajectories alone. The horizon comparison is also inconclusive: moving from T=2T=2 to T=8T=8 adds targets and clean contextual information, while the construction of matched sequences is insufficiently specified.

Questions for authors

The most useful clarifications would establish what is specific to reasoning supervision and what the experiments support. They would also separate an attainable guarantee from an unavoidable statistical cost.

  1. Can you motivate the instantiation of the Huber contamination model to this setting a bit better? (rather than taking it for granted why it should be studied).
  2. Can you give a concrete autoregressive example where the analysis establishes a benefit from corrupted intermediate states for a common final-answer prediction objective, beyond repeating noisy copies of a label?
  3. Does the horizon effect in Figure 2 survive when training uses only prompts and corrupted trajectories, with no clean-prefix access? A comparison using the same prompts and reporting accuracy on shared positions would help isolate the proposed mechanism.
4 comments
AuthorsOpenReview ↗

Response to Reviewer vUF5 (Part 1/3)

We thank the reviewer for a careful and expert review. The motivation of the corruption model (W1, Q1) is answered for all reviewers in the General Response, which grounds the model in distillation from stored reasoning traces; here we add what is specific to this review. Theorems 4.1–5.2 are unchanged; the additions below answer the questions raised.

W1: propagating noise and the model of Sriraman et al. We thank the reviewer for the pointer to Sriraman, Liu, Hsu & Block (arXiv:2606.30923), which we were not aware of and now cite in Sections 1 and 2. Their noisy-expert model is exactly the regime in which noise is consumed during generation: the noisy action is executed, and the expert's later actions are taken at the resulting states. Their offline result is that recovering the clean expert from noisy trajectories needs a number of trajectories exponential in the horizon, even when the corruption is known and the expert is deterministic: any offline learner needs n≳ηκ/((1−η)H+1ε)n\gtrsim\eta\kappa/((1-\eta)^{H+1}\varepsilon) for Hellinger error ε\varepsilon (their Proposition 15), and a likelihood estimator attains (1−η)−(H+2)log⁡∣Π∣/ε(1-\eta)^{-(H+2)}\log|\Pi|/\varepsilon up to a factor 1+ηκ1+\eta\kappa (their Theorem 6). On-policy access to the noisy expert reduces the dependence on the horizon to polynomial, and removes it under a domination condition on the noise. The revision records this dichotomy inside our framework, with matching bounds:

Proposition A.4. Under propagating corruption zt∼MC(π⋆(x,z<t),⋅)z_t\sim M_C(\pi^\star(x,z_{<t}),\cdot) with an unknown Huber channel, (i) teacher-forced ERM on the observed prefixes achieves Pr⁡(Lseq⋆>ϵ)≤∣Π∣(1−ϵ(1−α)T−1γα)n\Pr(L^\star_{\mathrm{seq}}>\epsilon)\le|\Pi|(1-\epsilon(1-\alpha)^{T-1}\gamma_\alpha)^n, and (ii) any learner, even one that knows CC, needs c (log⁡N+log⁡(1/δ))/(ϵ(1−α)T−1γα)c\,(\log N+\log(1/\delta))/(\epsilon(1-\alpha)^{T-1}\gamma_\alpha) samples in the worst case over classes of size NN.

The rate is therefore, up to universal constants, (1−α)−(T−1)(1-\alpha)^{-(T-1)} times the static rate of Theorem 5.4, which shows that recovering the entire clean trajectory from statically corrupted data is horizon-free, Θ(log⁡(N/δ)/(ϵγα))\Theta(\log(N/\delta)/(\epsilon\gamma_\alpha)). The proof of (i) replaces tensorization over positions by a stopping-time argument, since under propagation the input to the channel at position tt depends on the earlier corrupted outputs. The two regimes are not two parametrizations of one phenomenon: a learner with a fixed corpus is in ours, and the title question has a quantitative answer only there. They also call for different estimators: free-running rollout scoring (Theorem 5.1) in the static regime, and teacher forcing on the stored prefixes, i.e., standard SFT, in the propagating one. Real corpora mix both kinds of error (General Response; Fig. 3); our results give the rates for the static component and show that the propagating component cannot be averaged out by more offline data.

W1: Huber per token. The family {(1−α)I+αC}\{(1-\alpha)I+\alpha C\} is exactly the set of channels that retain each clean token with probability at least 1−α1-\alpha and otherwise replace it by an arbitrary, possibly token-dependent law (the diagonal-dominance condition of noisy-label learning; now stated in Section 3). α<1/2\alpha<1/2 is necessary, and Theorem 5.2 shows that γα\gamma_\alpha is the exact price. Independence across positions enters only one tensorization step; Theorem 5.6 covers an arbitrary known channel acting on the whole trajectory and arbitrary correlation with Huber marginals (details in the fA4u thread).

AuthorsOpenReview ↗

Response to Reviewer vUF5 (Part 2/3)

W2 / Q2: what is autoregressive-specific; the Hellinger-gap characterization. We agree with the diagnosis and adopted the suggested framing: Section 1 is organized around the product-channel characterization, Section 4 is presented as a baseline, and we now cite Wu, Grama & Szpankowski (NeurIPS 2024), whose Hellinger-gap characterization of noisy online classification gives exactly γα\gamma_\alpha for Bernoulli uncertainty sets; Section 4 is its batch counterpart. What a gap characterization does not give is the content of Section 5: a gap is governed by the closest pair of outputs and yields 1−ρM1-\rho_M for trajectories, whereas under the Hamming-normalized risk the separation is 1−ρMT1-\rho_M^T, obtained by tensorizing over the disagreement set and linearizing by convexity (Lemma C.1), with a matching lower bound. The separation is loss-graded: 1−ρMT1-\rho_M^T for Hamming error, 1−ρM1-\rho_M for full-sequence error, 1−ρMk1-\rho_M^k for final-answer error under kk-witnessing (Table 1, App. C.5), each with matching rates.

Once the rollout class is formed, Theorems 5.1–5.7 are statements about offline corrupted vector prediction, and the paper now says so. The autoregressive structure enters in three places (Section 5.3, App. A.2): (i) estimation must be rollout-based because the clean contexts are latent; (ii) the lower-bound rollouts are produced by candidates that differ only in their first state and then apply a shared injective update, so 1−ρMT1-\rho_M^T is the signature of early forks, and Theorem 5.7 shows that for such infinite classes the redundancy survives with matching rates; (iii) the following answer to Q2.

Q2: a concrete final-answer benefit. Call final-answer disagreements kk-witnessed if gT(x)≠h⋆(x)g_T(x)\neq h^\star(x) implies Kg(x)≥kK_g(x)\ge k, i.e., candidates that disagree on the answer disagree on at least kk intermediate states. Classes that differ in how they read the prompt and then run the same injective computation are TT-witnessed; so are modular counters πθ(x,s)=slast+θ mod p\pi_\theta(x,s)=s_{\mathrm{last}}+\theta \bmod p, whose rollouts differ at every position although no state copies the answer.

Corollary 5.5 and Proposition C.3. Under kk-witnessing, the final-answer error of the estimators satisfies Pr⁡(LFA⋆>ε)≤∣Π1:T∣(1−εΓα,k)n\Pr(L^\star_{\mathrm{FA}}>\varepsilon)\le|\Pi_{1:T}|(1-\varepsilon\Gamma_{\alpha,k})^n (and ΓM,k\Gamma_{M,k} for a known channel), and over kk-witnessed classes of cardinality at most NN this is tight: the worst-case rate is Θ((log⁡N+log⁡(1/δ))/(εΓα,k))\Theta\big((\log N+\log(1/\delta))/(\varepsilon\Gamma_{\alpha,k})\big). Corrupted final answers alone need clog⁡(N/δ)/(εγα)c\log(N/\delta)/(\varepsilon\gamma_\alpha) by Theorem 4.1.

Since Γα,k/γα≍min⁡{k,1/γα}\Gamma_{\alpha,k}/\gamma_\alpha\asymp\min\{k,1/\gamma_\alpha\}, the gain is of that order in both directions (about 7.9×7.9\times for k=8k=8 at α=0.45\alpha=0.45), and the contamination penalty disappears for k≳1/γαk\gtrsim1/\gamma_\alpha; with k=1k=1 there is no gain (Remark C.2). The statement characterizes how much corrupted intermediate states help final-answer prediction: by the factor min⁡{k,1/γα}\min\{k,1/\gamma_\alpha\} when they witness final-answer disagreements.

AuthorsOpenReview ↗

Response to Reviewer vUF5 (Part 3/3)

W3 / Q3: experiments. We agree that clean-prefix teacher forcing gives the learner contexts that the observation model excludes, and that the T=2T=2 versus T=8T=8 comparison was confounded. The controlled finite-class simulations, which instantiate estimators (13) and (17) exactly and reproduce the 1/γα1/\gamma_\alpha, 1/ΓM,T1/\Gamma_{M,T}, 1/Γα,T1/\Gamma_{\alpha,T} scalings, are now Fig. 2 in the main text. The clean-prefix LLM runs of the original Figure 2 are relabeled qualitative and moved to App. D.2.1 (Fig. 4). We ran the experiments the reviewer asked for.

No clean-prefix access, matched horizons (App. D.2.2, Table 2, Fig. 5). Qwen3-4B, 1,000 training and 72 held-out problems. Each problem has one fixed length-8 reference, and the T=2T=2 target is its first two positions, so both horizons share prompts, references, and the corruption of positions 1–2. Training sees only prompts and stored corrupted trajectories, and we report free-running accuracy on positions 1–2 (three training seeds × two channel seeds, paired bootstrap). In all six noisy conditions the mean T8−T2T8-T2 difference is positive (+3.0 to +5.8 points), so the horizon trend survives the removal of clean prefixes. However, the noiseless condition shows a similar gain (+4.4), and only one interval excludes zero (pair-swap, α=0.45\alpha=0.45, uncorrected). At α=0\alpha=0 the theory predicts no horizon effect for normalized Hamming error, and longer targets change supervision and optimization through shared parameters, so these runs do not isolate channel redundancy.

Suffix controls (Table 4). To isolate the information in the suffix, we compared the T=8T=8 model trained on the informative corrupted suffix with models whose positions 3–8 are uniformly random tokens or are excluded from the loss, which keeps the number of positions fixed. The informative suffix is better in all four cells (+2.0 and +5.2 for the uniform channel, +5.3 and +3.9 for pair-swap), but every interval includes zero; with 72 test problems the half-widths are about 6 points.

Known channel and channel geometry (Table 3, Fig. 6). Under the uniform channel at α=0.45\alpha=0.45, forward correction improves on plain cross-entropy by 11.0 and 11.7 points at T=2T=2 and T=8T=8 (paired 95% intervals [3.9, 18.3] and [4.4, 19.8]). Under plain cross-entropy, pair-swap corruption is not harder than uniform corruption (23.6 vs. 24.1 at T=2T=2), unlike in the clean-prefix runs of the original Figure 2, although Remark 5.3 predicts the uniform channel to be easier; the corrected objective does realize this gap (35.1 under the uniform channel). Since tokenwise ERM and maximum likelihood coincide for symmetric channels in the finite-class analysis, we attribute the difference between plain and corrected cross-entropy to neural training, consistent with forward loss correction (Patrini et al., 2017).

Real-teacher distillation (App. D.2.3, Tables 5–8, Figs. 8–11). We instantiated the scenario of the General Response: Qwen3-1.7B fine-tuned on 1,000 public DeepSeek-R1 traces (Bespoke-Stratos-17k), with the reasoning perturbed after generation, leaving the released solution, the teacher's own answer, unchanged; final answers on 128 GSM8K and 128 numerical MATH-500 problems, three training seeds. At the frozen 2,048-token budget, replacing digits with probability 20% or 50% changed accuracy by at most 1.6 points, whereas shuffling the reasoning paragraphs lowered it by 25.0 and 22.4points. Because many outputs reach the length limit, we re-evaluated all three seeds at 4,096 tokens post hoc: 50% digit replacement then lowers MATH accuracy by 6.5 points, a cost at fixed nn that the static analysis predicts qualitatively, and shuffling lowers accuracy by 26.3 and 31.5 points; the MATH length-limit rate remains 30% for unmodified and 60% for shuffled traces. The structural effect is far larger than the content effect at both budgets, consistent with Li et al. (2025). Fine-tuning on 1,000 traces does not reach the untuned, reasoning-trained student on MATH at either budget, so we compare conditions within the same pipeline.

Summary of changes. Section 1 rewritten around distillation from stored traces (Fig. 3, App. A.1) and the static/propagating dichotomy; Section 4 as a baseline; Theorem 5.4, Corollary 5.5 with Proposition C.3, Theorem 5.7; Proposition A.4; Wu et al. (2024) and Sriraman et al. (2026) discussed; Fig. 2 in the main text; App. D.2.2–D.2.3. We hope these address the concerns and would be grateful if the reviewer would reconsider the assessment.

References

  • Bespoke Labs. Bespoke-Stratos-17k. Dataset, 2025. https://huggingface.co/datasets/bespokelabs/Bespoke-Stratos-17k
  • Li, D., Cao, S., Griggs, T., Liu, S., Mo, X., Patil, S. G., Zaharia, M., Gonzalez, J. E., and Stoica, I. LLMs can easily learn to reason from demonstrations: Structure, not content, is what matters! Findings of EMNLP, 2025. arXiv:2502.07374.
  • Patrini, G., Rozza, A., Menon, A. K., Nock, R., and Qu, L. Making deep neural networks robust to label noise: A loss correction approach. CVPR, 2017.
  • Sriraman, V., Liu, P., Hsu, D., and Block, A. Behavior cloning is not all you need: The optimality of on-policy distillation for noisy expert feedback. arXiv:2606.30923, 2026.
  • Wu, C., Grama, A., and Szpankowski, W. Information-theoretic limits of online classification with noisy labels. NeurIPS 37, 2024.

Comments on the paper

3 comments
AuthorsOpenReview ↗

General Response(1/3)

We thank all reviewers. This response summarizes (1) what changed in the revision, (2) our answer to the question on motivation that all three reviews raise, and (3) the new experiments. Technical points are answered in the individual threads.

1. What changed

Every addition answers a specific question in the reviews and is marked in blue in the revised PDF. The new results build on the same framework, so their proofs are short and can be checked against the existing ones, and together they complete the characterization: every row of the summary table (Table 1, App. C.5) now has matching rates, for finite classes and for infinite classes whose rollouts fork early.

ChangeWhereAnswers
Motivation: distillation from stored reasoning traces, with evidence; pipeline figureSec. 1; App. A.1, Fig. 3all reviewers
Section 4 presented as a baseline (Massart & Nédélec, 2006; Wu et al., 2024)Sec. 1, Sec. 4fA4u W1, vUF5 W2
Full-sequence and final-answer rates (horizon-free)Thm. 5.4fA4u Q1 / W5
When corrupted intermediate steps help final-answer accuracy, tight in both directionsCor. 5.5, Prop. C.3vUF5 Q2
Correlated offline corruptionThm. 5.6, Rem. C.4fA4u Q3
Infinite classes (growth function of the rollout class; matching rates for early-forking classes)Thm. 5.7; Props. A.1–A.2, Rem. A.3fA4u Q4
Propagating corruption, matching upper and lower boundsProp. A.4vUF5 W1 / Q1
Experiments without clean prefixes; real-teacher distillationApp. D.2.2–D.2.3vUF5 W3 / Q3, fA4u W6
Controlled finite-class simulations moved to the main textFig. 2fA4u W6

2. Motivation

The scenario of distillation. The dominant recipe for training reasoning models is to generate traces with a teacher (a stronger model, or human solvers), store them, and fine-tune a student on the corpus, as in the DeepSeek-R1 distilled models, Sky-T1, s1, and OpenThoughts. The student holds a fixed corpus and has no further access to the teacher. Our question, how many corrupted prompt–trace pairs suffice to recover the teacher's clean behavior, is the statistical question this recipe raises. Fig. 3 (App. A.1) traces the distillation pipeline and marks where each kind of error enters.

Stored traces are corrupted, and the corruption is retained.

  • Filtering by the final answer admits traces with wrong intermediate steps: models trained with outcome supervision often reach correct answers through incorrect reasoning, and answer-filtered solutions are what is used for SFT (Lightman et al., 2024).
  • The strongest open recipes apply no verification, because none of the tested answer-filtering methods improved downstream performance (Guha et al., 2026).
  • Human-written solution sets keep errors after quality control: under 2% at release for GSM8K (Cobbe et al., 2021), about 5% of the test set on re-annotation (Vendrow et al., 2025). This is Setting A with a prompt-dependent QQ.
  • Stored corpora can be poisoned cheaply (Carlini et al., 2024; Wan et al., 2023), including CoT demonstrations (Xiang et al., 2024); an adversary editing a corpus chooses an arbitrary replacement law, which the Huber matrix CC allows.
  • Corruption is also injected into stored traces deliberately, for instance by replacing their digits at random (Li et al., 2025).

Such corpora mix two kinds of error: corruption applied to the stored trace after generation, and errors made by the teacher during sampling, which its later steps consume. Setting B is the first kind in its simplest form.

Finite class (8Coz), and the teacher being stronger than the student. The finite class is the hypothesis class of learning theory, not a claim about the world: the student does not know the teacher and selects among the behaviors it can represent. A finite class enters only through log⁡∣Π∣\log|\Pi|, as in the statistical theory of CoT learning (Joshi et al., 2025; Altabaa et al., 2025; Hanneke et al., 2026) and of behavior cloning (Foster et al., 2024); infinite classes are treated in Thm. 5.7. Deterministic teachers under realizability are the standard setting of this literature. Realizability concerns the teacher's behavior on the prompt distribution, not its architecture: a stronger teacher is realizable when a student can match its traces in the target domain, and otherwise the target is a best-in-class predictor (App. A.3).

Huber, and independence (8Coz, fA4u). The family (1−α)I+αC(1-\alpha)I+\alpha C is exactly the set of channels that retain each clean token with probability at least 1−α1-\alpha and otherwise replace it by an arbitrary, possibly token-dependent law: the weakest assumption under which the noise need not be known. α<1/2\alpha<1/2 is necessary, and the lower bounds show that γα\gamma_\alpha is its exact price. Independence is used in one tensorization step only; Thm. 5.6 treats an arbitrary known channel on the whole trajectory and arbitrary correlation with Huber marginals.

AuthorsOpenReview ↗

General Response(2/3)

Static versus propagating noise (vUF5, fA4u). When the noise is produced by the generator and consumed by later steps, offline learning toward the clean expert needs a number of trajectories exponential in the horizon (Sriraman et al., 2026). Prop. A.4 records this dichotomy inside our framework with matching bounds: the rate is Θ((log⁡N+log⁡(1/δ))/(ϵ(1−α)T−1γα))\Theta\big((\log N+\log(1/\delta))/(\epsilon(1-\alpha)^{T-1}\gamma_\alpha)\big), attained by teacher forcing on the observed prefixes, i.e., up to universal constants (1−α)−(T−1)(1-\alpha)^{-(T-1)} times the horizon-free static rate of Thm. 5.4. In the static regime corruption is not free, but it costs a multiplicative factor in the number of traces; a learner with a fixed corpus is in this regime, and the title question has a quantitative answer only there.

3. Experiments (App. D.2.2–D.2.3)

  • Without clean prefixes (Qwen3-4B; 1,000 training and 72 held-out problems; T=2T=2 targets are prefixes of the same T=8T=8 references). The mean gain of T=8T=8 over T=2T=2 on the shared positions is positive in all six noisy conditions (+3.0 to +5.8 points), but the noiseless condition shows a similar gain (+4.4) and most paired intervals include zero, so these runs do not isolate channel redundancy; the direct test of the predicted scalings remains the controlled simulations (Fig. 2). Suffix controls that keep the number of positions fixed (informative vs. random or masked suffix) are positive in all four cells but underpowered, with every interval including zero (Table 4). With a known uniform channel at α=0.45\alpha=0.45, forward correction improves on plain cross-entropy by 11.0 and 11.7 points; under plain cross-entropy pair-swap corruption is not harder than uniform corruption, whereas the corrected objective realizes the gap predicted by Remark 5.3, so we attribute the difference to neural training rather than to our finite-class rates.
  • Real teacher traces (Qwen3-1.7B fine-tuned on 1,000 public DeepSeek-R1 traces from Bespoke-Stratos-17k; digits replaced or paragraphs shuffled in the reasoning, leaving the released solution, the teacher's own answer, unchanged). At the frozen 2,048-token budget, digit replacement changes final-answer accuracy by at most 1.6 points, and shuffling lowers it by 25.0 (GSM8K) and 22.4 (MATH) points. In a post-hoc 4,096-token re-evaluation of all three seeds, 50% digit replacement lowers MATH accuracy by 6.5 points, a cost at fixed nn that the static analysis predicts qualitatively, and shuffling lowers accuracy by 26.3 and 31.5 points. Fine-tuning on 1,000 traces does not reach the untuned, reasoning-trained student on MATH, so we compare conditions within the same pipeline.
AuthorsOpenReview ↗

General Response(3/3)

References

  • Altabaa, A., Montasser, O., and Lafferty, J. CoT information: Improved sample complexity under chain-of-thought supervision. NeurIPS 38, 2025.
  • Bespoke Labs. Bespoke-Stratos-17k. Dataset, 2025. https://huggingface.co/datasets/bespokelabs/Bespoke-Stratos-17k
  • Carlini, N., Jagielski, M., Choquette-Choo, C. A., Paleka, D., Pearce, W., Anderson, H., Terzis, A., Thomas, K., and Tramèr, F. Poisoning web-scale training datasets is practical. IEEE Symposium on Security and Privacy, 2024.
  • Cobbe, K., Kosaraju, V., Bavarian, M., Chen, M., Jun, H., Kaiser, L., Plappert, M., Tworek, J., Hilton, J., Nakano, R., Hesse, C., and Schulman, J. Training verifiers to solve math word problems. arXiv:2110.14168, 2021.
  • DeepSeek-AI. DeepSeek-R1: Incentivizing reasoning capability in LLMs via reinforcement learning. arXiv:2501.12948, 2025.
  • Foster, D. J., Block, A., and Misra, D. Is behavior cloning all you need? Understanding horizon in imitation learning. NeurIPS 37, 2024.
  • Guha, E., Marten, R., Keh, S., Raoof, N., Smyrnis, G., et al. OpenThoughts: Data recipes for reasoning models. ICLR, 2026. arXiv:2506.04178.
  • Hanneke, S., Mehalel, I., and Moran, S. Sample complexity of autoregressive reasoning: Chain-of-thought vs. end-to-end. arXiv:2604.12013, 2026.
  • Joshi, N., Vardi, G., Block, A., Goel, S., Li, Z., Misiakiewicz, T., and Srebro, N. A theory of learning with autoregressive chain of thought. arXiv:2503.07932, 2025.
  • Li, D., Cao, S., Griggs, T., Liu, S., Mo, X., Patil, S. G., Zaharia, M., Gonzalez, J. E., and Stoica, I. LLMs can easily learn to reason from demonstrations: Structure, not content, is what matters! Findings of EMNLP, 2025. arXiv:2502.07374.
  • Lightman, H., Kosaraju, V., Burda, Y., Edwards, H., Baker, B., Lee, T., Leike, J., Schulman, J., Sutskever, I., and Cobbe, K. Let's verify step by step. ICLR, 2024.
  • Massart, P. and Nédélec, É. Risk bounds for statistical learning. The Annals of Statistics, 34(5):2326–2366, 2006.
  • Muennighoff, N., Yang, Z., Shi, W., Li, X. L., Fei-Fei, L., Hajishirzi, H., Zettlemoyer, L., Liang, P., Candès, E., and Hashimoto, T. s1: Simple test-time scaling. arXiv:2501.19393, 2025.
  • NovaSky Team. Sky-T1: Train your own O1 preview model within USD 450. Blog post, 2025. https://novasky-ai.github.io/posts/sky-t1/
  • Sriraman, V., Liu, P., Hsu, D., and Block, A. Behavior cloning is not all you need: The optimality of on-policy distillation for noisy expert feedback. arXiv:2606.30923, 2026.
  • Vendrow, J., Vendrow, E., Beery, S., and Madry, A. Do large language model benchmarks test reliability? arXiv:2502.03461, 2025.
  • Wan, A., Wallace, E., Shen, S., and Klein, D. Poisoning language models during instruction tuning. ICML, 2023.
  • Wu, C., Grama, A., and Szpankowski, W. Information-theoretic limits of online classification with noisy labels. NeurIPS 37, 2024.
  • Xiang, Z., Jiang, F., Xiong, Z., Ramasubramanian, B., Poovendran, R., and Li, B. BadChain: Backdoor chain-of-thought prompting for large language models. ICLR, 2024.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.