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.
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
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.