{"id":"6463551e-9463-4900-b047-49b3752ebdb2","arxiv_id":"2608.07224","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For stochastic next-token generators, chain-of-thought supervision costs at most base learning at scale epsilon/M^2, while end-to-end learning costs at most about M/epsilon times chain-of-thought, with tight worst-case constructions.","lead":"This paper introduces a mathematical model of stochastic autoregressive generation, where a generator samples the next token from a probability distribution, and asks how many training examples are needed under different supervision styles. It shows that chain-of-thought samples can be far more data-efficient than final-token-only samples, and gives tight comparisons for logistic next-token models.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified: the stochastic autoregressive taxonomy is internally consistent under its stated realizable assumptions.","rationale":"The reader's weakest_assumption correctly identifies the realizable PAC setting and the LPN conditionality as the main caveats of the paper. These are genuine limitations, but they are explicit in the model definition and standard for this line of work; they do not constitute an internal flaw or an unstated assumption that would invalidate the central claim. My own review of the proof steps did not find a load-bearing technical gap: the sample-complexity comparisons, the exact-scale lower bounds, and the shifted-scale upper bounds all appear internally consistent. Because the caveats are stated and the mathematical arguments check out, the existing ACCEPT verdict stands. I mark agreement as 'partial' because the reader's flagged assumption is the right caveat to mention, but I do not treat it as a reason to change the verdict.","tokens_in":67066,"tokens_out":29417,"duration_ms":292767,"concrete_test":"Implement a small brute-force verification of Theorem 5.1's reduction: for randomly generated finite classes with M in {2,3,4}, draw a target g*, train a base learner to squared loss epsilon/M^2 on the random-time state distribution, construct the induced generator, and confirm that the final-token squared loss is at most epsilon. Additionally, verify Theorem 6.1's packing argument on a small artificial class by running the CoT learner and checking that the unique-decoding condition holds with c0 < 1/4.","verdict_should_be":"UNCHANGED","load_bearing_attack":"I read the proofs of The main results (Theorems 4.1, 5.1, 6.1-6.3, 7.6) and the logistic case study. The reductions are technically sound: Theorem 5.1's base-to-CoT reduction correctly uses the random-time state distribution, and the M^2 constant follows from Jensen and Cauchy-Schwarz; Theorem 6.1's Fano/packing argument properly conditions on the prompts and bounds mutual information by M m bits; the exact-scale lower bound constructions respect the blocker lemma, and the distributional choices satisfy the stated KL bounds. The main caveats are the realizable PAC assumption (target in F) and the LPN-conditioned hardness result, both explicitly stated and standard in the field. I found no internal contradiction, circular dependence, or missing proof step that would threaten the central sample-complexity taxonomy.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces a PAC-learning model for binary stochastic autoregressive generation, in which a single generator assigns a next-token Bernoulli distribution to every prompt string and iterated sampling produces length-M trajectories. Three supervision models are compared: base one-step samples, chain-of-thought (CoT) samples revealing full trajectories, and end-to-end (e2e) samples revealing only the final token. The main contribution is a sample-complexity taxonomy for these three tasks under squared loss. Theorems 4.1, 5.1, and 6.3 show that at the same accuracy scale there is no universal ordering of m_base, m_CoT, and m_e2e, but shifted-scale comparisons hold for every class: m_CoT(eps) is at most m_base(eps/M^2), and m_e2e(eps) is at most O~(M(1∨m_CoT(c eps))/eps), with matching constructions showing these shifts are essentially necessary. The paper also proves fat-shattering bounds for e2e learning (Theorem 7.6), a logistic-regression case study with an efficient proper CoT learner and an LPN-conditional hardness result for proper e2e learning (Theorems 8.1--8.3), and a detailed Section 10 on KL-based trajectory sampling, including margin-free lower bounds and an impossibility result for e2e sampling. All main results are proven in the realizable PAC setting, a limitation stated explicitly in Section 1.1.","tokens_in":67199,"tokens_out":9814,"duration_ms":107373,"significance":"The paper is a substantial contribution to the theory of stochastic autoregressive learning. If the results hold as stated, they fundamentally revise the deterministic picture of Joshi et al. and Hanneke et al.: the stochastic setting forbids exact-scale universal comparisons and instead requires accuracy-shifted comparisons, with both upper and lower bounds proved. The authors provide full proofs of the main reductions, and the constructions are self-contained against external benchmarks. The paper is careful about its assumptions: the realizable PAC condition is stated in Section 1.1, the LPN hardness result in Section 8.3 is explicitly conditional, and Section 10 sharply separates margin-free facts from margin-dependent transfers. The proof sketches in Section 2 are unusually informative, and the lower-bound techniques (Assouad, Fano, packing, rate-distortion) are used correctly. I found no internal contradiction or circular dependence in the central claims.","major_comments":[],"minor_comments":[{"comment":"In the first paragraph of the proof, the bound on |U| is stated as n ≤ |U| ≤ n(2M−1), but the set U = {x_i z : z ∈ {0,1}^{<M}} has n(2^M−1) elements. Since the subsequent line correctly uses |U| ≤ n2^M, this is only a typo, but it should be corrected to n(2^M−1) or simply n2^M.","section":"Section 7, proof of Theorem 7.2"},{"comment":"The paragraph beginning 'We believe that our techniques can generally be adapted' explicitly disclaims proofs for the L1 analogues. This is an honest limitation, but as written it sits in the results section and could be misread as proven. I recommend moving the L1 discussion to a clearly labeled conjecture/remark in Section 11, or adding an explicit sentence that these statements are conjectural and not part of the formal results.","section":"Section 1.2, L1 loss paragraph"},{"comment":"The corollary states a Hellinger/total-variation guarantee for the logistic class with sample complexity eO((d^2 log M + log(1/δ))/ε^2), but the cited Theorem 8.2 is stated for squared-loss final-token accuracy ε with sample complexity eO((d^2 log M + log(1/δ))/ε). The proof mentions 'run at Hellinger accuracy ε^2', which is the correct mechanism, but the sample-complexity display should be stated explicitly in the corollary or derived in one line to avoid confusion.","section":"Section 10.4, Corollary 10.8"},{"comment":"The proof chooses a universal constant η < 1/8 and then sets c0 = η/2, but the particular value of η is left unspecified. Since the argument only needs any fixed η < 1/8, I suggest writing 'fix η = 1/16' for concreteness, which makes the quantitative claim immediately checkable.","section":"Section 10.5, Proposition 10.12"},{"comment":"There are several minor typographical/OCR artifacts, such as 'whetheras' in Section 1.3 and a duplicated 'the' near the start of Section 2's proof sketch. These do not affect the mathematics but should be cleaned up in the final version.","section":"Throughout"}],"recommendation":"minor_revision","confidential_remarks":"I see no novelty or scope concern: the paper is squarely within the target venue's interests and the central claims are internally consistent under the stated realizable PAC and LPN assumptions. The revision needed is purely editorial — the one mathematical typo in Section 7 (|U| bound) and the placement/labeling of the unproven L1 conjectures. I am happy to see the paper accepted after these local fixes."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The thing to know about this paper is that it earns its length. It introduces a stochastic autoregressive PAC model, proves a nearly complete sample-complexity taxonomy for base, CoT, and e2e supervision, and then goes further with fat-shattering bounds and a logistic case study. The central message is that stochastic autoregressive learning is governed by shifted-scale comparisons rather than by the deterministic relationships: exact-scale ratios can blow up arbitrarily, but CoT at scale epsilon is controlled by base at epsilon/M^2, and e2e is controlled by CoT up to an M/epsilon factor. That is a real result, not a repackaging of prior work.\n\nWhat the paper does well: the proofs are genuinely there. I read the main reductions, the Fano/packing argument, the blocker constructions, and the logistic structural bound on pseudo-dimension. The proofs are internally consistent, the lower bounds use standard Assouad and KL technology carried through carefully, and the constructions actually match the claimed scales. The paper is also honest: it states the realizable assumption, flags the LPN-conditioned hardness result, and explicitly marks the L1 analogues and margin-dependent KL transfers as not fully proven. That kind of clarity is worth a lot.\n\nSoft spots, in proportion: the main body assumes the target generator lies in the class and the prompt distribution is fixed but arbitrary. That is standard for PAC-style theory, but it means the sample-complexity bounds do not directly apply to misspecified settings. The logistic e2e hardness result is conditional on LPN, which is a cryptographic assumption — again standard in this subfield but worth remembering when citing. The KL section is interesting but the margin-free part is mostly negative or structural, and the positive transfers require a lower margin on probabilities; the paper says so explicitly. There is no machine-checked proof, and I did not verify every constant, but I found no step that looked wrong or circular. The citation pattern is fine: the deterministic model of Joshi et al. is the baseline, and the self-citation overlap is related work, not a premise.\n\nBottom line: this is a substantive contribution to learning theory, not a breakthrough that will change LLM practice directly, but it gives the right vocabulary for thinking about CoT supervision in stochastic generators. The paper deserves a serious referee and, assuming the review process does not uncover a hidden flaw, publication. I would send it out and cite it in my own work.","headline":"A solid, internally consistent theory paper that delivers a genuine sample-complexity taxonomy for stochastic autoregressive learning, with the main caveat being its realizable-PAC setting and one conditional hardness result.","tokens_in":67740,"tokens_out":1126,"would_cite":true,"duration_ms":16870,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q32"],"pacs":[],"model":"deepseek-v4-flash","headline":"Stochastic autoregressive learning breaks the deterministic sample-complexity comparison between base, chain-of-thought, and end-to-end supervision.","keywords":["stochastic autoregressive learning","chain-of-thought","end-to-end learning","sample complexity","PAC learning","fat-shattering dimension","logistic autoregressive class","learning parity with noise"],"falsifier":"Run the root-blocker constructions of Sections 4 and 6 at a concrete small ε (say ε = $2^{{-10}}$, M = 5) and compute m_base, m_CoT, and m_e2e by exhaustive search over learners; finding m_CoT(ε) > m_base(ε/M²) or m_e2e(ε) ≫ (M/ε)m_CoT(cε) would refute the claimed shifted-scale bounds, while finding both ratios bounded by M/ε for all large M would refute Theorem 4.1.","tokens_in":66880,"feed_emoji":"🎲","tokens_out":5135,"duration_ms":51803,"temperature":0.7,"pith_summary":"The paper introduces a PAC-learning model in which a fixed stochastic generator assigns a Bernoulli next-token distribution to every prompt and is iterated for M steps. It studies the minimum samples needed to learn the one-step probabilities from base samples, the final-token probability from full chain-of-thought trajectories, and the same final-token probability from end-to-end samples that reveal only the last token. The central finding is that, at the same accuracy scale, no universal ordering exists: both the CoT-to-base and e2e-to-CoT sample-complexity ratios can be made arbitrarily larger than M/ε. After shifting scales, however, universal bounds appear: CoT at scale ε costs no more than base at scale ε/M², and e2e at scale ε costs at most O~(M(1∨m_CoT(cε))/ε). This matters because practical language models are stochastic, so a theory built on deterministic next-token functions can misstate what chain-of-thought and end-to-end samples are worth.","feed_headline":"Stochastic autoregression resets the CoT sample-cost order","feed_subtitle":"CoT costs base at scale ε/M², e2e costs M/ε times CoT, and both gaps are provably unavoidable.","key_machinery":"The machinery is the stochastic autoregressive generator g:Σ*→Δ(Σ), whose one-step probabilities p_g(s) are iterated M times to induce the end-to-end final-token probability $q^{{e2e-M}}$_g(x). The key quantitative fact is a coupling bound: |$q_g^{{e2e-M}}$(x)−q_{bg}^{e2e-M}(x)| ≤ E[∑_{t=1}^M |p_g(S_t)−p_bg(S_t)| | X=x], so one-step squared error at scale ε/M² suffices for final-token squared error ε, giving the base-to-CoT comparison. For the CoT-to-e2e bound, the paper packs the induced e2e predictors, applies Fano's inequality using that each length-M trajectory carries only M binary bits, and then invokes a standard fat-shattering regression bound; the lower bounds are built from root-blocker gadgets whose hidden signs move one-step probabilities by Θ(√ε) but accumulate to Θ(√ε) shifts in final-token probabilities.","core_discovery":"The central claim is a sample-complexity taxonomy for stochastic autoregressive learning that differs fundamentally from the deterministic theory. At scale ε, both m_CoT/m_base and m_e2e/m_CoT can be made simultaneously arbitrarily larger than M/ε, the natural analogue of the deterministic rates, so no universal comparison holds at the same accuracy scale. Nevertheless, for every class, CoT learning at scale ε is upper bounded by base learning at scale ε/M², and e2e learning at scale ε is upper bounded, up to logarithmic factors, by (M/ε)·m_CoT(cε), with both bounds shown essentially tight. For the logistic class with dimension d, e2e learning needs Õ(d² log M/ε) samples information-theoretically, an efficient proper CoT learner achieves the same bound, and no efficient proper e2e learner exists under the LPN assumption, yielding a concrete statistical and computational separation between CoT and end-to-end supervision.","pith_inferences":["Editorial inference: the realizable assumption — the true generator lies in the class F and the prompt distribution is fixed but arbitrary — is essential; for misspecified generators the stated taxonomy does not apply, so these theorems do not directly transfer to arbitrary untrained language models.","Editorial inference: the ε/M² scale shift suggests that stochastic noise accumulates quadratically through trajectories; if so, treating chain-of-thought samples as exact intermediate labels overstates what they reveal.","Editorial inference: the paper conjectures L1-loss analogues with correspondingly different scales (for example m_CoT,1(ε) ≤ m_base,1(ε/M)), but these are unproved extensions stated in the discussion rather than results.","Editorial inference: the e2e information-vs-computation gap for logistic classes suggests similar statistical-computational separations may hold for other parametric next-token families, and the LPN reduction is a template for testing them."],"forward_implications":["If the bounds are correct, no same-scale comparison of base, CoT, and e2e sample complexity exists for stochastic classes; any universal statement must change the accuracy scale.","CoT supervision is never more expensive than base learning at scale ε/M², and this scale cannot be improved to a coarser base scale in general.","e2e learning is at most (M/ε)-times the CoT sample complexity up to logarithmic factors and a constant scale shift, and the factor M/ε is necessary.","The e2e sample complexity of any class is governed by the fat-shattering dimension of the one-step class at scale √ε/M, with near-matching lower bounds and optimality of the margin scale.","For logistic autoregressive generators, e2e learning is statistically easy but computationally hard for proper learners under LPN, while CoT supervision admits an efficient proper learner, giving a concrete separation between the two supervision models."],"supporting_citations":[{"why":"Introduces the deterministic autoregressive chain-of-thought framework that the stochastic model generalizes, and supplies the natural baseline for the comparison ratios M/ε.","marker":"[12]"},{"why":"Gives the near-complete deterministic sample-complexity taxonomy for CoT versus e2e learning, which the paper shows does not transfer to the stochastic setting.","marker":"[9]"},{"why":"Presents the more general imitation-learning model that includes autoregressive generation, and is compared against for the logistic class's dependence on dimension d.","marker":"[41]"},{"why":"Provides the learning parity with noise prediction assumption that is assumed for the computational hardness result ruling out efficient proper e2e learners.","marker":"[19]"},{"why":"Supplies the Rudelson–Vershynin entropy estimate used in the fat-shattering upper bound for e2e learning.","marker":"[14]"},{"why":"Supplies the Mendelson–Vershynin L2 entropy theorem that underlies the fat-shattering regression sample bound used throughout.","marker":"[13]"},{"why":"Supplies the Goldberg–Jerrum pseudo-dimension bound for semialgebraic classes, used to control the logistic end-to-end class after the rational-function change of variables.","marker":"[47]"},{"why":"Provides the finite-class fast-rate aggregation bound used in the paper's base regression upper bounds.","marker":"[18]"},{"why":"Provides the KL chain rule for relative entropy that underlies the Section 10 trajectory-sampling results and the linear-in-horizon sampling bound.","marker":"[5]"}],"fun_headline_variants":["Stochastic autoregression scrambles CoT and e2e sample costs","No universal sample-cost order in stochastic autoregression","CoT and e2e sample costs need different accuracy scales","Rescaled accuracy fixes CoT and e2e sample-cost gaps","Autoregressive learning: sample costs are scale-dependent"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The general sample-complexity theorems require the realizable PAC setting — the true generator lies in the class F and the prompt distribution is fixed but arbitrary — and the computational CoT-e2e separation additionally assumes the LPN prediction hardness assumption.","fun_headline_variants_meta":{"raw":{"variants":["Stochastic autoregression scrambles CoT and e2e sample costs","No universal sample-cost order in stochastic autoregression","CoT and e2e sample costs need different accuracy scales","Rescaled accuracy fixes CoT and e2e sample-cost gaps","Autoregressive learning: sample costs are scale-dependent"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000676,"raw_usage":{"total_tokens":3161,"prompt_tokens":1120,"completion_tokens":2041,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":736,"completion_tokens_details":{"reasoning_tokens":1956}},"tokens_in":736,"tokens_out":2041,"duration_ms":19229,"temperature":1.0,"reasoning_tokens":1956,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T12:25:27.072159+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the root-blocker constructions of Sections 4 and 6 at a concrete small ε (say ε = $2^{{-10}}$, M = 5) and compute m_base, m_CoT, and m_e2e by exhaustive search over learners; finding m_CoT(ε) > m_base(ε/M²) or m_e2e(ε) ≫ (M/ε)m_CoT(cε) would refute the claimed shifted-scale bounds, while finding both ratios bounded by M/ε for all large M would refute Theorem 4.1.","supporting_citations":[{"cited_title":"A theory of learning with autoregressive chain of thought","cited_arxiv_id":null,"evidence_quote":"Introduces the deterministic autoregressive chain-of-thought framework that the stochastic model generalizes, and supplies the natural baseline for the comparison ratios M/ε."},{"cited_title":"Foster, Adam Block, and Dipendra Misra","cited_arxiv_id":null,"evidence_quote":"Presents the more general imitation-learning model that includes autoregressive generation, and is compared against for the logistic class's dependence on dimension d."},{"cited_title":"Noise-tolerant learning, the parity problem, and the statistical query model.Journal of the ACM, 50(4):506–519, 2003","cited_arxiv_id":null,"evidence_quote":"Provides the learning parity with noise prediction assumption that is assumed for the computational hardness result ruling out efficient proper e2e learners."},{"cited_title":"Combinatorics of random processes and sections of convex bodies.Annals of Mathematics, 164(2):603–648, 2006","cited_arxiv_id":null,"evidence_quote":"Supplies the Rudelson–Vershynin entropy estimate used in the fat-shattering upper bound for e2e learning."},{"cited_title":"Entropy and the combinatorial dimension.Inven- tiones Mathematicae, 152(1):37–55, 2003","cited_arxiv_id":null,"evidence_quote":"Supplies the Mendelson–Vershynin L2 entropy theorem that underlies the fat-shattering regression sample bound used throughout."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the Goldberg–Jerrum pseudo-dimension bound for semialgebraic classes, used to control the logistic end-to-end class after the rational-function change of variables."},{"cited_title":"Optimal learning with Q-aggregation.The Annals of Statistics, 42(1):211–224, 2014","cited_arxiv_id":null,"evidence_quote":"Provides the finite-class fast-rate aggregation bound used in the paper's base regression upper bounds."}],"review_version":1}