A Theoretical Study of (Hyper) Self-Attention through the Lens of Interactions: Representation, Training, Generalization

Guannan Qu; Muhammed Ustaomeroglu

REVIEW 4 major objections 6 minor 56 references

A Theoretical Study of (Hyper) Self-Attention through the Lens of Interactions: Representation, Training, Generalization

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

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

Pith's one-line read A single linear self-attention layer can exactly represent, learn, and length-generalize pairwise interaction functions, and the paper introduces two extensions for higher-order interactions.

desk verdict A correct representation theorem with coherent conditional learning guarantees, but the paper overclaims the scope of its realizability assumptions and includes a sloppy efficiency theorem; worth serious review after fixes. read the letter →

arxiv 2506.06179 v1 pith:66QJSITE submitted 2025-06-06 cs.LG stat.ML

Muhammed Ustaomeroglu , Guannan Qu This is my paper

classification cs.LGstat.ML

keywords self-attentionpairwiseinteractionsrepresentationtheorygradientflowgeneralizationlengthHyperFeatureAttention

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 argues that one layer of linear self-attention is enough to represent any function of the form $y_X(i) = \sum_j f(X(i),X(j)) w_{X(j)}$, where each entity's output is a sum of pairwise effects from all other entities, provided the embedding dimension $d$ equals the number of distinct entity types $|S|$; it also claims $d \ge |S|$ is necessary. Under a mild 'versatility' condition on the training data and the assumption that the target is exactly realizable, the paper shows that gradient flow on mean-squared error converges to zero training error, and that any zero-error solution generalizes perfectly to the population and to unseen sequence lengths. If these results hold, attention parameters get a concrete interpretation as pairwise interaction coefficients, which would explain why attention performs well on tasks ranging from multi-agent systems to genomic sequences. The paper then introduces HyperFeatureAttention and HyperAttention, two new modules that extend the same logic to coupled feature-level interactions and to three-way or higher-order interactions, with accompanying representation and convergence analyses.

What carries the argument

The load-bearing object is the pairwise interaction function $y_X(i) = \sum_{j \in [L]} f(X(i),X(j)) \, w_{X(j)}$, where $f$ is a scalar pairwise effect and $w$ is a value weight per entity type. A single-layer linear self-attention computes $(X C X^\top) X W_V$, so the bilinear form $x(\mu)^\top C x(\nu)$ plays the role of $f(\mu,\nu)$ and $x(\nu)^\top W_V$ plays the role of $w_\nu$; with orthonormal embeddings of dimension $|S|$, $C$ and $W_V$ can be read off directly. Convergence and generalization are carried by the element-count data matrices $S_{B_\mu}$, whose full column rank (Assumption 4.2) forces zero-training-error solutions to agree on interaction coefficients, and by the transformed parameters $T_{\mu,k}(C,W_V) = \sum_{\nu} (x(\mu)^\top C x(\nu)) (x(\nu)^\top W_{:,k})$, which characterize functional equivalence across sequence lengths.

What would settle it

Take a small domain, fix a pairwise-interaction target, and make every training sequence contain the same multiset of domain elements so the count matrix for each element is rank-deficient; if gradient flow still finds a zero-error solution but two such solutions disagree on held-out sequences of the same length, the uniqueness and generalization claims would be refuted.

Watch

Extended reading notes

Core claim

The central claim is that a single-layer linear self-attention is a mutual-interaction learner: for a discrete vocabulary $S$, it can exactly represent every aggregate pairwise interaction function $y_X(i) = \sum_{j \in [L]} f(X(i),X(j)) \, w_{X(j)}$ simultaneously for all entities $i$, with embedding dimension $d = |S|$ sufficient and necessary. Self-attention therefore needs $\Theta(|S|^2)$ parameters to capture these interactions, while a linear fully connected network needs $\Omega(L^2|S|^2)$. The paper further proves that, under training-data versatility and exactly realizability, gradient flow reaches zero training error, and any zero-error parameter set also matches the population distribution at the training length and at every sequence length. It claims the new HyperFeatureAttention and HyperAttention blocks carry this interaction representation to products of feature-specific attention scores and to higher-order multi-entity interactions, and reports experiments in which trained parameters match theoretically predicted interaction matrices after a functional-equivalence transformation.

Load-bearing premise

The convergence and generalization theorems all presuppose that the target task is exactly realizable by a fixed single-layer linear self-attention block with the same interaction function across all sequence lengths, and the paper's use of its representation theorem to justify that presupposition covers only tasks already of the Eq. 2 form.

Editorial extensions

If this is right

Learned attention matrices $C$ can be interpreted entrywise as pairwise interaction strengths between entity types, making trained attention parameters inspectable.
One layer of linear self-attention suffices for tasks modeled by the pairwise interaction sum, so a deep Transformer can be understood blockwise: each block can carry an interaction subroutine.
With versatile training data and exact realizability, gradient flow converges to zero training error, and the fit transfers to the population and to other sequence lengths without early stopping or additional regularization.
HyperFeatureAttention represents products of feature-specific attention scores with parameter count linear in the number of features rather than exponential, and HyperAttention represents $n$-way interactions.
The functional-equivalence transformation of Corollary 4.9 yields a canonical parameter matrix for any interaction function, so different optimized parameter sets can be compared through their $T$ matrices.

Reading between the lines

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

