Transformers Provably Solve Parity Efficiently with Chain of Thought

Juno Kim, Taiji Suzuki

This work provides the first theoretical analysis of training transformers to solve complex problems by recursively generating intermediate states, analogous to fine-tuning for cha…