How Transformers Learn Regular Language Recognition: A Theoretical Study on Training Dynamics and Implicit Bias

Jing Yang; Ruiquan Huang; Yingbin Liang

REVIEW 4 major objections 4 minor 1 cited by

How Transformers Learn Regular Language Recognition: A Theoretical Study on Training Dynamics and Implicit Bias

T0 review · 4 major / 4 minor · reviewed 2026-08-16 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper claims a one-layer transformer learns even-pairs and parity-check recognition in two provable phases: attention first makes data separable, then a linear head aligns to a max-margin direction and the loss decays sublinearly.

desk verdict New even-pairs training dynamics with a plausible two-phase story, but the Phase 2 proof has a load-bearing gap and the abstract overstates the rate. read the letter →

arxiv 2505.00926 v3 pith:4TTKOMB6 submitted 2025-05-02 cs.LG cs.CLstat.ML

Ruiquan Huang , Yingbin Liang , Jing Yang This is my paper · ORCID

classification cs.LGcs.CLstat.ML MSC 68T0768Q45

keywords trainingdynamicstransformerevenpairsparitycheckchain-of-thoughtimplicitbiasmax-marginregularlanguagerecognition

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper sets out to prove exactly how a one-layer transformer (softmax attention followed by a linear layer) learns two regular-language recognition tasks, "even pairs" and "parity check", when trained by gradient descent. The central thesis is that training splits into two phases: in the first, the attention matrix grows quickly and reshapes the data so that positive and negative examples become linearly separable; in the second, attention nearly freezes while the linear head grows logarithmically, turns toward a max-margin separating direction, and drives the logistic loss down sublinearly. The same two-phase picture is extended to parity check by chain-of-thought, in two ways: zero-shot truncated CoT inference on a transformer already trained for even pairs, and CoT training with an even-pairs regularization term. A sympathetic reader would care because this is one of the first convergence and implicit-bias analyses of jointly trained attention and linear layers on structural language tasks rather than feature-based classification.

What carries the argument

The argument rests on three mechanisms. First, a higher-order Taylor expansion of the logistic-loss gradient tracks the coupling between the attention and linear updates in Phase 1, where every token contributes to both positive and negative samples and gradients partly cancel. Second, the softmax scaling parameter $\lambda$ is load-bearing: because softmax is $1/\lambda$-Lipschitz, a large $\lambda$ suppresses attention drift in Phase 2, keeping $\|W_t-W_{t_0}\|\le O(1)$ while the linear layer keeps learning. Third, the implicit-bias view of Phase 2: once the attention outputs are separable, gradient descent on the linear layer is analyzed as margin maximization, converging in direction to the max-margin hyperplane defined by the frozen attention outputs. For parity check, the extra machinery is the truncated-CoT automaton, which reduces parity to repeated even-pairs comparisons, and teacher-forced CoT training with an even-pairs regularization loss that prevents vanishing gradients.

What would settle it

Run the even-pairs training of Section 4 with the stated schedule and measure, at $t_0$, the attention weights: the theorem requires $\varphi_1>1/L$ for positive samples and $\varphi_2>1/L$ for negative samples, and in Phase 2 requires $\|W_t-W_{t_0}\|\le O(1)$. If either fails for a range of $\eta$ and $\lambda$, or if the loss's decay exponent is clearly worse than the claimed sublinear rate, the central claim would be refuted; the same test applies to the parity CoT settings.

Watch

Extended reading notes

Core claim

On the paper's own terms, the discovery is Theorem 4.4 and Theorem 4.5 for even pairs, and Theorems 5.2 and 5.3 for parity check. Under a two-phase learning-rate schedule (attention updated with an extra factor $\lambda=\Omega(L_{\max}^2)$ until $t_0=O(1/(\eta L_{\max}))$, then standard GD), the attention layer at the end of Phase 1 concentrates on the first token in positive samples and on the second token in negative samples, which makes the attention outputs separable by $u=E_1^a+E_1^b-E_2^a-E_2^b$. In Phase 2 the attention parameters move by at most $O(1)$, the linear head satisfies $\|u_t\|\ge\Omega(\log t)$, its normalized direction approaches the max-margin solution $u^*_{\mathrm{EP}}$ (or $u^*_{\mathrm{CoT}}$ for parity), and the logistic loss satisfies $\mathcal{L}_t=O(L_{\max}\|u^*\|^2/(\eta\sqrt{t}))$; the abstract states the faster $O(1/t)$ rate. For parity check, a transformer trained only on even pairs can label parity by iterated truncated comparisons (truncated CoT), and when CoT training is regularized with even-pairs loss, the same two-phase convergence holds.