If a real task only approximately matches the exact pairwise-interaction form, the convergence and length-generalization guarantees would become approximate rather than exact, so the practical reach of the theory depends on how well real data obey Eq. 2.
The same interaction-coefficient interpretation could be tested on softmax self-attention; if trained softmax scores are close to their linearized counterparts, similar coefficient extraction should appear, but the nonlinearity may break the rank-based uniqueness argument.
The skip-trigram discussion implies HyperAttention should reduce spurious pairwise completions by assigning probability mass to genuine triple contexts; a controlled comparison of pairwise versus ternary attention heads in a language model would test this directly.
For $d < |S|$, the paper's approximate representation theorem bounds the error by the truncated singular values of the interaction matrix $F$, suggesting a practical recipe: choose embedding dimension by thresholding those singular values rather than by vocabulary size.

Share X Bluesky LinkedIn Reddit HN

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

Quick take: the core representation result is correct, and the convergence/generalization story is coherent under its stated assumptions. But the paper oversells the reach of Theorem 3.1, and Theorem 3.2 is not rigorously formulated. Fix those, and this is a useful contribution to transformer theory.

The good part: Theorem 3.1 gives a clean orthonormal-embedding construction showing d = |S| suffices and is necessary for pairwise interactions of the form in Eq. 2. That unifies several domains nicely. The gradient-flow proof (Theorem 4.4) looks internally correct under data versatility and positive initialization; the Gram-matrix lower bound argument is plausible. The test and length generalization results (Theorems 4.6, 4.8) are identifiability statements from full-rank count matrices, and they hold under the assumptions. The HyperFeatureAttention and HyperAttention modules are natural extensions, and the theory for them follows the same pattern. No code is shipped, but the main proofs are self-contained.

The soft spots, in order of severity. First, the narrative overclaims. Section 4.2 says "Due to Theorem 3.1 and Appendix B, we can safely assume strong realizability." That is not what Theorem 3.1 proves. It only guarantees representation for functions exactly of the form Eq. 2 with the same f and w across lengths. Arbitrary tasks need not be realizable. The paper's own Appendix B.2 gives a genotype-phenotype example (always-active allele) that a single-layer linear self-attention cannot length-generalize. So Theorems 4.4-4.8 are conditional on exact realizability; the "minimal assumptions" framing is overbroad. This is the load-bearing gap between the representation result and the learning guarantees.

Second, Theorem 3.2 is not rigorously formulated. A linear fully connected network cannot compute quadratic pairwise interactions at any parameter count, so the claimed Omega(L^2 |S|^2) lower bound is comparing apples to oranges. The parameter-efficiency claim may be recoverable with a nonlinear architecture, but as written the theorem is unsound.

Third, the experiments are thin. No code, seeds, or error bars on the OpenWebText benchmark; the perplexity gains are single runs. The colliding-agents experiments are consistency checks on a task constructed to satisfy the assumptions—useful for validating the theory, but not independent predictions.

Who this is for: researchers in transformer theory, especially representation and generalization. The conditional theorems deserve a serious referee. I would send it to review with a request to fix the overclaims and restate or remove Theorem 3.2.

Referee Report

4 major / 6 minor

