Incremental Learning of Sparse Attention Patterns in Transformers

• The task tests whether heads coordinate by specializing from the start or by competing first for the statistically dominant signal.The question matters for understanding how structured attention patterns emerge during ordinary training.Source: §1 · p. 1
• Heads first converge on the most statistically important sparse pattern, then specialize through offshooting while other heads compensate.This competitive-to-cooperative transition is the paper’s central head-level finding.Source: §1 · pp. 2–3
• A high-order Markov-chain task requires transformers to combine information from multiple past-position groups with different statistical importance.Each group is mapped to prediction logits by an associated feature matrix.Source: §1 · p. 2, Figure 1 · p. 2
• A simplified regression model and population gradient-flow analysis capture shared convergence to a dominant pattern, followed by offshooting and compensation.Near-symmetric heads evolve as a coupled system in the analysis.Source: §1 · pp. 2–3
• The staged dynamics already arise in a single self-attention layer, making sparse attention formation a mechanism for positional incremental learning.The paper contrasts this with prior in-context Markov-chain settings involving more intricate multi-layer circuits.Source: §1 · p. 2
• In low-data regimes, early stopping favors simpler effective predictors that use only the most important positions.The paper suggests this links stage-wise learning with the effective complexity selected during training.Source: §1 · p. 3

2.1 Markov Chains with Importance Structure

• The task predicts the next token from groups of past positions paired with feature matrices of differing statistical importance.The groups partition the past positions; contiguous groups are one illustrative choice, and the task is not identifiable because the same generation rule admits multiple decompositions.Source: §2.1 · p. 3

2.2 Representing the Task with Sparse Attention

• A multi-head construction assigns each head a group's sparse attention pattern to copy relevant past tokens and a value map to apply its feature matrix.Sparse attention is the limiting case where attention mass concentrates on selected positions and vanishes elsewhere; finite logit gaps approximate it.Source: §2.2 · pp. 3–4

2.3 Transformers Learn Incrementally

• Training proceeds from overlapping attention on the most important positions to head specialization, with stages acquiring sparse patterns and ultimately integrating all positions.The task admits multiple decompositions, yet training consistently recovers a sparse, disjoint representation.Source: §2.3 · p. 5, Figure 2 · p. 5
• In function space, the full-context transformer approaches restricted-context models with c = 4, 8, then 12, learning each attention pattern and feature matrix together.The contexts correspond to access to I(1), then I(1) ∪ I(2), then all relevant positions; comparisons to ground-truth predictors show the same incremental pattern.Source: §2.3 · p. 5, Figure 3 · p. 6

2.4 Ablation Studies

• Removing components absent from the idealized construction, individually or together, does not significantly alter the incremental dynamics.The simplifications include layer normalization and residual connections, and reducing K⊤Q to a single matrix A.Source: §2.4 · p. 5
• Smaller initialization slows learning, zero initialization stalls after one pattern, and removing importance ordering collapses three stages to two.With m = 1.3 or 1.5, three stages emerge; larger importance gaps make them more clearly separated.Source: §2.4 · p. 6, Figure 4 · p. 6
• Competitive-to-cooperative dynamics persist across varied orderings, attention weights, interval overlap, initialization, optimizers, and head counts.With overlapping intervals, multiple sparse solutions may exist, and initialization and feature matrices can influence which is selected.Source: §2.4 · p. 7

2.5 Dataset Size and Effective Complexity

• Smaller datasets reach fewer training stages; early-stopped models in low-data regimes approach simpler predictors using only the most important positions.With 600 samples, attention concentrates on the first two patterns and gives minimal weight to the third, even when its feature matrix overfits training noise.Source: §2.5 · p. 7

3.1 The Regression Model

• The regression surrogate uses position-only attention scores and mean-squared loss; isotropic covariance and orthogonal feature matrices make its analysis tractable.Relaxing these assumptions would replace scalar feature ordering with an ordering based on the data covariance and target tensor.Source: §3.1 · p. 8
• Proposition 1 recasts the regression dynamics as gradient flow for a tensor-factorization problem, whose simulations recapitulate incremental learning.For simplicity, the analysis sets each positional group to size one.Source: §3.1 · pp. 8–9

3.2 Coupled Dynamics Describe the Competitive Phase

• Under an ordering condition, coupled heads converge to a fixed point; small deviations from symmetric initialization remain bounded for a controllable finite time.The initialization therefore influences how long heads remain coupled before they may diverge.Source: §3.2 · p. 9

3.3 Cooperation After Competition

• After the first feature is learned, an offshooting head can move toward the second while the ensemble’s value matrices compensate for an unnecessary prediction term.Theorem 4 requires an initialization that decreases loss beyond the first saddle; a small perturbation toward the second feature can suffice.Source: §3.3 · pp. 10–11
• The analysis extends specialization to later features, treating earlier heads as approximately fixed and bounding deviations from cooperative dynamics for a controlled time.A minimal-transformer classification experiment shows a qualitatively similar compensatory pattern, but the two settings differ in loss, parameterization, and timescale.Source: §3.3 · pp. 10–11

