← All AI/ML open problems

Transformer theory · Statistical learning theory / Open question

The Price of Reasoning Steps

Reasoning tokens can make learning easier while making deployment expensive. A theory should tell us which steps must be taught, generated or absorbed into the network.

OpenEditorially scopedFramework needs definitionCompiled 2026-11-19

Seed catalog · Showing the bundled record.

Problem statement

Take length-H products of permutations of S states, with uniformly sampled generators and a specified initial state. Train a finite-width causal softmax transformer to predict the final state, allowing a budget of intermediate state labels independently corrupted at rate nu below one half. Determine the trade-off among labelled prefixes, model depth and generated state-trace tokens for polynomial-time gradient learning and final-state error at most epsilon; compare explicit traces with computation internalized in the network.

Assumptions and scope

  • Fix the state-transition algebra, input distribution and task-size parameter; distinguish parity from noncommutative state tracking.
  • Specify which steps are revealed, their noise model and whether teacher forcing is used. Charge supervision and inference separately.
  • Fix finite-width softmax attention and the training curriculum. Expressivity, information-theoretic sample complexity and computational learning time are separate resources.

What would settle it?

Upper and lower bounds for the supervision–depth–token trade-off under partial or noisy traces, with a provably trainable procedure or a computational obstruction.

Selected for a theoretical or computational target. A fitted scaling curve or improved benchmark score alone does not establish the stated learning-theoretic guarantee.

Status and evidence

Parity sample-complexity separations, state-tracking optimization, logarithmic-stage internalization of parity, PAC taxonomies with complete traces, and hard-attention scratchpad lower bounds already exist. The target is the partially observed noisy-trace resource frontier for a specified trained softmax model. This is an editorial, source-motivated research target. The preliminary review through 2026-11-19 does not certify novelty or exclude an unlocated resolution.

Preliminary source check; not an expert-verified open status or an independent audit of proposed proofs. The compilation date is not a literature-review cutoff.

Sources and further reading

  1. Kim and Suzuki — Transformers Provably Solve Parity Efficiently with Chain of Thought ↗partial theory · source checked 2026-11-19

    Abstract checked: one-layer parity; hardness without intermediate supervision for finite-precision gradient methods, efficient learning with teacher forcing or self-verified augmented data.

  2. Wen et al. — From Sparse Dependence to Sparse Attention: How Chain-of-Thought Enhances Transformer Sample Efficiency ↗partial theory · source checked 2026-11-19

    Abstract checked: polynomial versus exponential sample complexity for parity with and without chain of thought.

  3. Hanneke, Mehalel and Moran — Sample Complexity of Autoregressive Reasoning: Chain-of-Thought vs. End-to-End ↗partial theory · source checked 2026-11-19

    Abstract checked: near-complete statistical taxonomy of end-to-end sample complexity in generation length T, and T-independent complexity with chain-of-thought supervision, in the Joshi et al. PAC framework. Computational efficiency is a separate question.

  4. Huang et al. — Transformers Provably Learn to Internalize Chain-of-Thought ↗partial theory · source checked 2026-11-19

    Abstract checked: a logarithmic-stage curriculum lets L-layer transformers learn k-parity with poly(n) samples without explicit reasoning tokens.

  5. Li et al. — Chain of Thought Empowers Transformers to Solve Inherently Serial Problems ↗partial theory · source checked 2026-11-19

    Abstract checked: expressivity results, AC0 without chain of thought at constant precision and size-T circuits with T steps. These are not training guarantees.

  6. Bavandpour et al. — Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers ↗partial theory · source checked 2026-11-19

    Abstract checked: chain-of-thought length lower bounds, tight up to logarithmic factors, in the hard-attention regime.

  7. Huang et al. — Transformers Provably Learn Chain-of-Thought Reasoning with Length Generalization ↗partial theory · source checked 2026-11-19

    Abstract checked: gradient-descent guarantees on synthetic state-tracking tasks, including NC1-complete problems with chain of thought, and recursive self-training extending length.