Summary. This paper studies single-layer linear self-attention SA_lin(X) = (XCX^T)XW^V through the lens of pairwise interaction functions y_X(i) = \sum_j f(X(i), X(j)) w_{X(j)} over a discrete vocabulary S. The main representation result (Theorem 3.1) gives d = |S| as necessary and sufficient (with orthonormal embeddings) to represent any such function family, and Theorem 3.2 claims a quadratic parameter-count lower bound for fully connected networks. Under a data-versatility condition (Assumption 4.2, each element's count matrix full column rank) and exact realizability (Assumptions 4.3/4.5/4.7), the paper proves gradient-flow convergence to zero training error, perfect in-distribution generalization, and length (OOD) generalization, together with an identifiability corollary (Corollary 4.9). It then introduces two modules, HyperFeatureAttention (Hadamard products of attention-score matrices) and HyperAttention (higher-order tensor attention), with representation and convergence statements, and reports experiments on a colliding-agents task plus small-scale next-token-perplexity benchmarks.

Significance. Conditional on the stated realizability assumptions, the paper's core theorems appear sound: the construction in Theorem 3.1 is explicit and correct, the convergence proof in Appendix C is technically substantial and appears to close under Assumptions 4.2-4.3, and Corollary 4.9 turns the identifiability argument into a falsifiable prediction that the experiments confirm with mean squared distance on the order of 10^-5 (Figures 3-4). The versatility assumption receives a concentration justification in Appendix E, and the two proposed modules are clearly motivated by the exponential-versus-linear parameter gap in Section 5. The significance is bounded, however: the learning and generalization guarantees are conditional on exact representability of the target by a single length-independent pair (f, w); the efficiency comparison against fully connected networks rests on Theorem 3.2, which is not rigorously established; and the two small perplexity benchmarks provide only weak evidence for the modules' practical value. With the scope of the guarantees stated precisely, the interaction-based perspective is a useful addition to the attention-theory literature.

major comments (4)

[Section 3, Theorem 3.2 (Appendix B)] Theorem 3.2's lower-bound claim is not a valid statement as written. A linear fully connected network computes an affine map of its input, while the functions in Eq. (2) are polynomial of degree at least two in the entries of X (each summand multiplies a bilinear form f(X(i), X(j)) by a value w_{X(j)} that depends linearly on the rows of X); consequently no linear fully connected network of any size can represent them exactly, and the stated bound Omega(L^2 |S|^2) holds only vacuously. This does not support the sentence in Section 3 that 'Transformers are mutual interaction learners, while generic fully connected architectures are not.' Moreover, Steps 2-3 of the proof merely assert that each summand 'must be learned with its own parameters' and that each output position pays the cost separately, without defining the network family, its parameterization, or ruling out weight sharing. The theorem should be restated for a well-specified nonlinear model class (e.g., a fixed-width two-layer network or a polynomial network) and given a formal counting or rank argument, or the efficiency claim should be withdrawn or relegated to a conjecture.
[Sections 4.2-4.3, Assumptions 4.5 and 4.7] The statements 'Due to Theorem 3.1 and Appendix B, we can safely assume strong realizability' (Section 4.2) and, for Assumption 4.7, 'which holds due to Theorem 3.1' (Section 4.3) overstate what Theorem 3.1 proves. Theorem 3.1 constructs (C, WV) only for functions of the exact form of Eq. (2) with a single pair (f, w) used at every length; it says nothing about realizability of arbitrary fixed-length tasks, let alone tasks expressible at every length with fixed parameters. The genotype-phenotype example in Appendix B.2 (an 'always active' allele with row weights 1/L) is the paper's own counterexample: the appendix explicitly states that a single-layer linear self-attention cannot length-generalize there. Consequently, Theorems 4.4, 4.6, and 4.8 apply only to tasks that are exactly representable with length-independent (f, w), and the abstract's and Section 1's 'minimal assumptions' framing (bullet iv: 'Our approach only requires mild and possibly inevitable conditions on the data distribution') is not supported, because Assumptions 4.3/4.5/4.7 are conditions on the task and on the existence of fixed parameters, not on the data distribution alone.
[Appendix D.2, Proof of Theorem 4.8] The proof's key rank step is not justified as written. Eq. (33) defines an 'infinite sample extension' S^{L*}_{B_inf_mu} by rows with 's_nu != 0', but it is unclear whether the restriction is on all coordinates or only the mu-coordinate; if all coordinates are required to be positive, such rows may not exist in the support of P^{L*} (e.g., when elements are sampled without repetition and L* < |S|). Full column rank of the finite training matrix S_{B_mu} does not in itself transfer to this restricted infinite matrix, and the conclusion that Delta^{L*}_{mu nu} = 0, hence that the parameter set generalizes to every length, depends on this rank condition. The proof should define S^{L*}_{B_inf_mu} precisely (presumably as the full set of count vectors in the population support, or as a matrix whose rows correspond to Eq. (32) for all X in the support) and then prove the rank implication, rather than asserting that it is 'satisfied by Assumption 4.2.'
[Section 5 / Remark F.6 (Appendix F)] Remark F.6's claim that even a two-layer multi-head linear self-attention cannot represent factorized cross-feature interactions such as sum_j f^{(1)}(a_i,a_j) f^{(2)}(b_i,b_j) is supported only by a sketch, and the sketch's central assertion is questionable: it says that multi-head attention 'combines bilinear terms additively, not multiplicatively,' but the second layer computes new bilinear forms h_i^T C^{(p)} h_k of the first layer's outputs, where each h_i is itself a sum of bilinear terms; the resulting objects are sums of products of bilinear forms, which is exactly the multiplicative structure needed for the factorized target. Since this remark is cited in Section 5 as the justification for introducing HyperFeatureAttention, the impossibility claim needs a formal proof (or a corrected statement with the precise separability conditions under which two-layer multi-head linear self-attention fails) before the motivation for the new module is established.

minor comments (6)

[Throughout the appendix] There are several typos and notation errors: 'Threorem B.6' appears twice in Appendix B.1.2, 'Threorem 3.1' appears in the heading of the Proof of Theorem 3.1, 'MutiHeadHA' appears in Definition G.1, 'kronocker' appears in the proof of Theorem 4.4, and Definition 6.1 refers to 'Table H' rather than the numbered comparison table.
[Section 7.1] The experimental setup sentence 'C(t=0) = 0, <x(alpha), w(t=0)>, for all alpha in S' is incomplete; Theorem 4.4 requires a positive lower bound <x(alpha), w(t=0)> >= b > 0, which should also be stated in the experimental setup.
[Section 7.2, Tables 1-2] The perplexity results are single-run with no error bars or seed counts, and the HFAv2 row uses 4 heads against 3 for the SA baseline, so the comparison does not isolate the effect of the proposed mechanism; the Conclusion's claim that the modules 'consistently achieve lower perplexity' is stronger than two small benchmarks (28k iterations) can support.
[Theorem 4.6] The displayed population expectation uses single vertical bars, 'E | f_{C,WV}(X) - Y | = 0', where a norm should appear to match the MSE objective.
[Section 6 (Definition 6.1)] The text says the final equation of Definition 6.1 introduces O(L^3) computational cost, but the summation runs over 1 <= j1 <= j2 <= L, which has Theta(L^2) terms; the stated complexity should be tied to the tensor contractions or aligned with the n-th order definition in Table 3 to be consistent.
[Section 3, 'Why d = |S|' paragraph] The claim that reducing to d < |S| 'merely introduces a small approximation gap without altering the core theory' is not supported by Theorem B.2, whose error bound involves sigma_{d+1}(F) * L * zeta_1 and need not be small; the sentence should be qualified by the singular-value tail of F.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the representation, convergence, and generalization results are conditional theorems with self-contained proofs; the main caveat is an overbroad realizability claim, not a construction-level circularity.

full rationale

The paper's derivation chain is largely self-contained and conditional. Theorem 3.1 gives an explicit construction (C with x(alpha)^T C x(beta) = f(alpha,beta), and WV with x(alpha)^T WV = w_alpha) for the class of functions in Eq. 2, and the necessity argument via rank(X C X^T) <= d is a genuine lower bound. Theorems 4.4, 4.6, and 4.8 are honest implications: each assumes exact realizability (Assumptions 4.3, 4.5, and 4.7) and then proves convergence or generalization using the count-matrix full-rank condition (Assumption 4.2) and nontrivial gradient-flow or identifiability arguments. The conclusion of Theorem 4.8 is not a restatement of Assumption 4.7 alone; the proof uses the versatility condition to force the L*-generalizing parameters to coincide with the universal solution. No load-bearing self-citations appear; the cited representation and optimization results are either external or proven in the paper. The main caveat is scope, not circularity: Sections 4.2 and 4.3 state 'Due to Theorem 3.1 and Appendix B, we can safely assume strong realizability' and 'Assumption 4.7 ... holds due to Theorem 3.1,' but Theorem 3.1 only guarantees realizability for tasks of the exact pairwise-sum form in Eq. 2 with the same (f,w) across lengths. The paper itself concedes in Appendix B.2 that a single-layer linear self-attention cannot length-generalize the genotype-phenotype task with an always-active allele. This overstatement is a correctness or scope gap, not an instance of a 'prediction' reducing to a fitted input by construction. The experiments are consistency checks of the conditional theorems under tasks built to satisfy realizability; they do not fit a parameter and then relabel it as a prediction.

Assumptions & free parameters 0 free parameters · 7 assumptions · 2 invented entities

The theory rests on exact representability, orthonormal embeddings, full-rank count matrices, and specific initializations; these are assumptions rather than fitted parameters. The new modules are tested only on in-paper benchmarks without external replication.

assumptions (7)

domain assumption Embedding dimension d = |S| with orthonormal embeddings
Used throughout Section 3 and Appendix B; makes X^T X diagonal and enables exact representation.
domain assumption Training data versatility Assumption 4.2: SBmu full column rank for all mu
Core identifiability condition in Theorems 4.4, 4.6, and 4.8; claimed mild and justified by Theorem E.2 under positive-definite covariance.
domain assumption Weak, Strong, and Universal realizability (Assumptions 4.3, 4.5, 4.7): fixed C and WV exactly fit training, population, and all lengths
The predictive content of the convergence and generalization theorems is conditional on this. It is not implied by Theorem 3.1 for arbitrary tasks, only for tasks exactly of the form Eq. 2 with length-independent f and w.
domain assumption Initialization C(0) = 0 and positive w(0)
Required by Lemma C.2 to keep w entries bounded away from zero during gradient flow; not a data assumption.
domain assumption Scalar output d2 = 1 in the convergence proof
Adopted in Section 4.1 to simplify analysis; the convergence theorem is stated only for scalar outputs.
domain assumption Infinite population count matrices SB∞mu have full column rank
Needed in Appendix D.2 for length generalization; the paper notes it can fail under constraints such as unique elements.
standard math Standard linear algebra, singular value inequalities, matrix Bernstein, and ODE convergence tools
Background tools used in Appendices B through E.

invented entities (2)

HyperFeatureAttention
purpose: Capture Hadamard products and couplings of multiple pairwise attention-score matrices to model feature-level interaction couplings.
New module supported only by in-paper perplexity tables; no external benchmark, code, or data are provided.
HyperAttention
purpose: Capture higher-order n-way interactions via order-n attention tensors.
New module supported only by in-paper experiments; no external replication artifacts are provided.

how reviews work

0 comments

Cite this review

Pith. "Pith review of A Theoretical Study of (Hyper) Self-Attention through the Lens of Interactions: Representation, Training, Generalization." pith.science (2026). https://pith.science/paper/66QJSITE

@misc{pith2026250606179,
  author       = {Pith},
  title        = {Pith review of: A Theoretical Study of (Hyper) Self-Attention through the Lens of Interactions: Representation, Training, Generalization},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/66QJSITE}},
  note         = {Machine review of arXiv:2506.06179}
}