Load-bearing premise

The load-bearing premise is the purpose-built two-phase learning-rate schedule in which attention is updated with an extra factor $\lambda=\Omega(L_{\max}^2)$ until $t_0$ and with plain GD afterwards; the theorems do not apply to vanilla constant learning rate or to a small $\lambda$, and those regimes are only supported empirically.

Editorial extensions

If this is right

If the two-phase dynamics hold, a one-layer transformer trained on even pairs will, at the end of Phase 1, have attention that reliably distinguishes positive samples (first-token focus) from negative samples (second-token focus), so the learned representation is linearly separable and the final classifier is a max-margin separator of those representations.
The zero-shot result means the even-pairs transformer can be reused as a parity checker without retraining: iterating the even-pairs comparison along the sequence implements a two-state automaton and yields the parity label after $L-1$ steps.
The convergence rate $O(L_{\max}\|u^*\|^2/(\eta\sqrt{t}))$ (stated as $O(1/t)$ in the abstract) implies that, with sufficiently large $\lambda$, the logistic loss can be driven below any target $\epsilon$, so the trained transformer achieves near-zero classification error on the even-pairs and parity tasks.
In the CoT training approach, the even-pairs regularization is load-bearing: it steers the linear layer early so that the CoT data become separable, preventing the gradient vanishing observed when training on the CoT loss alone.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The schedule assumption is an idealization: the proof needs $\lambda=\Omega(L_{\max}^2)$ in Phase 1, but the paper's own constant-learning-rate experiments suggest the two-phase pattern is not an artifact of that schedule; proving the same statement for vanilla GD would be a natural next step, and the current theorems do not yet cover it.
The truncated-CoT construction suggests a broader principle: any transformer that learns pairwise token-equality can simulate a finite-state automaton by sliding comparisons, so the even-pairs result may serve as a building block for other regular languages, not just parity.
The discrepancy between the $O(1/t)$ rate in the abstract and the $O(1/\sqrt{t})$ rate in Theorem 4.5 points to a possible tightening: if the faster rate is true, it would come from a sharper Phase 2 alignment argument, and a direct check on the loss curve's exponent would settle which rate actually occurs in practice.
A testable extension is to track attention weights during training on sequences of varying maximum length; the theory predicts the Phase 1/Phase 2 boundary $t_0$ scales as $O(1/(\eta L_{\max}))$, so doubling $L_{\max}$ should roughly halve the number of Phase-1 steps.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Two things worth knowing about this one. The even-pairs analysis is a real step forward: it is the first to track joint linear-and-attention training on that task, and the two-phase story—attention grows first, then freezes while the linear layer aligns with a max-margin direction—is a natural and useful picture. The truncated-CoT transfer to parity is clever. The experiments are simple, but they do show the claimed token and attention patterns.

The soft spots are in the Phase 2 proof, not in the narrative. In Appendix B.2 the authors define T as a minimum of two terms and then assert the minimum equals the second term. That equality needs ||u*_EP|| ≤ O(λ^{1/3}), and no such bound is proved. The Phase 1 bounds only give lower bounds on attention-score gaps; those gaps, after softmax scaling by λ, look like they make the margin Ω(1/(λ L^4))-ish, which would force ||u*|| Ω(λ L^4). For λ = Ω(L^2) that violates the needed condition. So the min-term drop is not a detail; the phase-2 time horizon may be empty as stated. Separately, the paper claims ||W_t - W_t0|| ≤ O(1), but their own bound η²L²t²/λ at T = Θ(λ^{2/3}/(ηL)) gives O(λ^{1/3}), which for λ = Ω(L^2) is not O(1). That's a direct inconsistency.

The abstract also says O(1/t) loss decay while Theorem 4.5 proves O(Lmax||u*||²/(η√t)). That's an overclaim, though a smaller one.

Minor issues: the learning-rate schedule (ηλ for attention in phase 1, then η) is purpose-built; the authors say it approximates Adam, but the proof only covers that schedule. Appendix C compresses the parity phase-2 proof, and the direct-CoT gradient-vanishing claim is experimental without analysis. No code, but the experiments are easy to reproduce.

