Pith. sign in

REVIEW 5 cited by

A Theory of Learning with Autoregressive Chain of Thought

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2503.07932 v2 pith:7T4EN2C7 submitted 2025-03-11 stat.ML cs.AIcs.CCcs.LG

Nirmit Joshi , Gal Vardi , Adam Block , Surbhi Goel , Zhiyuan Li , Theodor Misiakiewicz , Nathan Srebro This is my paper · ORCID
classification stat.MLcs.AIcs.CCcs.LG
keywords chain-of-thoughtbaselearningclassallowscomplexitysamplewhen
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
read the original abstract

For a given base class of sequence-to-next-token generators, we consider learning prompt-to-answer mappings obtained by iterating a fixed, time-invariant generator for multiple steps, thus generating a chain-of-thought, and then taking the final token as the answer. We formalize the learning problems both when the chain-of-thought is observed and when training only on prompt-answer pairs, with the chain-of-thought latent. We analyze the sample and computational complexity both in terms of general properties of the base class (e.g. its VC dimension) and for specific base classes such as linear thresholds. We present a simple base class that allows for universal representability and computationally tractable chain-of-thought learning. Central to our development is that time invariance allows for sample complexity that is independent of the length of the chain-of-thought. Attention arises naturally in our construction.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 5 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. When Does On-Policy Interaction Help? Representational Tradeoffs in Value-Based Imitation Learning

    cs.LG 2026-07 conditional novelty 8.0 of 10

    Interactive imitation learning works with only expert-value realizability, while offline learning under the same assumption is provably hard.

  2. Mistake-bounded online learning with operation caps

    cs.LG 2025-09 conditional novelty 7.0 of 10

    The paper proves opt_ag,weak(F, eta) = O((k ln k) opt_std(F) + k eta), matching the known lower bound, and develops a new operation-caps model for mistake-bounded online learning.

  3. Hierarchical Domain Generalization

    cs.LG 2026-07 conditional novelty 6.0 of 10

    Over infinite domains, hierarchy-uniform domain generalization is impossible for every nontrivial hypothesis class; a length-generalization bound is a property of the length hierarchy, not a hierarchy-free guarantee.

  4. From Reasoning to Super-Intelligence: A Search-Theoretic Perspective

    cs.AI 2025-07 conditional novelty 6.0 of 10

    The Diligent Learner, a reverse-curriculum algorithm with explicit backtracking and a validator, is proven to learn chain-of-thought reasoning efficiently under two learnability assumptions, while standard methods fai...

  5. Sample Complexity and Representation Ability of Test-time Scaling Paradigms

    cs.LG 2025-06 conditional novelty 6.0 of 10

    Best-of-n sampling provably needs about 1/Δ samples versus 1/Δ² for self-consistency, and a constructed Transformer can route among experts using verifier feedback to reach near-optimal final responses.

Pith tools