read the original abstract

Self-attention has emerged as a core component of modern neural architectures, yet its theoretical underpinnings remain elusive. In this paper, we study self-attention through the lens of interacting entities, ranging from agents in multi-agent reinforcement learning to alleles in genetic sequences, and show that a single layer linear self-attention can efficiently represent, learn, and generalize functions capturing pairwise interactions, including out-of-distribution scenarios. Our analysis reveals that self-attention acts as a mutual interaction learner under minimal assumptions on the diversity of interaction patterns observed during training, thereby encompassing a wide variety of real-world domains. In addition, we validate our theoretical insights through experiments demonstrating that self-attention learns interaction functions and generalizes across both population distributions and out-of-distribution scenarios. Building on our theories, we introduce HyperFeatureAttention, a novel neural network module designed to learn couplings of different feature-level interactions between entities. Furthermore, we propose HyperAttention, a new module that extends beyond pairwise interactions to capture multi-entity dependencies, such as three-way, four-way, or general n-way interactions.

Figures

Figures reproduced from arXiv: 2506.06179 by the authors.

**Figure 1.** Diagonal entries of the interaction matrix C for N = 360 agents with radius R = 5. The pattern emerges from Fourier analysis of collision dynamics in the agent movement model. The matrix indices are from 0 to N − 1. Letting ak = 2 Re{X[k]} and bk = −2 Im{X[k]}, the same function can be expressed as x[n] =    a0 2 + N−1 X2 k=1 ak cos 2π N kn + bk sin 2π N kn , for odd N a0 2 + aN/2 2 cos 2π N … view at source ↗