My read: this is a serious theory paper with a genuinely new result and a coherent story. The Phase 2 gap is load-bearing and needs to be fixed—either by proving a bound on ||u*_EP||, adjusting the schedule, or weakening the claims. But it's not a desk-reject; a serious referee should spend time on it. I'd send it to review with the gap flagged.

Referee Report

4 major / 4 minor

Summary. The paper studies a one-layer transformer (softmax attention followed by a linear head) trained by gradient descent on two binary-sequence tasks: 'even pairs' and 'parity check'. The main theoretical claim is that joint training of the attention matrix W and linear vector u exhibits two phases. In Phase 1, W grows rapidly and maps inputs to separable attention outputs; in Phase 2, W is nearly frozen, u grows logarithmically and aligns in direction with a max-margin separator u* of the Phase-1 attention outputs, and the logistic loss decays sublinearly. Parity check is addressed in two ways: by truncated chain-of-thought inference from a transformer already trained on even pairs, and by training a one-layer transformer on a CoT loss regularized by the even-pairs loss. The paper provides proofs in Appendices B and C and synthetic experiments in Section 6 and Appendix D.

Significance. If the central theorems were correct, this would be a valuable contribution: it would give one of the first joint training-dynamics analyses of attention and linear layers on structured language tasks, with explicit two-phase schedules, an implicit-bias characterization, and a CoT extension. The higher-order Taylor-expansion technique for Phase 1 and the use of max-margin analysis in Phase 2 are natural and potentially reusable. The paper also makes concrete falsifiable predictions about token-score growth, attention-score differences, and loss decay. However, the present manuscript does not establish the main Phase-2 theorem: a load-bearing parameter choice in the proof appears to be unjustified, and the attention-drift bound in Theorem 4.4 is contradicted by the paper's own estimates. Because the central two-phase claim is not proven, the contribution is not yet at the level claimed.

major comments (4)

[Appendix B.2, Parameter setup; Theorem 4.4] The definition of T is T = min( λ/(3∥u*_EP∥ηLmax), λ^{2/3}/(2^{2/3}ηLmax) ), and the text asserts that the minimum equals the second term. This requires ∥u*_EP∥ ≤ O(λ^{1/3}), but no such bound is proved. In fact, Theorem 4.1 gives attention-score gaps of order Ω(η²t²/L) at t0 = O(1/(ηLmax)), i.e., gaps of order Ω(1/L³). After softmax with scaling λ, the separating margin of the candidate vector ∑_w(E^w_1−E^w_2) is then of order Ω(1/(λ L⁴)), which forces ∥u*_EP∥ = Ω(λ L⁴). For λ = Ω(L²) this violates the required ∥u*_EP∥ ≤ O(λ^{1/3}); the first min-term dominates, T becomes O(1/(ηL⁵)) or smaller, and the interval t2≤t≤T can be empty or shorter than t0. The statement 'there exists t2=Ω(1) and T=... such that t2≤t≤T' then becomes vacuous. A valid proof needs a genuine upper bound on ∥u*_EP∥, or a different Phase-2 time horizon, neither of which is currently supplied.
[Appendix B.2 and Theorem 4.4] Theorem 4.4 claims ∥W_t−W_t0∥ ≤ O(1), but the proof's own bound is ∥W_t−W_t0∥ ≤ η²L_max²t²/λ, which at the stated T = Θ(λ^{2/3}/(ηLmax)) evaluates to O(λ^{1/3}), not O(1). Since λ = Ω(L²), this is inconsistent with the theorem as written. If one instead lets the first min-term dominate T, then T may be too small for the alignment time t2 in Lemma B.6, so the attention-stability claim and the margin-alignment claim cannot both be supported by the current proof.
[Abstract, Introduction, Section 4.2, Theorems 4.5 and 5.3] The abstract and introduction state that the loss decreases at rate O(1/t), but Theorem 4.5 and Theorem 5.3 prove only O(Lmax∥u*∥²/(η√t)). The faster O(1/t) rate is not derived anywhere in the paper. The sentence after Theorem 4.5, which concludes a loss of O(η^{1/2}/λ^{1/3}) at t=T, also needs a derivation; substituting T = Θ(λ^{2/3}/(ηLmax)) into the theorem gives a different expression unless additional assumptions on ∥u*_EP∥ are made. The advertised rate should be corrected to match the proven statement.
[Appendix C, Theorem 5.1] The Phase-1 proof for parity check is not fully supplied: after the initialization lemma, the text says 'For the rest of the proof, the steps follow the same as in Appendix B' and then states Theorem C.3. Because the parity loss includes both LCoT and LReg, and because the attention-score inequalities for L≥L0 involve a new reference position ℓ0 = L−L0+1, the induction is not literally identical to the even-pairs case. In particular, the cancellations between positive and negative samples need to be checked for the CoT-labeled lengths. This is load-bearing for Theorems 5.2 and 5.3, so the proof should either be written out or the missing steps explicitly identified.

