REVIEW 2 major objections 7 minor 14 references
Learning full Chain-of-Thought traces costs no extra samples
Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →
T0 review · glm-5.2
2026-07-09 11:17 UTC pith:6XQ2NJX3
load-bearing objection Solid result: exact-trace CoT learning has no sample-complexity penalty over local next-token learning, proved via a new parity dimension invariant. the 2 major comments →
The Optimal Sample Complexity of Learning Autoregressive Chain-of-Thought
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
Core claim
The central object is parity dimension (ParDim), a rollout-stable complexity measure defined via even pseudo-cubes — collections of functions whose coordinate-deletion marginals vanish over the field F₂. ParDim sits between one-inclusion density and DS dimension (μ_H(n) ≤ ParDim(H) ≤ DSdim(H)), and the key structural theorem is that ParDim does not increase under autoregressive rollout: ParDim(Roll_halt(H)) ≤ ParDim(H). This invariance, combined with the density bound, yields the main result that exact-trace PAC learning of autoregressive Chain-of-Thought requires only O((DSdim(H) + log(1/δ))/ε) samples, matching the lower bound from one-step stopping. The proof of rollout-stability uses a '
What carries the argument
Parity dimension (ParDim) is the load-bearing invariant. It is defined via even pseudo-cubes: a finite restriction H'|D is an even pseudo-cube if there exists a nonzero F₂-vector whose sum over every coordinate-deletion fiber is zero. The proof chain is: (1) absence of large even pseudo-cubes forces low-coordinate spanning on finite restrictions (a linear-algebra argument over F₂), which bounds one-inclusion density; (2) a partition-tree peeling theorem moves any trace-level parity certificate down prefix trees until each coordinate becomes a one-step next-action choice, converting a rollout certificate into a local one. The counterexample showing DS dimension can increase under rollout uses
Load-bearing premise
The entire argument takes place in the realizable PAC setting: the training data is assumed to be perfectly generated by some target hypothesis in the class H. If the true data-generating process lies outside H, the one-inclusion density machinery and the leave-one-out-to-PAC conversion do not directly apply, and the sample complexity guarantee may not hold.
What would settle it
Construct a natural next-token class H with small DSdim but where the rollout class Roll(H) has high one-inclusion density — this would break the chain ParDim(Roll(H)) ≤ ParDim(H) ≤ DSdim(H) and invalidate the main bound.
If this is right
- If the result extends to agnostic or noisy settings, Chain-of-Thought supervision would remain statistically efficient even when the realizable assumption fails — but the current proof relies on realizability throughout.
- The parity dimension invariant may apply to other sequential composition problems beyond Chain-of-Thought, such as multi-step reinforcement learning or recursive reasoning, wherever a shared local rule generates variable-length outputs.
- The finding that uniform random ERM can be logarithmically suboptimal (Theorem 6.2) while an optimal learner exists suggests practical algorithms should look beyond standard ERM for trace learning.
- The separation between ParDim and DSdim (Corollary 3.7) raises the question of whether other natural complexity parameters in multiclass learning also fail to be rollout-stable, and whether further refinements exist.
Where Pith is reading between the lines
- The result implies that the statistical difficulty of learning to produce correct reasoning traces is entirely determined by the difficulty of learning the next-token distribution — trace length is statistically free. This would mean that data efficiency for Chain-of-Thought training is governed by local rule complexity, not by reasoning chain depth.
- If parity dimension turns out to be the 'right' complexity measure for other autoregressive or recursive learning problems, it could become a standard tool analogous to how VC dimension serves binary classification — but the paper does not explore this generality beyond the rollout setting.
- The counterexample where DSdim increases under rollout suggests a structural reason: trace-level disagreements can occur at incompatible prefix depths, so they cannot be reduced to fixed-depth local disagreements. This obstruction may recur in any setting where sequential composition creates multi-scale disagreement structure.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. This paper studies the realizable PAC sample complexity of learning full autoregressive Chain-of-Thought (CoT) traces under exact-trace loss. The main result (Theorem 1.1) establishes that for every stopping rule halt and every pointwise halt-halting local class H, the PAC sample complexity of the rollout class Roll_halt(H) is O((DSdim(H) + log(1/δ))/ε), with no dependence on rollout length. Since one-step stopping recovers ordinary multiclass learning of H, this rate is worst-case optimal. The proof introduces a new combinatorial parameter called parity dimension (ParDim), which is shown to (i) upper-bound one-inclusion density (Theorem 3.3), (ii) be upper-bounded by DS dimension (Corollary 3.4), and (iii) not increase under autoregressive rollout (Theorem 3.5). The chain of inequalities μ_Roll(H)(n) ≤ ParDim(Roll(H)) ≤ ParDim(H) ≤ DSdim(H) yields the main theorem via standard one-inclusion and leave-one-out-to-PAC black boxes. The paper also constructs a finite counterexample (Section D) showing that DS dimension itself can increase under rollout, justifying the parity dimension detour. An application to full-label multi-instance learning is given in Section 6.
Significance. The paper resolves a natural and well-motivated question: whether the all-or-nothing nature of exact-trace loss for autoregressive CoT incurs a statistical cost beyond the local next-token complexity. The answer is negative, and the optimal rate is characterized sharply. The proof is parameter-free and self-contained: the main bound follows from first principles via the one-inclusion density framework, with no ad hoc assumptions beyond the standard realizable PAC setting. The introduction of parity dimension as a rollout-stable refinement of DS dimension is a genuine technical contribution, and the finite counterexample in Section D (verifying that DSdim(H)=2 but DSdim(Roll(H))≥3) is carefully constructed and verified, demonstrating that the detour through ParDim is necessary rather than merely convenient. The lower bound via one-step stopping (Corollary 3.8) provides an external benchmark against ordinary multiclass learning. The result improves on prior routes (Joshi et al. 2025; Hanneke et al. 2026b; Doron-Arad et al. 2026) by achieving the sharp DSdim rate without logarithmic dependence on rollout length or larger complexity factors.
major comments (2)
- [Theorem 5.7] The extension of η by zero to the full product L_1 × ... × L_d and the verification of line-evenness via the fiber structure of the restriction map is the most delicate step in the rollout stability argument. The claim that 'each full line in L_1 × ... × L_d intersects V in one fiber of the restriction map V → V|_{[d]/{r}}' is correct when the coordinate-r line is a full fiber, but the argument should more explicitly address the case where a line in the extended tensor has no support in V at all (i.e., the line passes entirely through zero-padded entries). In that case the line sum is trivially zero, which is fine, but the phrasing 'intersects V in one fiber' could be read as implying every line has nonempty intersection with V. A one-sentence clarification would strengthen the proof.
- [Section D, Theorem 3.6] The counterexample construction is load-bearing for the paper's narrative that parity dimension is necessary (not merely sufficient). The verification that the base class has DSdim(H)=2 proceeds by ruling out all possible three-state witnesses among {x_0, x_P, x_N, x_R, x_C}. The argument is correct and exhaustive, but it is quite dense. In particular, the forest obstruction argument for the three cases {x_0, x_R, x_C}, {x_P, x_R, x_C}, {x_N, x_R, x_C} relies on the interplay between sign slices, ⊥-slices, and within-sign forests (Tables 2–4). The logic is sound, but a reader would benefit from a brief summary table or diagram showing which case maps to which forest obstruction, to make verification more transparent.
minor comments (7)
- [Table 1] The eO notation in the second row is introduced without explicit definition of the tilde convention. While standard, a footnote stating that polylogarithmic factors are in VCdim(H) and VCdim*(H) would match the precision level of the rest of the paper.
- [Definition 3.1] The even pseudo-cube definition uses η ∈ F_2^{H'|D}, but the notation F_2^{H'|D} is slightly unusual; a brief remark that this is the F_2-vector space of functions from H'|D to F_2 would aid readers less familiar with the convention.
- [Section 2.1, Algorithm 1] The algorithm uses 'halt(x, y)' where y is the accumulated suffix, but Definition 2.1 defines halt as taking arguments (x, u) where u is the emitted suffix. The relationship between 'emitted suffix' and the accumulated y in the algorithm should be stated explicitly (they are the same), to avoid confusion.
- [Section 6, Theorem 6.1] The condition DSdim(G) ≥ 1 is needed for the lower bound, and the DSdim(G) = 0 case is handled separately. The theorem statement could note that the Θ notation implicitly requires DSdim(G) ≥ 1, as is done, but the transition between the two cases in the proof could be smoother.
- [Acknowledgments] The acknowledgment of ChatGPT for finding the finite example in Section D is transparent and appropriate. No change needed, but noted for completeness.
- [Section C, Theorem C.2] The halting-oracle assumption is clearly stated as information-theoretic, but the proof's case analysis for nontermination (predicting ε when the oracle says nontermination) could note that this case arises only when bh's rollout diverges from h*'s rollout at some prefix state, which is the key insight. This is present but somewhat buried.
- [References] Several references are to arXiv preprints from 2026 (e.g., Hanneke et al. 2026a, 2026b; Pabbaraju 2026; Doron-Arad et al. 2026; Balcan et al. 2026). If any of these have been published or accepted by the time of revision, updated citations would be appropriate.
Simulated Author's Rebuttal
We thank the referee for the careful reading and the positive assessment. Both major comments identify legitimate expository gaps in delicate parts of the proof. We will address both in the revision.
read point-by-point responses
-
Referee: [Theorem 5.7] The extension of η by zero to the full product L_1 × ... × L_d and the verification of line-evenness via the fiber structure of the restriction map. The claim that 'each full line in L_1 × ... × L_d intersects V in one fiber of the restriction map V → V|_{[d]/{r}}' could be read as implying every line has nonempty intersection with V. A one-sentence clarification addressing the case where a line passes entirely through zero-padded entries would strengthen the proof.
Authors: The referee is correct that the phrasing is imprecise. When a full line in L_1 × ... × L_d has no support in V—meaning every entry on that line was zero-padded—the line sum is trivially zero, which is consistent with line-evenness but is not covered by the phrase 'intersects V in one fiber.' We will add a sentence after the current statement in the proof of Theorem 5.7 explicitly noting that lines disjoint from V have zero sum by construction, so line-evenness holds for all lines: those intersecting V nontrivially by the fiber argument, and those disjoint from V trivially. revision: yes
-
Referee: [Section D, Theorem 3.6] The verification that DSdim(H)=2 is correct and exhaustive but dense. The forest obstruction argument for the three cases {x_0, x_R, x_C}, {x_P, x_R, x_C}, {x_N, x_R, x_C} relies on the interplay between sign slices, ⊥-slices, and within-sign forests (Tables 2–4). A brief summary table or diagram showing which case maps to which forest obstruction would make verification more transparent.
Authors: We agree that a summary would aid readability. We will add a small table mapping each of the three cases to the specific forest obstruction that rules it out: {x_0, x_R, x_C} maps to the mixed-sign forest (Table 2); {x_P, x_R, x_C} maps to the mixed-sign forest for the ⊥-slice and the within-P forest (Table 3) for surviving P_1/P_2 slices; {x_N, x_R, x_C} maps to the mixed-sign forest (Table 2) for the ⊥-slice and the within-N forest (Table 4) for surviving N_1/N_2 slices. This will be inserted just before the three case analyses. revision: yes
Circularity Check
No significant circularity identified.
full rationale
The paper's central derivation chain is self-contained and parameter-free. The main theorem (Theorem 1.1) follows from the chain μ_{Roll_halt(H)}(n) ≤ ParDim(Roll_halt(H)) ≤ ParDim(H) ≤ DSdim(H), combined with standard one-inclusion and leave-one-out-to-PAC black boxes (Theorems 2.10, 2.11). Each link in this chain is proved from first principles within the paper: Theorem 3.3 (parity density theorem) is proved in Section 4 via finite linear algebra (Lemmas 4.5–4.7); Theorem 3.5 (parity dimension does not increase under rollout) is proved in Section 5 via partition-tree peeling (Theorems 5.4, 5.7); the inequality ParDim ≤ DSdim is proved in Corollary 3.4 / Appendix A by a direct support argument. The lower bound (Corollary 3.8) recovers ordinary multiclass learning via one-step stopping, which is an external benchmark. The cited results (Daniely-Shalev-Shwartz 2014, Pabbaraju 2026, Aden-Ali et al. 2023, Hanneke et al. 2026a) are used as standard black boxes with stated assumptions that do not include the target result, and they are externally verifiable. No step reduces to its inputs by construction, no parameter is fitted to data and then 'predicted,' and no self-citation is load-bearing for the central claim.
Axiom & Free-Parameter Ledger
axioms (4)
- domain assumption Realizable PAC setting: training data is generated by a target hypothesis h* in H
- domain assumption Pointwise halting: for every h in H and every initial state x, the rollout terminates after finitely many iterations
- standard math One-inclusion transductive leave-one-out bound (Theorem 2.10)
- standard math Leave-one-out to PAC aggregation (Theorem 2.11)
invented entities (1)
-
Parity dimension (ParDim)
independent evidence
read the original abstract
We prove that, in the realizable PAC setting, the sample complexity of exact-trace learning for full autoregressive Chain-of-Thought traces is upper bounded by the standard multiclass rate of the local next-token class, where this rate is governed by the Daniely--Shalev-Shwartz dimension. Under exact-trace loss, one wrong action makes the whole trace incorrect; nevertheless, for every stopping rule $\mathtt{halt}$ and every pointwise $\mathtt{halt}$-halting local class $\mathrm{H}$, $n_{\mathrm{PAC}}^{\varepsilon,\delta}(\operatorname{Roll}_{\mathtt{halt}}(\mathrm{H}))=O((\operatorname{DSdim}(\mathrm{H})+\log(1/\delta))/\varepsilon)$, with no dependence on rollout length. The dependence on $\operatorname{DSdim}(\mathrm{H})$ is worst-case optimal, since one-step stopping recovers ordinary multiclass learning of $\mathrm{H}$. The proof introduces parity dimension, a rollout-stable refinement of DS dimension based on even pseudo-cubes. It controls one-inclusion density via a low-coordinate spanning theorem on finite restrictions and, unlike DS dimension itself, does not increase under autoregressive rollout. We also show why this detour is necessary: DS dimension can increase under rollout.
Reference graph
Works this paper leans on
-
[1]
Online Learnability of Chain-of-Thought Verifiers: Soundness and Completeness Trade-offs
M.-F. Balcan, A. Blum, K. Fragkia, Z. Li, and D. Sharma. Online learnability of chain-of-thought verifiers: soundness and completeness trade-offs. arXiv:2603.03538,
work page internal anchor Pith review Pith/arXiv arXiv
-
[2]
A Theory of Online Learning with Autoregressive Chain-of-Thought Reasoning
I. Doron-Arad, I. Mehalel, and E. Mossel. A theory of online learning with autoregressive chain-of- thought reasoning. arXiv:2605.06819,
work page internal anchor Pith review Pith/arXiv arXiv
-
[3]
An Optimal Sauer Lemma Over $k$-ary Alphabets
S. Hanneke, Q. Meng, S. Moran, and A. Shaeiri. An optimal Sauer lemma over k-ary alphabets. arXiv:2604.12952,
work page internal anchor Pith review Pith/arXiv arXiv
-
[4]
The Optimal Sample Complexity of Multiclass and List Learning
C. Pabbaraju. The optimal sample complexity of multiclass and list learning. arXiv:2604.24749,
work page internal anchor Pith review Pith/arXiv arXiv
-
[5]
Sample Complexity of Autoregressive Reasoning: Chain-of-Thought vs. End-to-End
S. Hanneke, I. Mehalel, and S. Moran. Sample complexity of autoregressive reasoning: chain-of- thought vs. end-to-end. arXiv:2604.12013,
work page internal anchor Pith review Pith/arXiv arXiv
-
[6]
23 M. Nye, A. J. Andreassen, G. Gur-Ari, H. Michalewski, J. Austin, D. Bieber, D. Dohan, A. Lewkowycz, M. Bosma, D. Luan, C. Sutton, and A. Odena. Show your work: Scratchpads for intermediate computation with language models. arXiv:2112.00114,
work page internal anchor Pith review Pith/arXiv arXiv
-
[7]
X. Wang, J. Wei, D. Schuurmans, Q. Le, E. Chi, S. Narang, A. Chowdhery, and D. Zhou. Self- consistency improves chain of thought reasoning in language models. arXiv:2203.11171,
work page internal anchor Pith review Pith/arXiv arXiv
-
[8]
The Expressive Power of Transformers with Chain of Thought
W. Merrill and A. Sabharwal. The expressive power of transformers with chain of thought. arXiv:2310.07923,
work page internal anchor Pith review Pith/arXiv arXiv
-
[9]
Z. Li, H. Liu, D. Zhou, and T. Ma. Chain of thought empowers transformers to solve inherently serial problems. arXiv:2402.12875,
work page internal anchor Pith review Pith/arXiv arXiv
-
[10]
C. Yang, N. Srebro, D. McAllester, and Z. Li. PENCIL: Long thoughts with short memory. arXiv:2503.14337,
work page internal anchor Pith review Pith/arXiv arXiv
-
[11]
C. Yang, N. Srebro, and Z. Li. Recursive models for long-horizon reasoning. arXiv:2603.02112,
work page internal anchor Pith review Pith/arXiv arXiv
-
[12]
A Dimension comparisons For completeness, we prove the dimension comparisons used in Corollary 3.4. Keeping the proof here lets the main text use the comparison chain without interrupting the proof of the autoregressive PAC bound. Proof of Corollary 3.4.The upper density bound sup n≥1 µH(n)≤ParDim(H) is exactly Theorem 3.3. Next, ParDim(H) ≤DSdim (H) foll...
work page 2026
-
[13]
Hence, conditional onS, Pr bg∼VG(S) [bg⋆(Uj,r)̸=g ⋆ ⊥(Uj,r)] = 2u−1 1 + 2u ≥ 1 3
Such choices put a one somewhere in Uj,r, and therefore make a full-label mistake onU j,r. Hence, conditional onS, Pr bg∼VG(S) [bg⋆(Uj,r)̸=g ⋆ ⊥(Uj,r)] = 2u−1 1 + 2u ≥ 1 3 . Taking expectation over the sample and the random ERM draw gives E[errD(bg⋆)]≥ ρ 3 1− ρ N n . Indeed, each rare list has mass ρ/N, and the probability that a fixed rare list is absent...
work page 2026
-
[14]
In this setup, a complete-trace online mistake can be charged to one local next-action mistake. The simulation below is oracle-assisted: it uses a halting oracle to decide whether the current local prediction map terminates from the queried start state. Thus this appendix is only an information-theoretic online comparison and is not used in the PAC proof ...
work page 1988
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.