**Figure 2.** Comparison of learned vs. devised parameters for sinusoidal embedding: (a) Devised matrix C∀L showing the original devised structure, (b) Learned matrix C demonstrating the emergent but non-interpretable patterns. While visually distinct, both parameterizations lead to equivalent model behavior through different mathematical organizations. 52 [PITH_FULL_IMAGE:figures/full_fig_p052_2.png] view at source ↗

**Figure 3.** Equivalence of learned parameters with one-hot embedding in domain embedding base (here the parameters are already in the domain embedding base so we did not transfer them): (a) Cµν learned parameters in domain embedding base, (b) C ∀L devised parameters in domain embedding base, (c) CµνWν0 the interesting matrix in domain embedding base, (d) Transformed C ∀L µν W∀L ν0 using original parameters. The mean squared dif… view at source ↗

Figures from the paper (1 more)

**Figure 4.** Figure 4: Equivalence of learned parameters with sinusoidal embedding in domain embedding base: (a) Cµν learned parameters in domain embedding base, (b) C ∀L devised parameters in domain embedding base, (c) CµνWν0 the interesting matrix in domain embedding base, (d) Transformed …

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

56 extracted references · 17 canonical work pages

[1]

Transformers learn to implement preconditioned gradient descent for in-context learning, November 2023

Ahn, K., Cheng, X., Daneshmand, H., and Sra, S. Transformers learn to implement preconditioned gradient descent for in-context learning, November 2023. URL http://arxiv.org/abs/2306.00297. arXiv:2306.00297 [cs]

arXiv 2023
[2]

Linear attention is (maybe) all you need (to understand transformer optimization)

Ahn, K., Cheng, X., Song, M., Yun, C., Jadbabaie, A., and Sra, S. Linear attention is (maybe) all you need (to understand transformer optimization). arXiv preprint arXiv:2310.01082, 2024. URL https://arxiv.org/abs/2310.01082

arXiv 2024
[3]

Block coordinate descent for neural networks provably finds global minima

Akiyama, S. Block coordinate descent for neural networks provably finds global minima. 2024. URL https://openreview.net/forum?id=n2RIkaf1S4

work page 2024
[4]

and Song, Z

Alman, J. and Song, Z. How to Capture Higher -order Correlations ? Generalizing Matrix Softmax Attention to Kronecker Computation , October 2023. URL https://arxiv.org/abs/2310.04064v1

arXiv 2023
[5]

Neural Machine Translation by Jointly Learning to Align and Translate , May 2016

Bahdanau, D., Cho, K., and Bengio, Y. Neural Machine Translation by Jointly Learning to Align and Translate , May 2016. URL http://arxiv.org/abs/1409.0473. arXiv:1409.0473 [cs]

arXiv 2016
[6]

On the ability and limitations of transformers to recognize formal languages, 2020 a

Bhattamishra, S., Ahuja, K., and Goyal, N. On the ability and limitations of transformers to recognize formal languages, 2020 a . URL http://arxiv.org/abs/2009.11264

arXiv 2020
[7]

On the Computational Power of Transformers and its Implications in Sequence Modeling , October 2020 b

Bhattamishra, S., Patel, A., and Goyal, N. On the Computational Power of Transformers and its Implications in Sequence Modeling , October 2020 b . URL http://arxiv.org/abs/2006.09286. arXiv:2006.09286 [cs]

arXiv 2020
[8]

Brown, T., Mann, B., Ryder, N., Subbiah, M., Kaplan, J. D., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., Agarwal, S., Herbert-Voss, A., Krueger, G., Henighan, T., Child, R., Ramesh, A., Ziegler, D., Wu, J., Winter, C., Hesse, C., Chen, M., Sigler, E., Litwin, M., Gray, S., Chess, B., Clark, J., Berner, C., McCandlish, S., Radford, A.,...

work page 1901

Show all 56 references

[9]

Cammarata, N., Carter, S., Goh, G., Olah, C., Petrov, M., Schubert, L., Voss, C., Egan, B., and Lim, S. K. Thread: Circuits. Distill, 2020. doi:10.23915/distill.00024. https://distill.pub/2020/circuits

2020 doi
[10]

Decision Transformer : Reinforcement Learning via Sequence Modeling , June 2021

Chen, L., Lu, K., Rajeswaran, A., Lee, K., Grover, A., Laskin, M., Abbeel, P., Srinivas, A., and Mordatch, I. Decision Transformer : Reinforcement Learning via Sequence Modeling , June 2021. URL http://arxiv.org/abs/2106.01345. arXiv:2106.01345 [cs]

2021 arXiv
[11]

and Li, Y

Chen, S. and Li, Y. Provably learning a multi-head attention layer, February 2024. URL http://arxiv.org/abs/2402.04084. arXiv:2402.04084 [cs, stat]

2024 arXiv
[12]

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, 2024

2024 arXiv
[13]

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. In Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pp.\ 8002--8037. PMLR,...

2024 doi arXiv
[14]

Rethinking Attention with Performers , November 2022

Choromanski, K., Likhosherstov, V., Dohan, D., Song, X., Gane, A., Sarlos, T., Hawkins, P., Davis, J., Mohiuddin, A., Kaiser, L., Belanger, D., Colwell, L., and Weller, A. Rethinking Attention with Performers , November 2022. URL http://arxiv.org/abs/2009.14794. arXiv:2009.14794 [cs]

