Skip to main content
Back

Researchers Prove Chain-of-Thought Training Beats End-to-End Learning at Any Reasoning Length

New theoretical work proves that showing a model its intermediate reasoning steps during training eliminates any dependence on how long the reasoning is.

Pro

Paper, Full Access
  • Chain-of-thought supervision makes sample complexity independent of reasoning length T for any finite-VC base class.
  • End-to-end supervision can produce essentially any growth rate between constant and linear in T.
  • No combinatorial dimension can cleanly characterize which classes admit sublinear end-to-end growth.
  • Proof uses sample compression on an inflated version of each CoT example, one per prefix.
  • A new autoregressive tree dimension gives logarithmic e2e bounds strictly broader than Littlestone-based ones.
  • Builds on Joshi et al. COLT 2025, resolving several of their open questions.

A new theoretical result answers a question that has been lurking behind every chain-of-thought pipeline: does supervising the intermediate reasoning steps actually change the fundamental difficulty of learning, or does it just help in practice? According to a fresh paper from Steve Hanneke, Idan Mehalel, and Shay Moran, the answer is a clean and surprising yes. When a learner sees the entire generated trajectory during training, the number of examples needed to hit a target accuracy stops depending on the length of the reasoning chain altogether.

The work builds directly on a framework introduced by Joshi et al. at COLT 2025, which modeled autoregressive models as iterated next-token generators and asked, in PAC learning terms, how sample complexity scales with the number of generation steps T. That paper left several open questions, and this one closes most of them.

The setup in plain terms

PAC (Probably Approximately Correct) learning asks how many labeled examples you need so that, with high probability, your learned predictor is close to the true target. In this autoregressive version, an unknown next-token generator maps a sequence of tokens to the next token and is iteratively applied for T steps, producing a chain whose final token constitutes the output. These models generate text one token at a time, and often solve complex tasks by producing intermediate reasoning steps before arriving at a final answer.

Two supervision regimes are worth comparing:

  • End-to-end (e2e): training examples reveal only the final answer after T steps.
  • Chain-of-thought (CoT): training examples reveal the entire