Research map / Architectures and efficiency / Attention and transformers
How Transformers Learn Regular Language Recognition: A Theoretical Study on Training Dynamics and Implicit Bias
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Theoretically analyzes gradient-descent training dynamics of a one-layer transformer (softmax attention + linear layer) on the even pairs and parity check regular-language tasks, showing two-phase dynamics with max-margin implicit bias, and proposes truncated and teacher-forced CoT for parity.
Problem
Understanding how transformers are trained to recognize regular languages (even pairs and parity check), where training dynamics and implicit bias are largely unstudied theoretically, and parity check is hard without chain-of-thought.
Approach
Jointly analyzes gradient descent on attention and linear layers of a one-layer transformer for even pairs, showing a rapid-growth phase producing separable attention outputs followed by convergence of the linear layer in direction to a max-margin hyperplane with O(1/t) loss decay; extends to parity check via zero-shot truncated CoT inference from the even-pairs model or CoT training under teacher
Key results
- For even pairs, the loss decays at O(1/t) (stated as O(L_max||u*||^2/(eta sqrt t)) bound on the loss) after a two-phase training process, with the linear layer converging in direction to the max-margin hyperplane.
- Zero-shot truncated CoT inference with an even-pairs-trained transformer solves parity check without additional training.
- Experiments with L_max=6, L_0=4, eta=0.1, lambda=2 on synthetic data validate the phase-wise token score and attention dynamics.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Train the one-layer transformer jointly on attention and linear layers for even pairs | One-layer transformer · Even pairs | classification | Helped |
| Continue training the linear layer after the attention outputs become separable | One-layer transformer · Even pairs | classification margin | Helped |
| Use the even-pairs-trained transformer with truncated CoT at inference | One-layer transformer trained on even pairs · Parity check | classification | Helped |
| Add even-pairs regularization to teacher-forced CoT training | One-layer transformer trained for parity check · Parity check via CoT | gradient behavior | Helped |
| Remove the even-pairs regularization loss from teacher-forced CoT training (ablation) | One-layer transformer trained for parity check · Parity check via CoT | gradient behavior | Hurt |
| Use a two-phase gradient-descent schedule for joint attention and linear-layer training | One-layer transformer · Even pairs | loss | Helped |
| Use teacher-forced CoT with even-pairs regularization | One-layer transformer · Parity check via CoT | classification | Helped |
Surprising findings
- A transformer trained only on even pairs can solve parity check zero-shot via truncated CoT at inference time.
Limitations
- Analysis restricted to a one-layer transformer with reparameterized attention and zero initialization.
- Experiments are small-scale synthetic (L_max=6) and do not test larger models or natural language.
Experimental setup
Datasets: synthetic binary sequences over {a,b} for even pairs and parity check
Metrics: logistic loss token score dynamics attention weights alignment of linear layer with max-margin direction
Builds on: chain-of-thought max-margin implicit bias of gradient descent
Closest papers by meaning
- Training Dynamics of Transformers to Recognize Word Co-occurrence via Gradient Flow Analysis (NeurIPS 2024 · similarity 0.88)
- Unveiling Induction Heads: Provable Training Dynamics and Feature Learning in Transformers (NeurIPS 2024 · similarity 0.88)
- Training Neural Networks as Recognizers of Formal Languages (ICLR 2025 · similarity 0.88)
- How Do Nonlinear Transformers Learn and Generalize in In-Context Learning? (ICML 2024 · similarity 0.87)
- Transformers Get Stable: An End-to-End Signal Propagation Theory for Language Models (ICML 2024 · similarity 0.87)
- How Transformers Learn Structured Data: Insights From Hierarchical Filtering (ICML 2025 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.