2022 arXiv
[15]

On the Optimization and Generalization of Multi -head Attention , October 2023

Deora, P., Ghaderi, R., Taheri, H., and Thrampoulidis, C. On the Optimization and Generalization of Multi -head Attention , October 2023. URL http://arxiv.org/abs/2310.12680. arXiv:2310.12680 [cs, math, stat]

2023 arXiv
[16]

BERT : Pre -training of Deep Bidirectional Transformers for Language Understanding , May 2019

Devlin, J., Chang, M.-W., Lee, K., and Toutanova, K. BERT : Pre -training of Deep Bidirectional Transformers for Language Understanding , May 2019. URL http://arxiv.org/abs/1810.04805. arXiv:1810.04805 [cs]

2019 arXiv
[17]

An Image is Worth 16x16 Words : Transformers for Image Recognition at Scale , June 2021

Dosovitskiy, A., Beyer, L., Kolesnikov, A., Weissenborn, D., Zhai, X., Unterthiner, T., Dehghani, M., Minderer, M., Heigold, G., Gelly, S., Uszkoreit, J., and Houlsby, N. An Image is Worth 16x16 Words : Transformers for Image Recognition at Scale , June 2021. URL http://arxiv....

2021 arXiv
[18]

L., Goel, S., Kakade, S., and Zhang, C

Edelman, B. L., Goel, S., Kakade, S., and Zhang, C. Inductive Biases and Variable Creation in Self - Attention Mechanisms , June 2022. URL http://arxiv.org/abs/2110.10090. arXiv:2110.10090 [cs, stat]

2022 arXiv
[19]

A mathematical framework for transformer circuits

Elhage, N., Nanda, N., Olsson, C., Henighan, T., Joseph, N., Mann, B., Askell, A., Bai, Y., Chen, A., Conerly, T., DasSarma, N., Drain, D., Ganguli, D., Hatfield-Dodds, Z., Hernandez, D., Jones, A., Kernion, J., Lovitt, L., Ndousse, K., Amodei, D., Brown, T., Clark, J., Kaplan...

2021
[20]

Phenotypes and Genotypes: The Search for Influential Genes, volume 18 of Computational Biology

Frommlet, F., Bogdan, M., and Ramsey, D. Phenotypes and Genotypes: The Search for Influential Genes, volume 18 of Computational Biology. Springer, 2016. ISBN 978-1-4471-5309-2. doi:10.1007/978-1-4471-5310-8. URL https://link.springer.com/book/10.1007/978-1-4471-5310-8

2016 doi
[21]

M., and Fan, J

Gao, C., Cao, Y., Li, Z., He, Y., Wang, M., Liu, H., Klusowski, J. M., and Fan, J. Global convergence in training large-scale transformers. In Proceedings of the 38th Conference on Neural Information Processing Systems (NeurIPS 2024), 2024

2024
[22]

On Limitation of Transformer for Learning HMMs , June 2024

Hu, J., Liu, Q., and Jin, C. On Limitation of Transformer for Learning HMMs , June 2024. URL http://arxiv.org/abs/2406.04089. arXiv:2406.04089 [cs]

2024 arXiv
[23]

In-context convergence of transformers

Huang, Y., Cheng, Y., and Liang, Y. In-context convergence of transformers. In Proceedings of the 41st International Conference on Machine Learning (ICML). PMLR, 2024 a

2024
[24]

How Transformers Learn Diverse Attention Correlations in Masked Vision Pretraining

Huang, Y., Wen, Z., Chi, Y., and Liang, Y. How Transformers Learn Diverse Attention Correlations in Masked Vision Pretraining . 2024 b

2024
[25]

E., and Li, Y

Jelassi, S., Sander, M. E., and Li, Y. Vision Transformers provably learn spatial structure, October 2022. URL http://arxiv.org/abs/2210.09221. arXiv:2210.09221 [cs]

2022 arXiv
[26]

Jensen, H. J. Complexity Science: The Study of Emergence. Higher Education from Cambridge University Press, November 2022. doi:10.1017/9781108873710. URL https://www.cambridge.org/highereducation/books/complexity-science/E0761D26BDAB25D75C6AB868AECE2F2D. ISBN: 9781108873710, P...

2022 doi
[27]

Jumper, J., Evans, R., Pritzel, A., Green, T., Figurnov, M., Ronneberger, O., Tunyasuvunakool, K., Bates, R., Žídek, A., Potapenko, A., Bridgland, A., Meyer, C., Kohl, S. A. A., Ballard, A. J., Cowie, A., Romera-Paredes, B., Nikolov, S., Jain, R., Adler, J., Back, T., Petersen...

2021
[28]

PolySketchFormer : Fast Transformers via Sketching Polynomial Kernels , March 2024

Kacham, P., Mirrokni, V., and Zhong, P. PolySketchFormer : Fast Transformers via Sketching Polynomial Kernels , March 2024. URL http://arxiv.org/abs/2310.01655. arXiv:2310.01655 [cs]

2024 arXiv
[29]

and Sato, I

Kajitsuka, T. and Sato, I. Are transformers with one layer self-attention using low-rank weight matrices universal approximators? In International Conference on Learning Representations (ICLR), 2024

2024
[30]

Transformers are RNNs : Fast Autoregressive Transformers with Linear Attention