minor comments (4)

[Section 6] The main experiments use λ=2 with Lmax=6, while Theorem 4.1 requires λ=Ω(Lmax²). Please clarify whether these plots are meant only as qualitative illustrations, or add experiments in the theoretical parameter regime.
[Section 3 and Appendix A] There are several typos and minor grammatical slips: 'Frobenious' should be 'Frobenius', 'scaler' should be 'scalar', and the inner-product definition says 'Trace(AB⊤) Trace(AB⊤)'.
[Theorem B.3] The last lower bound in Theorem B.3 is written as Ω((1+η³t²/(λL³))^t · η⁴/(λL)), which as displayed grows exponentially in t and is inconsistent with the later use of the bound. Please correct the formula or the exponent.
[Section 5.1, Algorithm 1] The line 'Predictyt = TθT (X)' has a typo in the subscript; it should be T_θ(X). The notation for the appended token y_t is also overloaded with the label y_n elsewhere, which is confusing.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the derivation is a forward gradient-descent analysis, with u* used only as an analysis target.

full rationale

The paper's derivation chain is a forward gradient-descent analysis rather than a fit or a renaming. Phase 1 (Theorem 4.1) proves the growth of token and attention scores by induction from the stated two-phase update rule, and Phase 2 (Theorem 4.4 and Theorem 4.5) applies a Soudry-style implicit-bias argument to the attention outputs at time t0 while separately controlling attention drift using the softmax Lipschitz bound (Lemma A.1). The max-margin vector u*_EP is defined from the Phase-1 attention outputs solely as an analysis target; it is never used as a training signal or as a parameter in the updates, so the alignment claim is a derived property rather than a self-definition. The parity-check results (Theorems 5.1-5.3) reduce to the same separability and implicit-bias argument, and the CoT construction is an explicit algorithmic use of the even-pairs solution, not a renamed restatement of it. Citations to the authors' prior next-token prediction work are for reparameterization conventions and background, while the load-bearing implicit-bias result is externally established (Soudry et al.); hence there is no load-bearing self-citation. The only flagged issue is a correctness gap rather than circularity: in Appendix B.2 the time horizon T = min(lambda/(3||u*_EP|| eta Lmax), lambda^{2/3}/(2^{2/3} eta Lmax)) is asserted to equal the second term without proving ||u*_EP|| = O(lambda^{1/3}), so the Phase-2 interval may be empty under the stated parameter regime; additionally, the abstract's O(1/t) loss rate is stronger than the proved O(1/sqrt(t)) rate. These are internal proof concerns and do not make the theorem equal to its inputs by construction.

Assumptions & free parameters 4 free parameters · 6 assumptions · 0 invented entities

Central claim rests on idealized assumptions: orthogonal positional embeddings, complete balanced data, zero initialization, and a purpose-built learning-rate schedule. No new physical or model entities are introduced. The main hyperparameters (lambda, eta, t0) are chosen by hand, not fit to data, so the circularity burden is low.

free parameters (4)

attention scale lambda = Omega(Lmax^2) in theorems; lambda=2 in main experiments
Chosen by hand; large lambda is used to keep softmax Lipschitz and attention drift small, making the two-phase proof work. Not learned from data.
learning rate eta = O(min{1/Lmax, 1/lambda^(2/3)}) in theorems; eta=0.1 in experiments
Hyperparameter range chosen to make the Taylor expansions and phase separation valid; experiments use a value within the range.
phase length t0 = O(1/(eta Lmax)) in theorems; t0=100 in experiments
Separates Phase 1 from Phase 2; not fitted to data, but a hand-chosen schedule point.
CoT sequence length L0 = L0=4 in experiments
Determines the parity-task sequence lengths in Approach 2; dataset construction parameter, not fitted.

assumptions (6)

