REVIEW 9 cited by
Transformers Provably Solve Parity Efficiently with Chain of Thought
Not yet reviewed by Pith; the record is open.
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
Transformers Provably Solve Parity Efficiently with Chain of Thought
read the original abstract
This work provides the first theoretical analysis of training transformers to solve complex problems by recursively generating intermediate states, analogous to fine-tuning for chain-of-thought (CoT) reasoning. We consider training a one-layer transformer to solve the fundamental $k$-parity problem, extending the work on RNNs by Wies et al. (2023). We establish three key results: (1) any finite-precision gradient-based algorithm, without intermediate supervision, requires substantial iterations to solve parity with finite samples. (2) In contrast, when intermediate parities are incorporated into the loss function, our model can learn parity in one gradient update when aided by \emph{teacher forcing}, where ground-truth labels of the reasoning chain are provided at each generation step. (3) Even without teacher forcing, where the model must generate CoT chains end-to-end, parity can be learned efficiently if augmented data is employed to internally verify the soundness of intermediate steps. Our findings, supported by numerical experiments, show that task decomposition and stepwise reasoning naturally arise from optimizing transformers with CoT; moreover, self-consistency checking can improve multi-step reasoning ability, aligning with empirical studies of CoT.
Forward citations
Cited by 9 Pith papers
-
Transformers Provably Learn to Internalize Chain-of-Thought
L-layer transformers under Log-ICoT curriculum provably learn k-parity with poly(n) samples and log k stages, matching explicit CoT efficiency without inference overhead.
-
On the Emergence of Implicit Curriculum in RLVR Learning Dynamics
For a stylized transformer, outcome-only RL learns short compositions, and mixed-difficulty training produces an implicit easy-to-hard curriculum: smooth difficulty spectra relay progress, abrupt spectra grok.
-
Learning through Internalization
A simplified one-layer transformer provably learns parities first with explicit CoT supervision then internalizes to direct computation as CoT tokens are removed.
-
Agentic Transformers Provably Learn to Search via Reinforcement Learning
In a stochastic k-ary tree, a two-head transformer learns randomized DFS via policy gradient under depth-wise curriculum, generalizes to deeper trees, and adapts to imbalanced goals via discounting.
-
A Theory of Online Learning with Autoregressive Chain-of-Thought Reasoning
Online mistake bounds for autoregressive output learning can grow logarithmically with generation horizon M under end-to-end feedback but become independent of M with chain-of-thought trajectory access.
-
Learning to Think from Multiple Thinkers
Multi-thinker CoT learning is hard passively under crypto assumptions but admits an efficient active algorithm with O(log 1/ε log log 1/ε) thinkers and O(1/ε poly log 1/ε) end-result data.
-
The Power of Power Law: Asymmetry Enables Compositional Reasoning
Power-law data distributions outperform uniform ones for compositional reasoning by creating asymmetry that lets frequent skill compositions scaffold rare ones with less data.
-
The Power of Power Law: Asymmetry Enables Compositional Reasoning
Power-law data sampling creates beneficial asymmetry in the loss landscape that lets models acquire high-frequency skill compositions first, enabling more efficient learning of rare long-tail skills than uniform distr...
-
On the Emergence of Implicit Curriculum in RLVR Learning Dynamics
RLVR training on transformers for compositional tasks follows an implicit curriculum from easy to hard problems, with difficulty spectrum smoothness determining steady relay progress or grokking phase transitions.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.