Katharopoulos, A., Vyas, A., Pappas, N., and Fleuret, F. Transformers are RNNs : Fast Autoregressive Transformers with Linear Attention . Proceedings of Machine Learning Research, August 2020. doi:10.48550/arXiv.2006.16236. URL http://arxiv.org/abs/2006.16236. arXiv:2006.16236 [cs]

2020 doi arXiv
[31]

Koohpayegani, S. A. and Pirsiavash, H. SimA : Simple Softmax -free Attention for Vision Transformers , March 2024. URL http://arxiv.org/abs/2206.08898. arXiv:2206.08898 [cs]

2024 arXiv
[32]

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

Li, H., Wang, M., Liu, S., and Chen, P.-y. A theoretical understanding of shallow vision transformers: Learning, generalization, and sample complexity, 2023. URL http://arxiv.org/abs/2302.06015

2023 arXiv
[33]

The closeness of in-context learning and weight shifting for softmax regression

Li, S., Song, Z., Xia, Y., Yu, T., and Zhou, T. The closeness of in-context learning and weight shifting for softmax regression. arXiv preprint arXiv:2304.13276, 2024

2024 arXiv
[34]

On the Expressive Power of Self - Attention Matrices , June 2021

Likhosherstov, V., Choromanski, K., and Weller, A. On the Expressive Power of Self - Attention Matrices , June 2021. URL http://arxiv.org/abs/2106.03764. arXiv:2106.03764 [cs]

2021 arXiv
[35]

T., Goel, S., Krishnamurthy, A., and Zhang, C

Liu, B., Ash, J. T., Goel, S., Krishnamurthy, A., and Zhang, C. Transformers Learn Shortcuts to Automata , May 2023. URL http://arxiv.org/abs/2210.10749. arXiv:2210.10749 [cs, stat]

2023 arXiv
[36]

S., and Xu, H

Lu, C., Shi, R., Liu, Y., Hu, K., Du, S. S., and Xu, H. Rethinking Transformers in Solving POMDPs , May 2024. URL http://arxiv.org/abs/2405.17358. arXiv:2405.17358 [cs]

2024 arXiv
[37]

Your transformer may not be as powerful as you expect

Luo, S., Li, S., Zheng, S., Liu, T.-Y., Wang, L., and He, D. Your transformer may not be as powerful as you expect. In Advances in Neural Information Processing Systems (NeurIPS), 2022

2022
[38]

Transformers are expressive, but are they expressive enough for regression? arXiv preprint arXiv:2402.15478, 2024

Nath, S., Khadilkar, H., and Bhattacharyya, P. Transformers are expressive, but are they expressive enough for regression? arXiv preprint arXiv:2402.15478, 2024

2024 arXiv
[39]

Theory, Analysis , and Best Practices for Sigmoid Self - Attention , September 2024

Ramapuram, J., Danieli, F., Dhekane, E., Weers, F., Busbridge, D., Ablin, P., Likhomanenko, T., Digani, J., Gu, Z., Shidani, A., and Webb, R. Theory, Analysis , and Best Practices for Sigmoid Self - Attention , September 2024. URL http://arxiv.org/abs/2409.04431. arXiv:2409.04431 [cs]

2024 arXiv
[40]

Representational Strengths and Limitations of Transformers , November 2023

Sanford, C., Hsu, D., and Telgarsky, M. Representational Strengths and Limitations of Transformers , November 2023. URL http://arxiv.org/abs/2306.02896. arXiv:2306.02896 [cs, stat]

2023 arXiv
[41]

Effects of depth, width, and initialization: A convergence analysis of layer-wise training for deep linear neural networks

Shin, Y. Effects of depth, width, and initialization: A convergence analysis of layer-wise training for deep linear neural networks. arXiv , 2020. doi:10.48550/arXiv.1910.05874. URL http://arxiv.org/abs/1910.05874

2020 doi arXiv
[42]

Unraveling the gradient descent dynamics of transformers

Song, B., Han, B., Zhang, S., Ding, J., and Hong, M. Unraveling the gradient descent dynamics of transformers. In Advances in Neural Information Processing Systems (NeurIPS), 2024

2024
[43]

RoFormer : Enhanced Transformer with Rotary Position Embedding

Su, J., Lu, Y., Pan, S., Murtadha, A., Wen, B., and Liu, Y. RoFormer : Enhanced Transformer with Rotary Position Embedding . arXiv preprint arXiv:2104.09864, November 2023. doi:10.48550/arXiv.2104.09864. URL http://arxiv.org/abs/2104.09864. Available at http://arxiv.org/abs/2104.09864

2023 doi arXiv
[44]

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

Tarzanagh, D. A., Li, Y., Thrampoulidis, C., and Oymak, S. Transformers as support vector machines, 2024. URL http://arxiv.org/abs/2308.16898

2024 arXiv
[45]

Scan and snap: Understanding training dynamics and token composition in 1-layer transformer, 2023

Tian, Y., Wang, Y., Chen, B., and Du, S. Scan and snap: Understanding training dynamics and token composition in 1-layer transformer, 2023. URL http://arxiv.org/abs/2305.16380

2023 arXiv
[46]

Tropp, J. A. An introduction to matrix concentration inequalities, 2015. URL https://arxiv.org/abs/1501.01571

2015 arXiv
[47]

N., Kaiser, L., and Polosukhin, I

Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, L., and Polosukhin, I. Attention Is All You Need , August 2023. URL http://arxiv.org/abs/1706.03762. arXiv:1706.03762 [cs]

2023 arXiv
[48]

Transformers learn in-context by gradient descent, 2023