Incremental learning

• Incremental-learning studies span linear and ReLU models and transformer tasks, while dataset size affects hierarchy order in random probabilistic context-free grammars.The cited grammar work connects that data-dependent progression to effective model complexity (Cagnetta & Wyart, 2024; Cagnetta et al., 2025).Source: §4 · p. 11

n-gram models

• Prior n-gram task studies report staged sub-n-gram solutions, while standard n-gram models lack the hierarchical abstractions characteristic of natural language.This task adds an importance hierarchy over positional features, leaving richer abstraction and composition outside its scope (Edelman et al., 2024; Varre et al., 2025; Wu et al., 2022; 2025).Source: §4 · p. 12

Attention dynamics

• Attention analyses often use simplified parameterizations; a related position-only-softmax study considers one head, while multi-head dynamics have been less developed.The single-head setting studies escape from uniform attention via a local Taylor approximation (Zucchet et al., 2026).Source: §4 · p. 12

Discussion

• Here, symmetric heads sharing the same input and output domain compete for a dominant sparse pattern, then specialize sequentially as other heads compensate through value matrices.The discussion distinguishes this from competition between algorithmic circuits (Reddy, 2024; Park et al., 2025) and argues that analyzing attention and value dynamics jointly preserves these structural signatures.Source: §4 · p. 12

5 Conclusion

• The paper concludes that stages acquire sparse attention patterns in statistical-importance order through a transition from shared focus to head specialization.Its simplified architecture and regression objective yield surrogate differential equations that capture the qualitative staged dynamics.Source: §5 · p. 12

Organization of the Appendix

• Appendices A–E cover task non-identifiability, theoretical proofs, relaxed theorem initializations, regression-flow simulations, and experiment details.The appendix roadmap assigns those topics respectively to Appendices A, B, C, D, and E.Source: Organization of the Appendix · p. 20
• Appendix F adds experiments on data regime, importance and interval structure, model depth, and optimizer.The listed variations include infinite data, weight decay, reverse ordering, overlapping intervals, two-block transformers, and SGD.Source: Organization of the Appendix · p. 20

Appendix A Identifiability

• Different choices of positional partitions and feature matrices can induce the same conditional distribution, so the generating representation is not unique.The ambiguity extends beyond simple permutations to decompositions with overlapping groups and attention weights spread across positions.Source: Appendix A · p. 20
• Jointly permuting the partition-feature pairs leaves the data-generation sum unchanged.This is a trivial source of non-identifiability.Source: Appendix A · p. 20
• Despite equivalent non-sparse representations, training consistently recovers a sparse, disjoint decomposition.Source: Appendix A · p. 20

Appendix B Deferred Proofs

• Proposition 1 states that the gradient flow of the loss in Equation (3) is equivalent to the dynamics of another loss, L(θ).The supplied passage does not give the full expression for L(θ).Source: Appendix B · p. 21
• The derivation computes derivatives with respect to the value parameters and attention scores, then writes the resulting gradient-flow dynamics.It also recasts the flow as gradient descent on a loss.Source: Appendix B · p. 21
• The appendix introduces auxiliary lemmas about the kernel of Π(s) and vectors ordered consistently with a simplex vector s.The supplied passages state the lemma setups but omit their complete conclusions.Source: Appendix B · p. 22

B.1 Boundedness

• Theorem 2 bounds deviations in V_k and s_k from the symmetric system by ϵe^(c1t).The stated bounds are ∥V_k(t) − V(t)∥_F ≤ ϵe^(c1t) and ∥s_k(t) − s(t)∥_2 ≤ ϵe^(c1t).Source: §B.1 · p. 22
• A non-decreasing Lyapunov function constrains V: it cannot exceed the optimal value for a given s without making the function decrease.The optimal value is described as Gs h∥s∥² in norm.Source: §B.1 · p. 22
• A similar argument to Theorem 2 gives an upper bound on ϕ and boundedness of the flow, and shows the noise process grows as O(ϵ), with ϵ the same quantity as in Theorem 2.Source: §B.1 · p. 24

B.2 Competitive Phase

• Under Theorem 1’s initialization condition, the competitive-phase flow converges to a stationary point, with the maximal alignment among the listed feature directions belonging to the first feature.The proof uses a forward-invariant set to establish the convergence result.Source: §B.2 · pp. 24–25

B.3 Cooperation Phase

• The cooperative-phase analysis first establishes convergence for the second head, then extends the analysis to arbitrary phases.The appendix describes this progression as the route to its remaining results.Source: §B.3 · p. 25, §B.3.1 · p. 27

B.3.1 Convergence of the Second Head