domain assumption Token embeddings are orthogonal canonical basis vectors: E^a_l=e_{2l-1}, E^b_l=e_{2l}, with dimension d at least 2Lmax.
Invoked in Section 3 'Embedding strategy'; Lemma B.1's symmetry properties and all token-score decompositions depend on this.
domain assumption Training data is the complete set of binary sequences of lengths 1 through Lmax, with equal weight 1/|I_L| per length.
Section 3 'Learning objective'. The length-1 positive samples create the initial first-token bias that seeds Phase 1; without this exact weighting the proof's initialization step fails.
ad hoc to paper Zero initialization theta0=0 and the two-phase learning-rate schedule for W (eta*lambda before t0, eta after).
Section 3 update rules. This schedule is not standard GD; it is justified only as an 'approximation' of Adam, and the theorems are stated for it.
ad hoc to paper For Approach 2, the training loss is LParity=LCoT+LReg, including the even-pairs regularization.
Section 5.2. Added because direct CoT training is reported to encounter gradient vanishing; this auxiliary task is not part of the parity objective itself.
standard math Softmax is (1/lambda)-Lipschitz and the logistic loss admits the Taylor expansion in Eq. (2).
Used throughout Appendix A and B as Lemma A.1 and Eq. (2), inherited from Gao and Pavel (2017).
standard math Implicit-bias and max-margin convergence background for logistic loss on separable data.
The Phase 2 analysis in Appendix B.2 builds on Soudry et al. (2018) style arguments; the paper does not fully re-derive all background.

how reviews work

0 comments

Cite this review

Pith. "Pith review of How Transformers Learn Regular Language Recognition: A Theoretical Study on Training Dynamics and Implicit Bias." pith.science (2026). https://pith.science/paper/4TTKOMB6

@misc{pith2026250500926,
  author       = {Pith},
  title        = {Pith review of: How Transformers Learn Regular Language Recognition: A Theoretical Study on Training Dynamics and Implicit Bias},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/4TTKOMB6}},
  note         = {Machine review of arXiv:2505.00926}
}

abstract

Language recognition tasks are fundamental in natural language processing (NLP) and have been widely used to benchmark the performance of large language models (LLMs). These tasks also play a crucial role in explaining the working mechanisms of transformers. In this work, we focus on two representative tasks in the category of regular language recognition, known as `even pairs' and `parity check', the aim of which is to determine whether the occurrences of certain subsequences in a given sequence are even. Our goal is to explore how a one-layer transformer, consisting of an attention layer followed by a linear layer, learns to solve these tasks by theoretically analyzing its training dynamics under gradient descent. While even pairs can be solved directly by a one-layer transformer, parity check need to be solved by integrating Chain-of-Thought (CoT), either into the inference stage of a transformer well-trained for the even pairs task, or into the training of a one-layer transformer. For both problems, our analysis shows that the joint training of attention and linear layers exhibits two distinct phases. In the first phase, the attention layer grows rapidly, mapping data sequences into separable vectors. In the second phase, the attention layer becomes stable, while the linear layer grows logarithmically and approaches in direction to a max-margin hyperplane that correctly separates the attention layer outputs into positive and negative samples, and the loss decreases at a rate of $O(1/t)$. Our experiments validate those theoretical results.

Figures

Figures reproduced from arXiv: 2505.00926 by the authors.

**Figure 1.** An illustration of CoT on input abb, where L0 = 3. Training design. To train a transformer to learn each step 1 ≤ t ≤ L0 − 1 of CoT, our dataset should be labeled to compare the token wL0+t−1 (last token of the input sequence of the current CoT step) and wt, and such a label is used to train (supervise) the transformer to conduct the t-th step of CoT correctly. Thus, to train the t-th step of CoT, we use the set IL… view at source ↗