von Oswald, J., Niklasson, E., Randazzo, E., Sacramento, J., Mordvintsev, A., Zhmoginov, A., and Vladymyrov, M. Transformers learn in-context by gradient descent, 2023. URL http://arxiv.org/abs/2212.07677. arXiv preprint arXiv:2212.07677

2023 arXiv
[49]

Z., Khabsa, M., Fang, H., and Ma, H

Wang, S., Li, B. Z., Khabsa, M., Fang, H., and Ma, H. Linformer: Self - Attention with Linear Complexity , June 2020. URL http://arxiv.org/abs/2006.04768. arXiv:2006.04768 [cs]

2020 arXiv
[50]

Wang, Z., Wei, S., Hsu, D., and Lee, J. D. Transformers Provably Learn Sparse Token Selection While Fully - Connected Nets Cannot , June 2024. URL http://arxiv.org/abs/2406.06893. arXiv:2406.06893 [cs, math, stat]

2024 arXiv
[51]

Statistically meaningful approximation: a case study on approximating turing machines with transformers, 2023

Wei, C., Chen, Y., and Ma, T. Statistically meaningful approximation: a case study on approximating turing machines with transformers, 2023. URL http://arxiv.org/abs/2107.13163

2023 arXiv
[52]

Training Dynamics of Transformers to Recognize Word Co -occurrence via Gradient Flow Analysis , October 2024

Yang, H., Kailkhura, B., Wang, Z., and Liang, Y. Training Dynamics of Transformers to Recognize Word Co -occurrence via Gradient Flow Analysis , October 2024. URL http://arxiv.org/abs/2410.09605. arXiv:2410.09605

2024 arXiv
[53]

Self-attention networks can process bounded hierarchical languages, 2023

Yao, S., Peng, B., Papadimitriou, C., and Narasimhan, K. Self-attention networks can process bounded hierarchical languages, 2023. URL http://arxiv.org/abs/2105.11115

2023 arXiv
[54]

S., Reddi, S

Yun, C., Bhojanapalli, S., Rawat, A. S., Reddi, S. J., and Kumar, S. Are Transformers universal approximators of sequence-to-sequence functions?, February 2020. URL http://arxiv.org/abs/1912.10077. arXiv:1912.10077 [cs, stat]

2020 arXiv
[55]

T.-K., Lin, S., and Yao, Y

Zeng, J., Lau, T. T.-K., Lin, S., and Yao, Y. Global convergence of block coordinate descent in deep learning, 2019. URL http://arxiv.org/abs/1803.00225

2019 arXiv
[56]

Zhai, X., Zhou, R., Zhang, L., and Du, S. S. Transformers are Efficient Compilers , Provably , October 2024. URL http://arxiv.org/abs/2410.14706. arXiv:2410.14706 [cs]

2024 arXiv

Pith tools

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

[1] [1]

Transformers learn to implement preconditioned gradient descent for in-context learning, November 2023

Ahn, K., Cheng, X., Daneshmand, H., and Sra, S. Transformers learn to implement preconditioned gradient descent for in-context learning, November 2023. URL http://arxiv.org/abs/2306.00297. arXiv:2306.00297 [cs]

arXiv 2023

[2] [2]

Linear attention is (maybe) all you need (to understand transformer optimization)

Ahn, K., Cheng, X., Song, M., Yun, C., Jadbabaie, A., and Sra, S. Linear attention is (maybe) all you need (to understand transformer optimization). arXiv preprint arXiv:2310.01082, 2024. URL https://arxiv.org/abs/2310.01082

arXiv 2024

[3] [3]

Block coordinate descent for neural networks provably finds global minima

Akiyama, S. Block coordinate descent for neural networks provably finds global minima. 2024. URL https://openreview.net/forum?id=n2RIkaf1S4

work page 2024

[4] [4]

and Song, Z

Alman, J. and Song, Z. How to Capture Higher -order Correlations ? Generalizing Matrix Softmax Attention to Kronecker Computation , October 2023. URL https://arxiv.org/abs/2310.04064v1

arXiv 2023

[5] [5]

Neural Machine Translation by Jointly Learning to Align and Translate , May 2016

Bahdanau, D., Cho, K., and Bengio, Y. Neural Machine Translation by Jointly Learning to Align and Translate , May 2016. URL http://arxiv.org/abs/1409.0473. arXiv:1409.0473 [cs]

arXiv 2016

[6] [6]

On the ability and limitations of transformers to recognize formal languages, 2020 a

Bhattamishra, S., Ahuja, K., and Goyal, N. On the ability and limitations of transformers to recognize formal languages, 2020 a . URL http://arxiv.org/abs/2009.11264

arXiv 2020

[7] [7]

On the Computational Power of Transformers and its Implications in Sequence Modeling , October 2020 b

Bhattamishra, S., Patel, A., and Goyal, N. On the Computational Power of Transformers and its Implications in Sequence Modeling , October 2020 b . URL http://arxiv.org/abs/2006.09286. arXiv:2006.09286 [cs]

arXiv 2020

[8] [8]

Brown, T., Mann, B., Ryder, N., Subbiah, M., Kaplan, J. D., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., Agarwal, S., Herbert-Voss, A., Krueger, G., Henighan, T., Child, R., Ramesh, A., Ziegler, D., Wu, J., Winter, C., Hesse, C., Chen, M., Sigler, E., Litwin, M., Gray, S., Chess, B., Clark, J., Berner, C., McCandlish, S., Radford, A.,...

work page 1901