• With the stated initialization conditions, the second head’s value matrix and attention pattern converge to the fixed point given in Theorem 4.The proof uses a Lyapunov function and an invariant set.Source: §B.3.1 · p. 27

B.4 Extension to Higher-order Heads

• For an arbitrary later head, features 2 through n−1 are assigned to one head while the remaining heads stay aligned with the first feature; the analyzed head converges to a fixed point.The extension assumes analogous initialization and a fast-dynamics approximation.Source: §B.4 · pp. 28–29

Appendix C Expanding the Initialization Condition

• The theorem initializations form large ordered sets rather than neighborhoods of a particular point, allowing the initialization basin to be expanded.The passage contrasts this with analyses relying on vanishing initialization or limits toward critical submanifolds.Source: Appendix C · p. 30

D.1 Numerical Simulations of the Regression Flow

• The regression-flow simulations show sequential learning of positions (1), (2), then (3), with the first stage fastest and the third slowest.All heads initially learn from position (1), then specialize on later positions; Figure 6 reports the attention, value parameters, and loss over time.Source: §D.1 · p. 30

Appendix D Simulations and Comparison with Transformers

• The simplified dynamics quantitatively trace the full regression ODE across attention and value parameters, including non-monotonic dips in non-offshooting heads.The trajectories start from theoretical initializations at the second- and third-stage boundaries.Source: §D.1 · p. 30

D.2 Comparison with the Classification Transformer

• Both settings show all three heads concentrating on the most important positions before specializing, and heads leave the shared pattern in feature-importance order.The second-most important position is acquired before the least important one.Source: §D.2 · p. 30, Figure 8 · p. 33
• When an offshooting head acquires a feature, non-offshooting heads reduce alignment with that feature to cancel a cross-term from residual attention.The regression flow shows negative value-parameter dips, while the transformer shows corresponding alignment dips.Source: §D.2 · pp. 30–31, Figure 6 · p. 31, Figure 8 · p. 33
• The comparison is qualitative because the regression flow and transformer differ in objective, data setting, architecture, and parameterization, so their axes and timescales are not aligned.The regression uses continuous-time population gradient flow with singleton groups; the transformer uses finite-sample cross-entropy and absolute positional encodings.Source: §D.2 · pp. 31, 33

Appendix E Experimental Details

• The full and minimal transformers share optimization hyperparameters and synthetic data generation, but differ in architecture, positional encodings, and Markov interval lengths.The full model uses intervals of length 4; the minimal model uses intervals of length 2.Source: Appendix E · p. 34, Table 2 · p. 34, Table 1 · p. 34
• The n-gram models use the full transformer's architecture and optimization settings, training on windows of size n sliding over each sequence.The experiments’ source code is available in the repository named in the passage.Source: Appendix E · p. 34

Appendix F Additional Experiments

• Additional experiments examine infinite versus finite data, reversed importance ordering with non-uniform interval lengths, and weight decay.Source: Appendix F · p. 35

F.1 Infinite Data

• The same incremental-learning behavior persists with newly sampled data at each training step, removing any effect of overfitting.This experiment uses the minimal architecture; Figures 9 and 10 show attention patterns, validation loss, and KL divergence.Source: Figure 9 · p. 35, §F.1 · p. 35, Figure 10 · p. 36

F.2 Reverse Order

• Reversing interval importance preserves the observed behavior, and incremental learning is generally easier to observe when the most important interval is furthest away.The reversed-order intervals are I(3) = {12, 13}, I(2) = {8, 9, 10, 11}, and I(1) = {0, 1, 2, 3, 4, 5, 6, 7}.Source: §F.2 · pp. 35–36, Figure 11 · p. 36, Figure 12 · p. 36

F.3 Weight Decay

• Applying weight decay makes almost no difference to the learning dynamics.Source: §F.3 · p. 37

F.4 Two-block Transformers

• Two-block minimal and full transformers show incremental learning similar to the one-block case, though the first region corresponding to the first feature matrix is less pronounced.Source: Figure 13 · p. 37, Figure 14 · p. 37, §F.4 · p. 37

F.5 Non-uniform α values

• With α = [0.7, 0.3], learning remains incremental, and heads focus more attention on the position with the highest α value.Source: §F.5 · p. 37, Figure 15 · p. 38, Figure 16 · p. 38

F.6 Overlapping Intervals

• With overlapping intervals, the four-head model still learns incrementally, while three- and four-head models show different attention-learning orderings.The authors note that overlapping intervals make it unclear which positions are statistically most significant, and transformers may follow different solutions based on their feature matrices.Source: Figure 17 · p. 38, §F.6 · p. 38, Figure 18 · p. 39

F.7 Stochastic Gradient Descent (SGD)

• Incremental learning’s quantitative behavior is the same with SGD as with the paper’s other optimizer.Figures 20 and 21 show KL divergence and attention patterns over training steps with SGD.Source: §F.7 · p. 39, Figure 20 · p. 40, Figure 21 · p. 41