**Figure 2.** Results of one-layer transformer on even pairs. From the left to the right: (1) Loss decay over training. (2) Token scores at first three positions. (3) Attention scores in length-3 sequences [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗

**Figure 3.** Results of one-layer transformer on parity check. From the left to the right: (1) Loss decay over training. (2) Token scores at first three positions. (3) Attention scores in length-5 sequences. have ∥ut∥ ≥ Ω(log t), and D ut ∥ut∥ , u ∗ CoT ∥u ∗ CoT ∥ E ≥ 1 − 1 2 1 6∥u ∗ CoT ∥ − 1 ∥ut∥ 2 . Moreover, we have ∥Wt − Wt0 ∥ ≤ O(1). The above theorem also implies that the total loss converges sublinearly, which further… view at source ↗

Figures from the paper (4 more)

**Figure 4.** Figure 4: Training dynamics of learning Even pairs when λ = 10 [PITH_FULL_IMAGE:figures/full_fig_p034_4.png]

**Figure 5.** Figure 5: Training dynamics of learning Even pairs when λ = 18 = L 2 max/2 [PITH_FULL_IMAGE:figures/full_fig_p034_5.png]

**Figure 6.** Figure 6: Training dynamics of training transformer on even pairs using vanilla GD (constant learning rate) and λ = 2 [PITH_FULL_IMAGE:figures/full_fig_p034_6.png]

**Figure 7.** Figure 7: Results of nanoGPT, trained on ’shakespeare’ dataset. Configuration: block-size=64, batch-size=12, n-layer=4, n-head=4, n-embd=128 34 [PITH_FULL_IMAGE:figures/full_fig_p034_7.png]

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Transformers with RL or SFT Provably Learn Sparse Boolean Functions, But Differently
cs.LG 2025-11 conditional novelty 6.0 of 10

Under hand-designed masks and task-specific activations, RL fine-tuning learns a k-sparse Boolean reasoning chain in one gradient update while SFT learns it one CoT step per update.

Reference graph

Works this paper leans on

30 extracted references · 5 canonical work pages · cited by 1 Pith paper

[3]

Training dynamics of multi-head softmax attention for in-context learning: Emergence, convergence, and optimality

Chen, S., Sheen, H., Wang, T., and Yang, Z. Training dynamics of multi-head softmax attention for in-context learning: Emergence, convergence, and optimality. arXiv preprint arXiv:2402.19442,

arXiv
[4]

Transformers implement functional gradient descent to learn non-linear functions in context

Cheng, X., Chen, Y ., and Sra, S. Transformers implement functional gradient descent to learn non-linear functions in context. arXiv preprint arXiv:2312.06528,

arXiv
[5]

and Cholak, P

Chiang, D. and Cholak, P. Overcoming a theoretical limita- tion of self-attention. arXiv preprint arXiv:2202.12172,

arXiv
[7]

On the optimization and generalization of multi-head attention

Deora, P., Ghaderi, R., Taheri, H., and Thrampoulidis, C. On the optimization and generalization of multi-head attention. arXiv preprint arXiv:2310.12680,

arXiv
[8]

Bert: Pre-training of deep bidirectional transformers for lan- guage understanding

Devlin, J., Chang, M.-W., Lee, K., and Toutanova, K. Bert: Pre-training of deep bidirectional transformers for lan- guage understanding. arXiv preprint arXiv:1810.04805,

arXiv
[10]

and Pavel, L

Gao, B. and Pavel, L. On the properties of the softmax func- tion with application in game theory and reinforcement learning. arXiv preprint arXiv:1704.00805,

arXiv
[12]

Non-asymptotic conver- gence of training transformers for next-token prediction

Huang, R., Liang, Y ., and Yang, J. Non-asymptotic conver- gence of training transformers for next-token prediction. In Proc. Advances in Neural Information Processing Sys- tems (NeurIPS), 2024a. 9 Training Dynamics of Transformers Huang, Y ., Cheng, Y ., and Liang, Y . In-context convergence of transformers. arXiv preprint arXiv:2310.05249,

arXiv
[13]

How transform- ers learn diverse attention correlations in masked vision pretraining

Huang, Y ., Wen, Z., Chi, Y ., and Liang, Y . How transform- ers learn diverse attention correlations in masked vision pretraining. arXiv preprint arXiv:2403.02233, 2024b. Ji, Z. and Telgarsky, M. Characterizing the implicit bias via a primal-dual analysis. In Algorithmic Learning Theory, pp. 772–804. PMLR,

arXiv

Show all 30 references

[15]

Accessed: 2025-04-28. Kim, J. and Suzuki, T. Transformers learn nonlinear fea- tures in context: Nonconvex mean-field dynamics on the attention landscape. arXiv preprint arXiv:2402.01258, 2024a. Kim, J. and Suzuki, T. Transformers provably solve par- ity efficiently with chain...

2025 arXiv
[16]

A theoretical understanding of shallow vision transformers: Learning, generalization, and sample complexity

Li, H., Wang, M., Liu, S., and Chen, P.-Y . A theoretical understanding of shallow vision transformers: Learning, generalization, and sample complexity. arXiv preprint arXiv:2302.06015,

arXiv
[17]

Training nonlinear transformers for chain-of-thought inference: A theoretical generalization analysis

Li, H., Wang, M., Lu, S., Cui, X., and Chen, P.-Y . Training nonlinear transformers for chain-of-thought inference: A theoretical generalization analysis. arXiv preprint arXiv:2410.02167, 2024a. Li, Y ., Huang, Y ., Ildiz, M. E., Rawat, A. S., and Oymak, S. Mechanics of next t...

arXiv
[18]

B., and Ma, T

Mahankali, A., Hashimoto, T. B., and Ma, T. One step of gradient descent is provably the optimal in-context learner with one layer of linear self-attention. arXiv preprint arXiv:2307.03576,

arXiv
[19]

and Sabharwal, A

Merrill, W. and Sabharwal, A. The expressive power of transformers with chain of thought. arXiv preprint arXiv:2310.07923,

arXiv
[20]

Merrill, W., Ramanujan, V ., Goldberg, Y ., Schwartz, R., and Smith, N. A. Effects of parameter norm growth during transformer training: Inductive bias from gradi- ent descent. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pp. 1766–1781,

2021
[22]

and Sato, I

Sakamoto, K. and Sato, I. Benign or not-benign overfitting in token selection of attention mechanism. arXiv preprint arXiv:2409.17625,

arXiv
[23]

Sheen, H., Chen, S., Wang, T., and Zhou, H. H. Implicit regularization of gradient flow on one-layer softmax at- tention. arXiv preprint arXiv:2403.08699,

arXiv
[24]

A., Li, Y ., Thrampoulidis, C., and Oymak, S

10 Training Dynamics of Transformers Tarzanagh, D. A., Li, Y ., Thrampoulidis, C., and Oymak, S. Transformers as support vector machines. arXiv preprint arXiv:2308.16898, 2023a. Tarzanagh, D. A., Li, Y ., Zhang, X., and Oymak, S. Max- margin token selection in attention mechan...

arXiv
[25]

Tian, Y ., Wang, Y ., Chen, B., and Du, S. S. Scan and snap: Understanding training dynamics and token composition in 1-layer transformer. Advances in Neural Information Processing Systems, 36:71911–71947, 2023a. Tian, Y ., Wang, Y ., Zhang, Z., Chen, B., and Du, S. Joma: Demy...

arXiv
[26]

Implicit bias and fast convergence rates for self-attention

Vasudeva, B., Deora, P., and Thrampoulidis, C. Implicit bias and fast convergence rates for self-attention. arXiv preprint arXiv:2402.05738,

arXiv
[27]

From sparse dependence to sparse attention: Unveiling how chain-of- thought enhances transformer sample efficiency

Wen, K., Zhang, H., Lin, H., and Zhang, J. From sparse dependence to sparse attention: Unveiling how chain-of- thought enhances transformer sample efficiency. arXiv preprint arXiv:2410.05459,

arXiv
[28]

Train- ing dynamics of transformers to recognize word co- occurrence via gradient flow analysis

Yang, H., Kailkhura, B., Wang, Z., and Liang, Y . Train- ing dynamics of transformers to recognize word co- occurrence via gradient flow analysis. In Proc. Advances in Neural Information Processing Systems (NeurIPS) , 2024a. Yang, T., Huang, Y ., Liang, Y ., and Chi, Y . In-co...

arXiv
[29]

Auxiliary Lemmas and Equations Lemma A.1 (Gao & Pavel (2017))

11 Training Dynamics of Transformers A. Auxiliary Lemmas and Equations Lemma A.1 (Gao & Pavel (2017)). The softmax function with scaling factorλ is 1 λ-Lipschitz continuous. Mathematically, we have ∥ϕ(x/λ)−ϕ(y/λ)∥≤ 1 λ∥x−y∥. By Lemma A.1 andφ(n,t) ℓ = exp ⟨x(n) ℓ ,Wtx(n) L ⟩/λ...

2017
[30]

This can be done by noting that⟨u2,Ew 1 −E2 ℓ⟩≥ Ω(η) forℓ̸=ℓ0

32 Training Dynamics of Transformers Finally, we aim to show that at time stept = 3, the attention layer also distinguishes between first and other tokens. This can be done by noting that⟨u2,Ew 1 −E2 ℓ⟩≥ Ω(η) forℓ̸=ℓ0. More importantly,φ(+,2) 1 >φ (−,2) 1 Specifically, we have...

2023
[2018]

L., Srebro, N., and Hu, W

Frei, S., Vardi, G., Bartlett, P. L., Srebro, N., and Hu, W. Implicit bias in leaky relu networks trained on high- dimensional data. arXiv preprint arXiv:2210.07082 ,

arXiv
[2019]

Nichani, E., Damian, A., and Lee, J. D. How transform- ers learn causal structure with gradient descent. arXiv preprint arXiv:2402.14735,

arXiv
[2020]

and Rofin, M

Hahn, M. and Rofin, M. Why are sensitive functions hard for transformers? arXiv preprint arXiv:2402.09963,

arXiv
[2021]

Unveil benign overfitting for transformer in vision: Train- ing dynamics, convergence, and generalization

Jiang, J., Huang, W., Zhang, M., Suzuki, T., and Nie, L. Unveil benign overfitting for transformer in vision: Train- ing dynamics, convergence, and generalization. arXiv preprint arXiv:2409.19345,

arXiv
[2022]

Superiority of multi-head attention in in-context linear regression

Cui, Y ., Ren, J., He, P., Tang, J., and Xing, Y . Superiority of multi-head attention in in-context linear regression. arXiv preprint arXiv:2401.17426,

arXiv
[2023]

and Li, Y

Chen, S. and Li, Y . Provably learning a multi-head attention layer. arXiv preprint arXiv:2402.04084,

arXiv
[2024]

On the abil- ity and limitations of transformers to recognize formal languages

Bhattamishra, S., Ahuja, K., and Goyal, N. On the abil- ity and limitations of transformers to recognize formal languages. arXiv preprint arXiv:2009.11264,

2009 arXiv

Pith tools

Reviewed August 16, 2026 · model on record in the stance chip above.

[1] [3]

Training dynamics of multi-head softmax attention for in-context learning: Emergence, convergence, and optimality

Chen, S., Sheen, H., Wang, T., and Yang, Z. Training dynamics of multi-head softmax attention for in-context learning: Emergence, convergence, and optimality. arXiv preprint arXiv:2402.19442,

arXiv

[2] [4]

Transformers implement functional gradient descent to learn non-linear functions in context

Cheng, X., Chen, Y ., and Sra, S. Transformers implement functional gradient descent to learn non-linear functions in context. arXiv preprint arXiv:2312.06528,

arXiv

[3] [5]

and Cholak, P

Chiang, D. and Cholak, P. Overcoming a theoretical limita- tion of self-attention. arXiv preprint arXiv:2202.12172,

arXiv

[4] [7]

On the optimization and generalization of multi-head attention

Deora, P., Ghaderi, R., Taheri, H., and Thrampoulidis, C. On the optimization and generalization of multi-head attention. arXiv preprint arXiv:2310.12680,

arXiv

[5] [8]

Bert: Pre-training of deep bidirectional transformers for lan- guage understanding

Devlin, J., Chang, M.-W., Lee, K., and Toutanova, K. Bert: Pre-training of deep bidirectional transformers for lan- guage understanding. arXiv preprint arXiv:1810.04805,

arXiv

[6] [10]

and Pavel, L

Gao, B. and Pavel, L. On the properties of the softmax func- tion with application in game theory and reinforcement learning. arXiv preprint arXiv:1704.00805,

arXiv

[7] [12]

Non-asymptotic conver- gence of training transformers for next-token prediction

Huang, R., Liang, Y ., and Yang, J. Non-asymptotic conver- gence of training transformers for next-token prediction. In Proc. Advances in Neural Information Processing Sys- tems (NeurIPS), 2024a. 9 Training Dynamics of Transformers Huang, Y ., Cheng, Y ., and Liang, Y . In-context convergence of transformers. arXiv preprint arXiv:2310.05249,

arXiv

[8] [13]

How transform- ers learn diverse attention correlations in masked vision pretraining

Huang, Y ., Wen, Z., Chi, Y ., and Liang, Y . How transform- ers learn diverse attention correlations in masked vision pretraining. arXiv preprint arXiv:2403.02233, 2024b. Ji, Z. and Telgarsky, M. Characterizing the implicit bias via a primal-dual analysis. In Algorithmic Learning Theory, pp. 772–804. PMLR,

arXiv