REVIEW 7 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
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 7 Pith papers
-
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.
-
Learning Compositional Functions with Transformers from Easy-to-Hard Data
A transformer with O(log k) layers provably learns the k-fold permutation composition task in poly(N,k) samples with curriculum or mixed easy-to-hard data, despite an SQ lower bound requiring N^{Omega(k)} samples on h...
-
What makes a good feedforward computational graph?
The authors define mixing time and minimax fidelity for feedforward graphs, use them to design a recursive sparse graph (FS) with polylogarithmic mixing time, and show it matches dense attention on parity and retrieval tasks.
-
Metastable Dynamics of Chain-of-Thought Reasoning: Provable Benefits of Search, RL and Distillation
In a metastable Markov model of reasoning, search and RL improve hitting times by boosting rare hard edges, and distilling clusters into a meta-chain preserves escape dynamics.
-
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...
-
Towards Theoretical Understanding of Transformer Test-Time Computing: Investigation on In-Context Linear Regression
A one-layer linear-attention transformer implementing noisy gradient descent gives provable bounds showing linear noise plus ensembling avoids label-noise overfitting, and majority voting beats greedy decoding in spar...
-
RACE-Align: Retrieval-Augmented and Chain-of-Thought Enhanced Preference Alignment for Large Language Models
RACE-Align generates preference pairs from RAG-grounded chain-of-thought answers and applies DPO to align a 1.7B model, showing improved reasoning scores in TCM QA but lacking statistical support.
Discussion (0). Continue with ORCID to comment.