A Theoretical Study of (Hyper) Self-Attention through the Lens of Interactions: Representation, Training, Generalization
Authors: Muhammed Ustaomeroglu
Guannan Qu
Venue: ICML 2025 poster (2025)
Keywords: attention
self-attention
deep learning
theory
representation
convergence
generalization
interactions
Primary area: theory->deep_learning
TL;DR: We treat self-attention as an interaction learner, prove that a single linear self-attention can capture all pairwise dependencies, then introduce HyperFeatureAttention and HyperAttention to capture richer interactions.

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.

A Theoretical Study of (Hyper) Self-Attention through the Lens of Interactions: Representation, Training, Generalization
Muhammed Ustaomeroglu
Guannan Qu'
Abstract
reinforcement learning (Chen et al., 2021). Despite the success of attention, our formal understanding of its repre- sentation, optimization, and generalization abilities is in its early stages.
Self-attention has emerged as a core component of modern neural architectures, yet its theoretical underpinnings remain elusive, In this paper, we study self- aff-aatention through the lens of interact- ing entities, ranging from agents in multi-agent reinforcement learning to alleles in genetic se- quences, and show that single layer linear self- attention can efficiently represent, learn, and gen- eralize functions capturing pairwise interactions, including out-of-distributinn scenarios. Our amal- ysis reveals that self-attention acts as a mutual interaction learner under minimal assumptions the diversity of interaction patterns observed during training, thereby encompassing wide va- riety of real-world domains. In addition, we vali- date our theoretical insights through experiments demonstrating that self-attention learns interac- tion functions and generalizes across both pop- ulation distributions and out-of-distribution sce- narios. Building on our theories, we introduce HypeerFeatureAttentiion, novel neural network module designed to learn couplings of different feature-level interactions between entities. Fur- thermore, we propose HyperAttention, a new mod- ule that extends beyond pairwise interactions to capture multi-entity dependencies, such as three- way, four-way, or general n-way interactions.
Recent theoretical investigations illuminated Transformers' representational abilities/lmiittioons (Liu et al., 2023; San- ford al., 2023) and training dynamics (Ahn al., 2023; Jelassi et al., 2022; Gao et al., 2024) from different perspec- tives (e.g., language modeling, image patch classification, in context learning, etc.). Despite this progress, current theoretical frameworks exhibit critical limitations:
(i) Existing analyses often target isolated problems, lack- ing a unified perspective for characterizing Transform- ers' capabilities across diverse domains. In contrast, our theory makes an attempt to provide unified per- spective by assuming that the data comes from a mu- tual interaction model, which we show captures broad applications.
(ii)
Most mathematically rigorous theories overlook test- time generalization, particularly robustness to out-of- distribution (OOD) shifts. Our analysis addresses OOD terms of length generalization.
(iii) Mathematically rigorous theories typically offer inter- pretations only for the predetermined parameters. In contrast, our approach explains broader set of param- eters-many of which may initially appear unintuitive.
(iv) Generally, rigorous theories rely on restrictive assump- tions about model parameters. In contrast, our frame- work does not impose such assumptions the param- eters. Our approach only requires mild and possibly inevitable conditions on the data distribution -such as training data versatility.
1. Introduction
Ever since the invention of Transformers (Vaswani et al., 2023), attention is the building block for many domains, spanning natural language processing (Brown et al., 2020; Devlin al., 2019), computer vision (Dosovitskiy et al., 2021), protein structure prediction (Jumper et al., 2021),
In this work, we adopt a interacting entities viewpoint to study self-attention, where each token represents an interact- ing entity (e.g., agents in multi-agent reinforcement learn- ing, particles in physical simulations, amino acids in pro- tein sequences, words in natural language). Specifically, we introduce a function that models interactions among these entities and demonstrate its applicability across di- verse domains, including the colliding agents environment, genotype-phenotyy mapping task, vision task, and time
'Department of Electrical and Computer Engineering, Carnegie Mellon University, Pittsburgh, USA. Correspondence to: Muhammed Ustaomeroglu <mustaome
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

A Theoretical Study of (Hyper) Self-Attention through the Lens of Interactions
series prediction. Under this viewpoint, we prove that single-layer linear self-attention can efficiently represent such functions and show that gradient-descent training con- verges to the parameters realizing these interactions, under mild assumptions on the data.!2 12 In addition, we demon- strate versatility requirements on the train data such that the learned parameters generalize both to the test distribution and -iit----istriuttion (length generalization). By nei- ther imposing restrictive constraints on model parameters nor limiting ourselves to particular domains, our framework unifies some diverse application scenarios and offers a novel theoretical lens on how Transformers learn dependencies among multiple interacting entities.
In Section 7, we provide experiments that validate our theoretical predictions with clear interpretation of the learned parameters.
In Section 5, we introduce HyperFeatureAttenttne novel mechanism designed to capture couplings of feature interactions. In Section 6, we present Hyper- Attention, which models higher-onler dependencies between entities, such as three-way and four- four-way in- teractions. Also, we provide accompanying theoretical analyses of these models' capabilities. We also provide some preliminary experiments on these novel models in Section 7.
a
Related Works.
We further validate our theoretical insights on representation, convergence, and generalization through controlled exper- iments, demonstrating that the learned model parameters closely align with theoretical predictions. Beyond analyzing attention patterns, we highlight how the parameters them- selves can be directly interpreted to uncover meaningful interactions among entities.
Transformer Representation Theory. A large body of work has illuminated the representational abilities of self- attention from various angles (Yao et al., 2023; Bhattamishra et al., 2020a; Wei et al., 2023; Kajitsuka & Sato, 2024; Nath et al., 2024; Luo et al., 2022; Li et al., 2024). For instance, Transformers have been shown to be Turing-complete and capable of simulating intricate sequential computations (Bhattamishra et al., 2020b), act as provably efficient "com- pilers" for domain-specifie languages (Zhai et al., 2024), and approximate key operators such as sparse local aver- aging with sublinear complexity (Likhosherstov et al., 2021; Sanford et al., 2023; Edelman et al., 2022). Their abilities and limitations have also been explored in POMDP settings (Lu et al., 2024), automata theorrett perspectives (Liu et al., 2023), sequence-te -eeeeueeee tasks (Yun et al., 2020), and sequence hidden Markov model learning scenarios (Hu et al., 2024).
Building on these insights, investigations confirm that self- attention excels at capturing mutual interactions between entities. Motivated by this, introduce two novel gener- for capturing couplings of different interactions between features of the entities, and (ii) HyperAltention, for capturing higher-order interactions (c.g. three-way or four-way) between entities. Extending our single-layer analysis, we show that Hyper- FeatureAttention can efficiently represent the couplings of feature interactions. In addition, we show that HyperAtten- tion can represent and learn higher order interactions, with the corresponding theories.
alizations named (i) SnpeereeauurAAtteniiie
Transformer Convergence Analysis. Parallel to the progress on representation, another line of research has investigated the convergence properties of training Trans- formers (Ahn et al., 2023; Tarzanagh et al., 2024; Li et al., 2023; Tian et al., 2023; Song et al., 2024; Huang et al., 2024a: Chen et al., 2024). These studies analyze train- ing via gradient flow in simplified yet insightful settings (Yang et al., 2024), establish conditions under which one can efficiently learn multi-head attention layers (Chen & Li, 2024; Deora et al., 2023), or employ mean-field methods to show global convergence in large-scale regimes (Gao et al., 2024). Additional works examine specialized domains such as masked visual pretraining (Huang et al., 2024b) and spa- tial structure learning (Jelassi et al., 2022), or investigate sparse token selection tasks (Wang et al., 2024).
We summarize our main contributions as follows:
In Section 3, we present a unified perspective where each token (e.g., agent, amino acid, pixel patch) is treated as interacting entity, seamlessly bridging several experimental settings.
In Section 4, we show that gradient flow, on standard mean squared error loss, converges to a solution that captures how the entities interact. Furthermore, the learned parameters generalize to both unseen exam- ples from the task distribution and out of distribution (varying sequence lengths), under suitable versatility conditions in the training data.
Despite the valuable insights offered by these studies, the majority have all or some of the limitations, i.e. (i), (ii), (ii) we listed in the second paragraph of introduction.
requires Okk) parameters represent the interaction function, dense layer requires O(k I.²) parameters. we motivate this choice further in subsequent sections, but briefly: linear self-attention preserves essential optimization prop- erties of full Transformers while offering reduced computational complexity and simplified theoretical analysis (Ahn et al., 2024), making it ideal for theoretical investigations. A detailed discussion of linear self- attention appears in Section 2.
'If linear
2. Preliminaries
Self-Attention. The self-attention mechanism is a core component of Transformers (Vaswani et al., 2023), enabling
2

---

A Theoretical Study of (Hyper) Self-Attention through the Lens of Interactions
models to learn dependencies between input tokens effec- tively. For sequence of L. input tokens represented as matrix X E R2xdd the self-attention is defined as:
functions in context (Cheng al., 2024). Furthermore, (Ahn et al., 2024) demonstrates that linear self-attention replicates key optimization dynamics of Transformers -such as heavy- tailed gradient noise and ill-conditioned loss landscapes- without softmax or feedforward layers. This simplification retains the computational advantages of linearity while en- abling rigorous analysis of phenomena like adaptive opti- mizer superiority (e.g.. Adam over SGD) and gradient con- vergence. Critically, insights from this abstraction extend to softmax-based Transformers, particularly in understanding optimization stability and generalization under varying data distributions or model depths (Ahn et al., 2024).
SA 0 (X) = XW ( XWV,
vdk
where Wº, W W E dddd are the learnable projec- tion matrices. Deñning C = wQ(W*) //dg, we can write the same equation as
(X) = a (XCXT) XW
Since the introduction of attention mechanisms (Bahdanau et al., 2016), the function a _ + R has been predominantly implemented as row-wise softmax opera- tion, where the input matrix to a, commonly referred to as the attention scores, determines the relative importance of different tokens in the sequence.
In the following sections, we explore the capabilities of linear self-attention across diverse tasks to illustrate its practical and theoretical value. By striking a balance be- tween tractability and expressiveness, linear self-attention offers powerful framework for investigating and enhancing attention- based architectures.
Alternative Attention Functions. Recent advancements have explored alternative a functions beyond the tradi- tional softmax. One prominent direction is using linear self-attention mechanisms, which reduce the computational complexity of self-attentio from ((L?) to (LL). Lin- ear attention methods approximate the softmax function while maintaining comparable performance in many tasks (Katharopoulos et al., 2020; Choromanski et al., 2022). For instance, the Performer model introduces kernel- meth- ods to approximate the softmax operation efficiently, achiev- ing scalability without significant loss in accuracy (Choro- manski et al., 2022). Moreover, alternative activation func- tions, such as ReLU, cosine, polynomial and sigmoid based transformations, have been explored, showing competitive or even superior performance compared to softmax in some tasks (Koohpayegani & Pirsiavash, 2024; Kacham et al., 2024; Ramapuram et al., 2024).
3. Representing Mutual Interactions with Attention
Consider discrete finite domain (or "vocabulary") S = {a, w,,,,... with cardinality S|. In our setting we have tuples of L elements (or sequences of length L) from the domain, denoted by X' and entries of which are uniquely indexed by the integers in [L]. Here, [i] denotes the set Z+ For each index we
1,. - 1} for any denote the corresponding element X (i) S. Thus, we can write X' = (X' (0) X' (1). ..... X (L - 1)), which is distributed according to X' ~ D. We also have tuples y with elements from a corresponding relatively small set Sy. The tuples are jointly distributed according to a task distribution (X ~ Dxxx. In order to train a neural network, we map each element of S to d-dimensional embedding space via a function x S - Ed and each element of Sy to corresponding vector or scalar depending on the task, via the function y : Sy + Rdd Additionally, we stack the embeddings of the elements in X' and y as rows of X E RLxdd and Y E 2xdd matrices. We denote their distribution as (X, Y) ~ PXXY
To simplify theoretical analysis while shedding light on a diverse range of self-attention implementations, we adopt a linear variant of self-attention, which preserves the core characteristics of self-attentio through its reliance on atten- tion scores.
Linear Atte-tttenioon Linear self-attention simplifies the attention by omitting the a operation, resulting in:
Our first result concerns self-attention' the representation for mutual interactions, which we define below. We introduce pairwise effect function. For a E S, let [(a,, 3) E R measure how strongly entity 8 affects entity a, and let W E Rdd represent how that influence is expressed. The aggregated effect on the i-th entity, from all other entities, is
SA lin (X) = (XCX) X XWV.
(1)
Although omitting the a operation may appear to be over- simplification, extensive theoretical and empirical studies confirm the power of linear self- self-attention. Notably, layers of linear self-attention can implement gradient descent and pre- conditioned gradient descent (von Oswald et al., 2023; Ahn et al., 2023). In addition, variants of softmax, ReLU, and linear transformers (including the exact version used here) can perform functional gradient descent to learn nonlinear
Σ ((x (i) Wx JE(L]
Yx()
capturing mutual interactions: each entity's behavior or state depends on every other entity in the sequence.
3

---

A Theoretical Study of (Hyper) Self-Attention through the Lens of Interactions
Theorem 3.1 (Representation Ability of Linear Self-At- tention). d = |S] is sufficient for a single-layer linear self-attention to exactly represent any aggregate pairwise interaction functions xyx in Eq. 2 for all entities si- multaneously. Also, d 2 |S| is necessary for a single layer linear self self-attention to exactly represent any such functions.
Appendix B.I, we can write jth agent's effect on 1t agent's s value function as, [r, (r;) Wry, where Wry RR is scalar weight and f depends only on their relative position. Then we consider the value function of the i-th agent as
VA,
((ri-rr) r2)) Wry,
Consequently, self-attention requires @([S?) parameters to capture the interactions. The key distinction, however, lies in efficiency. The following theorem demonstrates that self-attention is efficient compared to fully connected neural networks. This kind efficiency is one of the reasons we contend that Transformers are mutual interaction learners, while generic fully connected architectures are not.
841
In Appendix B.I, we illustrate how a reward of -1 per distinct collision is captured by the value function above. This function fits directly into (2), allowing single-layer linear self-attention to represent the multi-agent value func- tion, when discrete positions are encoded orthogonally, In addition in Appendix B.1 we show similar results for non- identical agents setting, too.
Theorem 3.2 (Efficiency of Self-Attention). A linear fully connected network requires S2(I,2 |s(²) parameters to rep- resent the aggregate pairwise interaction functions {y: {y: in Eq. 2 exactly, for all entities simultaneously.
Example 2 EGenotype-Phenotypn Mapping Task), In many venotype-phenotyy models, a DNA sequence of length I. is composed of alleles which we represent as X' (i) S. Some alleles are always active, others' acti- vation level depends the presence of certain alleles, and some remain inactive regardless of context (Frommlet et al., 2016). Formally, in simplistic setting,
The proofs of Theorems 3.1 and 3.2 appear in Appendix B. Equation 2 and Theorem 3.1 underpin all later examples: the same simple formula can model multi-agent rewards, pixel patterns, time-series signals, and genotype-phenotyy rela- tions, showing that one self-attention layer already captures rich pairwise dependencies.
Px(2))
II {x (i) is always active}
A more practical interpretation of these results appears in the context of deep neural networks with modular per- spective. Learning algorithms, such as gradient descent applied to a loss criterion, often lead to the emergence of task specialization within small subcomponents of a large neural network. Specifically, individual neural network blocks naturally become responsible for particular subtasks -a phenomenon studied in (Elhage et al., 2021: Cammarata et al., 2020). Our representation theorem formally demon- strates that each self-attention block is indeed sufficiently powerful to execute any mutual interaction task potentially allocated to it within a deep neural network, so theoretically supporting the more empirical observations.
Σ II (x) is activated by X (j) wx()). JELL]
where Px(() captures activeness of the gene at position i. By orthogonally embedding each allele, Theorem 3.1 again ensures a single-layer linear self-attention can replicate these interactions exactly. For more details see the demonstrations at Appendix B.2.
We illustrate the generality of our theory with several addi- tional case studies, time-series prediction (Appendix B.4), computer- vision task (Appendix B.3), and variants of the colliding-agent environment (Appendix B. Study- ing isolated single-layer self-attention models uncovers component-level behaviors that directly inform the design and optimization of deep Transformer architectures. This mirrors the role of circuit theory in electrical engineering: although large-scale designs rely on simulation and proto- typing, foundational insights about tramsistors, resistors, and capacitors remain indispensable. Likewise, our block-level theory is a step toward a datasheet for self-attention units, helping steer the construction of deep Transformers. Full- network experiments remain vital, but a precise block-level theory focuses the design space and boosts the likelihood of success.
We provide the details about this section in Appendix B and provide convergence and generalization analyses in Section 4. Finally, Section 7 presents empirical results that confirm our theoretical findings and provide interpretation of the learned parameters.
Example (Colliding Agents Environment). In a multi- agent system with L identical agents positioned in a dim- dimensional space, with position vectors r, E Rdim (or I: E [N]dim for a discrete setup). We aim to capture how each agent's value function Vr, depends initial states (positions). Seeing that the system is transla- tionally and rotationally invariant, as explained detailly in
other agents'
Why d = |S| While setting the embedding dimension d equal to the domain size [S] may be impractical for large vocabularies, it simplifies our analysis without altering core insights. Our goal to understand how self attention cap-
In reinforcement learning context, the value function Vr, for agent typically denotes the expected return (sum of discounted rewards) from a particular configuration.
4

---

A Theoretical Study of (Hyper) Self-Attention through the Lens of Interactions
tures mutual interactions, and d |S] ensures orthogo- nal domain embeddings, yielding an exact and transparent representation. Compressing to d < [8] is perpendicular to this focus and can be addressed separately using stan- projections,
linearly independent, as redundant patterns (e.g., fixed linear relationships between element counts) are highly unlikely under unstructured or randomized data. Moreover, if the data distribution satisfies even milder assumption that the covariance of g(n) is positive definite (Assumption 1, we show in Theorem E.2 that IP (rank(S ) < [6)) S e- for some 7 E R, meaning Assumption 4.2 is satisfied with high probability.
dard techniques, such as Aehnnonn-Lindenstrenn to approximate nigh-dimensional orthogonal embeddings. Starting with d = |S] allows us to establish clean, exact theorems that elucidate how self-attention captures pairwise interactions, while reducing to d < |S| merely introduces small approximation gap without altering the core theory. For completeness, we provide an approximate version of Theorem 3.1 in Appendix B (Theorem B.2).
4.1. Convergence
In this section, we show that if the target function is repre- sentable by a single-layer linear self-attention model (as guaranteed by Theorem 3.1), then gradient descent on L L (C, W converges zero training error under mild conditions. It is stated below with proof in Appendix C.
4. Training and Generalization
In this section, we analyze how a single layer linear self- attention can achieve zero training error and demonstrate its generalization guarantees under mild assumptions. We focus on learning mutual interaction functions of the form (2), which, as ensured by Theorem 3.1, can be represented by linear self-attention.
Seeing that our main aim is studying the mutual interaction perspective, so the attention scores are the core component, which is also the core mechanism defining self-attention, we choose d2 = Thus, W is one dimensional which we denote as in this subsection. Lastly, we denote wn- = =(aa] w for any a E S.
simplify the convergence analysis.
Setup and Notation. Let {((1), ) be the train- ing data, where (Xim), Y(1) ~ P for specific L*, so in the training set all tuples have the same length L".
Assumption 4.3 (Weak Realizability). The task is realiz- able, i.e, there exist C* and w" that perfectly fits the training data. That is, y(n)
Also, let P&L Y be the universal distribution that covers samples of any length. Throughout, we focus on the mean- squared error (MSE) objective
C' (") T) x(") w" Vn E B.
Theorem 4.4 (Convergence to Zero Training Error). Let the dimensions d = |8| and d2 = 1. Also, let the initial parameters C(==)) = O, (x w((=))) 2 b > 0, Vo S. Then, under the assumptions 4.2 and 4.3, gradient flow on MSE (C, w) converges to zero training error.
MSE M, w
1 B
Σ
SA lin (x( - y
We address three key questions: (1) Convergence: Under what conditions does gradient flow reach zero training error? (2) Generalization: When does a perfect fit on the training set imply zero error on new data from y (3) OOD Generalization: Can such model generalize to longer or shorter sequences than those seen in training?
The realizability assumption decomposes into two parts: (i) the task genuinely involves mutual interactions, and (ii) the data are noise-free. The second condition, analogous to fixing d = (S), simplifies the presentation without alter- ing the core insight. Extending our results to noisy data is straightforward: in that setting, exact zero-error conver- gence is replaced by nonzero error bounds and probabilistic guarantees." 4 We leave such generalizations future work.
Definition 4.1 (Data Matrix for Element jt). Let B, as the set of training indices that contain element E S. Denoting the number of times an element μ appears in tuple (1) as
sj we define the data matrix for element y as
(n)
4.2. Test Generalization
s ((()= = {(((n)
(m)
(m)
Ss. [
s(n)
Under training data versatility and strong realizability, achieving zero training error with linear self-attention im- plies perfect generalization new data from the same dis- tribution. Moreover, under even milder assumptions, zero test error ensures generalization to unseen sequence lengths.
B
IEBB
In short, [Ss,]... 5/ but for n such that f E 2((m)
Assumption 4.2 (Training Data Versatility). For all μ E S, Sg, is full column rank.
Assumption 4.5 (Strong Realizability). The task strongly realizable, meaning there exist matrices Ct and WVt such that the model perfectly fits the underlying population dis-
This assumption is mild in practice. When elements in (x))
are drawn from a diverse distribution (e.g., uniformly with non non-degenerate correlations), the counts { for v E S naturally vary. This ensures that the columns of Ss, remain
Coondition (ii) mirrors the simplification in Newton's laws of motion, where measurement errors are simply neglected.
5

---

A Theoretical Study of (Hyper) Self-Attention through the Lens of Interactions
tribution at a fixed sequence length L*. Specifically, we assume that Y = (XCixT) XWVt holds almost surely for (X, Y) ~ Xxx
4.4. Discussion
Our theoretical findings in this section show that single- layer linear self-attention model not only converges to zero training error but also generalizes to both unseen data and unseen sequence lengths. In Section 7, we present controlled experiments, confirming our convergence and generalization guarantees hold.
Due to Theorem 3.1 and Appendix B, we can safely assume strong realizability.
Theorem 4.6 (Generalization). Suppose Assumptions 4.2 and 4.5 hold, than zero training error forces (C, WV) to agree with (Ci, WV on (X, Y) Pxxx. That is, the solution achieving zero training enror also satisfies
Building on the modular perspective introduced in Section 3, we view deep Transformer as a stack of self-contained blocks, each capable of shouldering a distinct subtask that emerges during gradient-based optimization. Our analysis shows that when a interaatittroatiinnn subtask is delegated to a single-layer linear self-attention block, that block provably (i) converges to zero error for the subtask and (ii) general- izes to unseen data and longer sequences. Earlier layer-wise results support this modular viewpoint. In deep linear net- works, (Shin, 2020) prove that block-coordinate (layer-by- layer) gradient descent reaches the same global optimum as full end-to-end training, provided every hidden layer is at least as wide as the input and output. For nonlinear architectures, (Zeng et al., 2019) show that cyclic block- coordinate descent converges to a stationary point at an (L/kk) rate, and (Akiyama, 2024) recently extend global- minimum guarantees to networks with strictly monotone activations (and, with skip connections, to modified ReLU nets). Although these results do not yet cover soft-max attention, they suggest that if each Transformer block can provably master its assigned mntual-interaattoon task as es- tablished here for linear self-attention then an alternating layer- wise schedule can, under suitable conditions, approach the performance of joint optimization. Our block-level theo- rem thus provides an "atomic" guarantee that future work can build on to analyze full Transformer training.
B(XYY) Borhirgy///Scc.w.. [5::w(()) -Y =0.
-
Hence, generalizes perfectly to new examples from the same distribution.
See Appendix D for the proof of Theorem 4.6.
4.3. Out of Distribution (Length) Generalization
A unique strength of oeff-attention is its ability to process sequences of variable length. In many tasks, we might train on sequences of length L. yet hope to predict accurately on sequences of different lengths L + L'. To state our result Theorem 4.8 (with proof in Appendix D.2), we need the following assumption, which holds due to Theorem 3.1.
Assumption 4.7 (Universal Realizability). The task is uni- versally realizable, meaning there exist matrices CVL and WVVL such that the model perfectly fits the population dis- tribution for all sequence lengths. Specifically, we assume that Y = (XC*LX XWV.LL holds almost surely for (X, Y) ~ ~PYL -xxx
Theorem 4.8 (Length Generalization). Under the Assump- tions 4.2 and 4.7, any Ct, WVt that generalizes to P
must generalize to P XXX-
Building the proof of Theorem 4.8 (in Appendix D.2), we observe key relationship between the matrices C and WY, which underpins the model's ability to generalize. We state this formally in the following corollary:
A key assumption throughout is training data versatility (Assumption 4.2). Intuitively, this requires each element in the domain to appear in sufficiently diverse contexts, en- suring the corresponding data matrix Sg. has full column rank. This richness is crucial for generalization, it allows the model to learn meaningful interactions that extend be- yond the training set. In realistic settings -where domain elements vary meaningfully (e.g., different agent configura- tions, protein sequences, or natural language tokens)- such rank deficiencies are unlikely. Consequently, data versatility ensures that the model not only fits the training data but also generalizes effectively to new distributions and sequence lengths.
Corollary 4.9. Two sets of parameters {c', W.))) {C2, w2.y lead to functionally equivalent linear self- attention blocks if and only if they satisfy
Tr. (..) -Ta.k (2.).. Ya,k, where
(C, W) = [xx (x) (xT ()).
WES
Consequently, you apply the transformation Tykk to the parameters, all of the sets of parameters that lead to func- tionally equivalent linear self-attentions be mapped to a specific matrix (over index μ. k) that depends on the func- tion they represent. Thus, for a specific task all length generalizing sets of parameters will lead to the same matrix under this transformation.
5. Extension to HyperFeatureAAteetiio
In the previous sections, we showed how self-attention learns pairwise interactions between entities. However, in practical scenarios, the entities p E S are not mono-
6

---

A Theoretical Study of (Hyper) Self-Attention through the Lens of Interactions
lithi.. In other words, they are composed of features. For instance, consider le be composed of M E Z+ features, μ = (1é1 .... :..: Moba)) ). where M4; E Sa,, so S x... x Spu Those features may be the (red, green, blue) components of an RGB pixel in an image or (height, weight....) characteristics of a person in a population or something else depending on the contex. To illustrate how the couplings of interactions between features are crucial, let us revisit the colliding agents environment of Section 3, with modifications.
From the preceding discussion, Linear HyperFeeatueeAtten tion requires only ( M) embedding dimension and parame- ters to express (3). One may concern that in practice we use layers of multi-head attention, which may possibly express Eq. 3, without exponential embedding dimension. However, we showed in Remark F.6 that even two layer multihead linear self-attention cannot express (3). After all these mo- tivations, we formally defined Multihead HyperFeatureAt- tention in Appendix F.2. Also, detailed comparison of the new modules' memory and computational requirements versus standard self-attention appears in Appendix H.
Colliding Agents Revisited. Assume the same setting as before except now the agents are not identical. We need labels for the agents & E St. Thus, each agent is composed of two features x; = r.). In Appendix F, we showed that for non-identical agents, is natural have the value function of the form
In short, similar to how self-attention generalizes dense lay- ers by enabling entity (token)-level interactions, HyperFea- tureAttention extends Self-Attention by enabling coupling between the feature interactions. It enhances traditional self-attention by allowing attentions to be coupled, which enables model to capture coupled feature level interactions.
) (II Wa (Tas)) (3)
;= Σ JE[L]
II fo (Po, Bas)) AeEA
aaEA
6. Extension to HyperAttention
where Da.i; Oaj. Ya.j are the corresponding features (label or position) picked depending on the scenario and fay Wa are some functions from features to real numbers.
Similar to pairwise interactions, some tasks may involve higher-order interactions, three-way four-way, n-way. Thus, in a tuple X' we may have μ S that is influenced by composite function of y and y E S. In this case, we would need our attention scores to be able to capture interaction functions of the form f(r, 7. From this need, we develop a novel generalization, named HyperAttention for capturing higher-order interactions, alongside (Sanford et al., 2023; Alman & Song, 2023). 8 Here we state third order and linear version, please see Appendix G for the full version.
Here we provide a simplified illustration of how Hyper- FeatuteAt emerges from our theoretical framework; see Appendix F.1 for a detailed motivation. Seeing that |S| = |+ from Theorem 3.1, a linear self-attention re- quires d = (( so O (((_)))))) parameters to rep- resent (3). However, defining new attention matrices, ((h,e) for each fa. we can represent the corresponding function parameters
only with (([S; ?). @([S, or (e)) depending on which features are used for fa. For example, [lt, requires O([Sal²) parameters. As result, if there are .M features, self-attention would require embedding di- mension and number of parameters in (M)))(M)) while defining attention for individual fa fa's only require ((M) (see Appendix F for exact calculation)." This brings us to HyperFeatureAAtennion
Definition 6.1 (Third order Linear HyperAttention).
Atju2 = Σ
Xia
Vindar Σ
X X125, ElEsT
WV
S1.5sE/d]
li HA
lin (X) = ir
Σ Visiar
Definition 5.1 (Linear HyperFeatureAttention of order A E Zt).
where we denote (i, k)-th entry of a tensor T as Tiyk and C Rdddddd WV E RRdxdxd2 and Table H.
C HEA (X) = II dE[A]
(
- II
XC T
VW dE[A]
Ternary Synergies in Multi-Agent Collaboration Imagine a multi-agent system in which each agent's 's payoff depends not just on pairwise interactions with other agents, but on three-way synergies. For instance, suppose agent i gets re- ward only if it forms an alliance with agents j and k, but
where I is Hadamard (element-wise) product between the matrices, and C(o), WV((a) E Rdxd
$ 'err, we do not assume knowledge of the features, we just assume each entity have some features.
*There are small differences between our definition and their ((Sanford et al., 2023; Alman & Song. 2023)) definition be- cause the way we reached to the architecture is different. For instance, their formulation is a low-rank approximation that as- sumes Vister Vi V22 In contrast, our approach offers more representational capacity while maintaining comparable efficiency.
'For an easy transition to the following example we sug- gest going over Appendix B.I -without the subsections- and Ap- pendix B.1.3.
"For more practical comparison of parameter counts with approximate represenations please refer to Remark F.1.
7

---

A Theoretical Study of (Hyper) Self-Attention through the Lens of Interactions
agents j and l does not form an alliance with each other. For- mally, each agent i has discrete state X' (i) that inclues its strategic type or coalition membership. Whenever i, J. and k all share a compatible configuration of states, gains an ad- ditional bonus. Concretely, define, / [xx (i) X (i) X (l:)), a ternary synergy function which is nonzero only when i, J. and are all in an appropriate joint configuration (e.g. is al- lied with j and & but j and l are not allied). Let (X)) be a weight that captures how the pair (j. k) specifically con-
the initial states. We leverage Theorem 3.1 and show how this reward structure and the final value function can be exactly represented by single layer linear self-attention. Under this setting, the final value function for each agent can be expressed as
1. VA,
- Σ 1f 1imin(1re (nn - n .N - |mX (onln S2 J3
(4) Seeing that the value function depends only on the y- coordinates, we focus our discussion on a one-dimensional case for simplicity. The extension to value functions with higher dimension dependence follows naturally and is illus- trated in Appendix B.1. We trained linear self-attention, for different embeddings one-hot and sinusoidal." It has an em- bedding dimension of N and its parameters are initialized as C = 0, (x (a), ((t))), Va E S.
tributes to i's reward under that triple configuration. Then agent i's total payoff takes the form:
Ve(0)
Σ ISiCKEL
xx))
In this setup, standard pairwise interactions (as in ordinary self-attention) are insufficient to capture the triple compat- ibility requirement. However, assigning each state X (-) a suitable embedding enables encoding these ternary syner- gies into a higher-order extension of (2), allowing the result- ing HyperAttentinn mechanism to learn how three agents jointly influence each other's rewards. We also provably explained how HyperAttention learns those higher order interactions in Appendix G.4.
One-Hot. We first use a one-hot embedding: each position n E [N] is represented by the standard basis vector en E R-V In Appendix B.I, we demonstrate how single-layer linear self-attention with WV =11N and
1, min(mm - n/,. N - |m - nl) S 2R, (5)
Cmn
For an additional example illustrating the representational capabilities of HyperAttention, see Appendix G.2 where we analyze the "sskiptrigram bug" (Elhage et al., 2021).
0, otherwise,
can exactly implement the value function (4), irrespective of L, so all realizability assumptions are satisfied. Under these, Theorem 4.4 predicts that the training mean squared error (MSE) converges to zero, which matches our obser- vations in practice. Furthermore, as the Theorems 4.6 and 4.8 predict, we see generalization results: negligible er- ror (9(10-7) on test sets both when L = 20 and when I. E (2, 5, 10, 30, 40} varies.
A potential concern is the ((T)) computational cost intro- duced by the final equation in Definition 6.1, which may pose efficiency challenges for long sequences. Leverag- ing techniques similar to those in (Katharopoulos et al., 2020; Choromanski et al., 2022), we address this issue in Appendix G.3. Also, detailed comparison of the new modules' memory and computational requirements versus standard self-attention appears in Appendix H.
Sinusoidal. We next consider sinusoidal embedding, in- spired by common positional encodings in attention models (Vaswani et al., 2023; Su et al., 2023). For even N, the position of agent i is mapped to
7. Experiments
7.1. Experiments for the Theories
2
2
P =
sin
ni
cos
Mi
V2"
N
N
We empirically validate our linear-SA theories, i.e. repre- sentation (Theorem 3.1), convergence (Theorem 4.4), and generalization (Theorem 4.6, Theorem 4.8) with the collid- ing agents environment.
2T
N
1
2TT
]
E R-
COS
n;
cos
2 144
V2
N
2
V2
N
Note that p; T Pj
7
N
S Due to Lemma B.4 and
Setup: Colliding Agents on a Cylindrical Grid. Consider identical agents on a cylindrical grid of size [N] x [N], with initial position vectors r, = [n] n²] E [N]a, with wrap-around in y (cylinder). Each agent modeled as a circle of radius R. executes simple "move-right" policy (one step to the right per time step if there is space to move, n. < N - 1, otherwise stays where it is). Whenever agent i collides with agent j (distinct), it receives a penalty of -1. Our goal is to capture how each agent's 's final total accumulated reward, that is the value function Vi, depends
Threorem B.6, a single layer linear self-attention with
W.V. = [-v2 O 0 ...] CVL E ERNNN such that
E RN1 and diagonal
4 (2R+ 3
if ====00 0, if Ju odd, if la even,
N
2 sin 37 (2R+
Cuu
N
sin +
sin 2 [2R+ (2))
2
N
sin 2 (5)
Under T. = 20, N = 360, and 100k.
8

---

A Theoretical Study of (Hyper) Self-Attention through the Lens of Interactions
Model
Order
Perplexity +
same embedding, MLP and optimiser settings (as in GPT3); HFA has the same @ time/space cost as SA, while HA (evaluated without low-rank tricks) scales (L)) in com- putation. The tables report the final validation perplexities. The results support our claim that the flexibility with richer interaction blocks improve language-moder quality.
Self-Attention
62.28
HyperFeatureAAtention
4
60.22
HyperAttention
3
51.26
HyperAttention (no sharing)
3
48.50
Table 1-layer, 1-head, 256-token window benemark All mod- els share GmTl-small hyper-parameters (deaode)=66 768, vocab size 50257. and identical optimiser settings). Training: k itera- tions, batch 0.16M tokens, cosine LR schedule with warm-up (7max=6 10 7/min 7max). Per-epoch validation perplexi- ties are Gaussian-smosee smoothed; final values are reported. SA and HFA have identical parameter counts and ((L²) compute; HA retains the same parameter count but, without the low-rank trick, scales as )L HA (no sharing) has slightly more parameters explained in Appendix G.
8. Conclusion
We introduced unifying theoretical framework that in- terprets tokens in self-attention as interacting entities and showed that a single layer linear self-attention mechanism can capture pairwise interactions across a broad range of domains. Our analysis clarified how self-attention learns and generalizes these interaction functions without relying on domain-specific assumptions. In particular, we proved that (i) such models converge under simple gradient-based training, (ii) they generalize to both unseen data, and vari- able sequence lengths when the training set is sufficiently diverse
Model
Heads / Order
Perplexity 4
SA
3/2 3/3
28.70
HFA
27.97
HFA22
4/(2x2, 2x3)
27.75
Building on our theories for self-attention, we introduced novel HyperFeatureAttention and HyperAttention modules that extend self-attention's abilities capturing couplings of different feature level interactions and higher-order in- teractions among multiple entities. Beyond the theoretical guarantees, our hanguage-oddeling benchmarks show that both HFA and HA consistently achieve lower perplexity than standard attention, confirming that their enhanced inter- action capacity translates into tangible performance gains.
Table 2. 3-layer, 1024-token benchmark. slyper-prammetrs and optimiser settings match Table 1. HFA incurs <0.1% extra pute over SA due to attention products. The hybrid HFA,2 (2 SA heads 2 order-3 HFA heads) attains the best perplexity.
can represent the value functions at Eq. 4 exactly, for any T., which is plotted Figure 1. The entries of C are simply Fourier transform of the interaction function, which is artifact of the sinusoidal embedding. Seeing that the same assumptions are satisfied for sinusoidal embedding, we ob- serve the same convergence and generalization results for sinusoidal embedding.
Taken together, our theoretical and empirical findings es- tablish self-attention -and its AlyperFeaturrAAttentio and HyperAttention variants- as efficient learners of complex entity interactions. Our manguage-modeling experiments confirm the feasibility of these modules, showing consis- tent perplexity reductions under matched compute budgets. A natural next step is to stress-test HFA and HA at larger scales and in applications such as multi-agent control, pro- tein design, and the other scenarios motivated in this paper. We hope this interaction-centrie lens spurs the creation of even more adaptable attention architectures and motivates deeper analyses of softmax attention, stacked transformer layers, and emerging attention mechanisms.
Although the results mathh the theorems, the learned pa- rameters do not overlap with the parameters we originally devised, especially for sinusoidal embedding, seen in Fig- ure 2 -these learned parameters lack an intuitive and easy interpretation. However, as discussed in Corollary 4.9, this outcome is a natural consequence of the generalization theo- ries (Theorems 4.6 and 4.8). Therefore, we focus on the ma- trices we get under the nontrivial transformation explained in 4.9, As shown in Figures and 4, these matrices are indistinguishable from the theoretical counterparts. With only @ (10-1) mean square distance between their entries. Thus, the parameters we get from training are functionally equivalent to the length generalizing parameters we devised.
7.2. Experiments for the Novel Modules
To verify that the theoretical benefits of our layers translate into practice, we ran two small-scale next-token- prediccionnni benchmarks on WebTett under hyperparameter parity with GPT3-small, see Tables 1 and 2. All models share the
9

---

A Theoretical Study of (Hyper) Self-Attention through the Lens of Interactions
Acknowledgements
languages, 2020a. URL http:////ar// 2009. 11264.
This research was supported by NSF Grants 2154171, CA- REER Award 2339112, CMU CyLab Seed Funding.
Bhattamishra, S., Patel, A., and Goyal, N. On the Com- putational Power of Trannformers and its Implications in Sequence Modeling, October 2020b. URL http: a arxiv. wrxiv.org/aaaiaa.a..o...o 2006. 69286. arXiv:2006.09286 [cs].
Impact Statement
This work advances the theoretical understanding of self- attention and its generalizations PlyperfFetturAAtteniio and HyperAttention- by providing a unifying framework for learning complex interactions. Our insights could ben- efit diverse applications, including NLP, computer vision, multi-agent systems, and scientific modeling. Improved interpretability and training efficiency may enhance model reliability and user trust.
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., Bemer, C., McCandlish, S., Radford, A., Sutskever, I., and Amodei, D. Language Models are Few-Shot Learn- ers. In Advances in Neural Information Processing Systems, volume 33, pp. 1877-1901. Curran Asso- ciates, Inc., 2020. URL https: http:///poocooeee./e//e/
While theoretical, our findings could indirectly impact real- world risks, such as biased decision- decision-making or misuse in misinformation and surveillance. Mitigating such risks re- quires policy measures rather than changes to fundamental theory. Additionally, optimizing attention mechanisms may contribute to more efficient models, reducing the environ- mental footprint of large-scale training. Overall, this work presents no unique societal risks beyond typical concerns in machine learning research.
A4SToobEEco.00111BBB9eeell222222 html.
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.om
References
https:/ddistill http::/dissill.pbb/222//iccccii wwtppp//////rriii......
Ahn, K., Cheng, X., Daneshmand, H., and Sra, S. Transformers learn to implement preconditioned gradient descent for in-context learning, Novem- ber 2023. URL http:: arxiv. org/ wtwgg//////....././///////// 00297. arXiv:2306.00297 [es].
Chen, L., Lu, K., Rajeswaran, A., Lee, K., Grover, A., Laskin, M., Abbeel, P., Srinivas, A., and Mordatch, I. Decision Transformer: Reinforcement Learning via Se- quence Modeling, June 2021. URL http: //axxiiv///vvv org/ abs//////// / 21 061066.00 01 01345. arXiv:2106.01345 [cs].
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.
Chen, S. and Li, Y. Provably learning multi-head at- tention layer, February 2024. URL http: //rvviv. org/ abs 2202244222222 04084. arXiv:2402.0408. [cs, stat].
org/abs/2310.. 01082.
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 244. 2024.
Akiyama, S. Block coordinate descent for neural networks provably finds global minima. 2024. URL https:// apenreview.o net. forum? 2ankiikaa
Cheng, X., Chen, Y., and Sra, S. Transformers imple- ment functional gradient descent to learn non-linear functions in context. In Proceedings of the 41st In- ternational Conference Machine Learning, volume 235 of Proceedings of Machine Learning Research, pp. 8002-8033 8037. PMLR, July 2024. doi: 10.48550/arXiv, 2312.06528. URL https: /ttpc//eeeddtee// ngs m
Alman, J. and Song, Z. How to Capture Higher-order Correlations? Generalizing Matrix Softmax Attention to Kronecker Computation, October 2023. URL https: //arxiv. wwtpxiiv.rr///...... abs/ /2100 0 04064v1.
Bahdanau, D., Cho, K., and Bengio, Y. Neural Machine Translation by Jointly Learning to Align and Translate, May 2016. URL http: / a arxiv wwwp/ogg///baa//.. 1109. 0473. 1oXix:1409.0477 [cs].
press/v235 hat/5//cheg2223 html. arXiv:2312.06528 [cs.LG].
Choromanski, K., Likhosherstov, V., Dohan, D., Song, X., Gane, A., Sarlos, T., Hawkins, P., Davis, J., Mo-
Bhattamishra, S., Ahuja, K., and Goyal, N. On the abil- ity and limitations of transformers to recognize formal
hiuddin, A., Kaiser, I.., Belanger, D., Colwell, I., and
10

---

A Theoretical Study of (Hyper) Self-Attention through the Lens of Interactions
Weller, A. Rethinking Attention with Performers, Novem- ber 2022. URL http:// axxiv. wxiivooo. www.:////ab///......///// 14794. arXiv:2009.1477 [es].
Huang. Y., Wen, Z., Chi, Y., and Liang, Y. How Trans- formers Learn Diverse Attention Correlations in Masked Vision Pretraining. 2024b.
Deora, P., Ghaderi, R., Taheri, H., and Thrampoulidis, C. On the Optimization and Generalization of Multi-head org/
Jelassi, S., Sander, M. E., and Li, Y. Vision Transformers provably learn spatial structure, Octo- ber 2022. URL http:/ /arxiv.v.v.. wwr.v.orr//vo abs/2210. 09221. arXiv:2210.09221 [es].
Attention, October 2023. URL abs/2332 12 280. arXiv:2310.12660 12680 [cs, math, stat].
Devlin, J.. Chang, M.-W., Lee, K., and Toutanova, K. BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding, May 2019. URLhttp:/ arxiv. orgoorgg//s... hatp///bb/111...../// /1800. 04805. arX0v:1810004805 [es].
Jensen, H. of Emergence. Higher Education from Cam- bridge University Press, doi: 10.1017/9881188877700 November 2022.
Complexity Science: The Study
URL https:
books /moolss/ccomllxttyysteeeee//// FD0611226EAA227777766666A6E 9781 108873777,, Publisher: Cambridge University Press.
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. org/ absaabs/22220 /201C. 11929. arXiv20010.11929 [es].
ISBN:
Jumper, J., Evans, R., Pritzel, A., Green, T., Figurnov, M., Ronneberger, O., Tunyasuvunakool, K., Bates, R., Zí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, S., Reiman, D., Clancy, E., Zielinski, M., Steinegger, M.. Pacholska, M., Berghammer, T., Bodenstein, S., Sil- D., Vinyals, O., Senior, A. W., Kavukcuoglu, K., Kohli, P., and Hassabis, D. Highly accurate protein struc- ture prediction with AlphaFold. Nature, 596(7873):583- 589, August 2021. ISSN 1476-4687. doi: 10.1038/
Edelman, B. L.,, Goel, S., Kakade, S., and Zhang, C. In-
ductive Biases and Variable Creation in Self-Attention Mechanisms, June 2022. URL http: arxiv. org/ abs/2110. 1 10000. arXiv:2110.10090 [es, stat].
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, J., McCandlish, S., and Olah, C. A math- ematical framework for transformer circuits. Trans- former Circuits Thread, 2021. https:/transformer- circuits. wttpsssuuub22//aaaeooottioio
$41586-021-03819-4 URL http:::tt//// //tpttss:://www// wwwww nature. com/ htt/aaatiiile.ee s 00441586-000 021 03819-2. lisher: Nature Publishing Group.
Pub-
Kacham, P., Mirrokni, V., and Zhong, P. PolySketch- Former:
Fast Transformers via Sketching Polynomial Kernels, March 2024. URL http: http/axxvvvv.ro.. abs / 2231 0. 01 655. arXiv:2310.01655 [cs].
Frommlet, F., Bogdan, M., and Ramsey, D. Phenotypes and Genotypes: The Search for Influential Genes, vol- ume 18 of Computational Biology. Springer, 2016. ISBN 978- 14----477--30--2. doi: 00.1007/978-14447-5533 URL /ttttps://iik..... Un..http::::inkssssiinng 1007/978-1 springer ccm/book/10.
Kajitsuka, T. and Sato, Are transformers with one layer self-attention using low-rank weight matrices universal approximators? In International Conference on Learning Representations (ICLR), 2024.
Katharopoulos, A., Vyas, A., Pappas, N., and Fleuret, F. Transformers are RNNs: Fast Autoregressive Trans- formers with Linear Attention. Proceedings of Machine Learning Research, August 2020. doi: 10.48550/arXiv. 2006. URL http:/ aaaxxiiiv... org/ abs 2206 16236. 1622 [cs].
Gao, C., Cao, Y., Li, Z., He, Y., Wang, M., Liu, H., Klu- sowski, J. M., and Fan, J. Global convergence in train- ing large-scale transformers. In Proceedings of the 38th Conference on Neural Information Processing Systems (NeurIPS 2024), 2024.
Hu, J., Liu, Q., and Jin, C. On Limitation of Transformer for Learning HMMs, June 2024. URL http: arxiv. org/
Koohpayegani, S. A. and Pirsiavash, H. SimA: Sim- ple Softmax-free Attention for Vision Transformers, March 2024. URL http: aaaaarxvvvvrro.. hat.v.org//bbss.. 2206. 08898. arXiv:2206.08890 [cs].
abs/ org/abs//
2406 6. 04089. arXiv:2406.04089 [cs].
Huang, Y., Cheng, Y., and Liang, Y. In-context convergence of transformers. In Proceedings of the 41st International Conference on Machine Learning (ICML). PMLR, 2024a.
Li, H., Wang, M.. Liu, S., and Chen, P.-y. theoreti- cal understanding of shallow vision transformers: Learn-

---

2210. A Theoretical Study of (Hyper) Self-Attention through the Lens of Interactions
ing, generalization, and sample complexity, 2023, URL htttp://axii..e org. abs 2302 06015.
erxiv.org/abs//100..0o 09864. Available at http: / //arxiv.org/ab//2222 09864.
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. 1326,, 2024.
Tarzanagh, D. A., Li, Y., Thrampoulidis, C., and Oymak, S. Transformers as support vector machines, 2024. URL http:://axxxv.ooo orw. abs/2308 6898.
Likhosherstov, V., Choromanski, K., and Weller, A. On the Expressive Power of Self-Attention Matrices, June 2021. URL http:: arxiv v. www.vvoorgggaaee wtgg/bs//10/000 03764. arXiv:2106.03764 [cs].
Tian, Y., Wang, Y., Chen, B., and Du, S. Scan and snap: Understanding training dynamics and token composition in I-layer transformer, 2023, URL http:://rxixs org/ //a//////// 2305 6380.
Liu, B., Ash, J. T., Goel, S., Krishnamurthy, A., and Zhang, C. Transformers Learn Shortcuts to Automata, May 2023. URL http::/tt///t. arxiv. 10749. arXiv:2210.10745 [cs, stat].
Tropp, J. A. An introduction to matrix concentration in- equalities, 2015. URL
01571.
Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, I.., Gomez, A. N., Kaiser, L.,, and Polosukhin, I. Attention Is All You Need, August 2023. URL http:// / /arxivi. org/ abs///////// / 1706. 0.7 62. arXiv:1706.03762 [es].
Lu, C., Shi, R., Liu, Y., Hu, K., Du, S. S., and Xu, H. Rethinking Transformers in Solving POMDPs, May 2024. URL http: arxiv. .rg. a/agg/bbs/200 2405.. 17358. arXiv:2405. 17355 [es].
von Oswald, J., Niklasson, E., Randazzo, E., Sacramento, J., Mordvintsev, A., Zhmoginov, A., and Vladymy- rov, M. Transformers learn in-context by gradient de- scent, 2023. URL http: org/ abs////b///// 2212. 07677. arXiv preprint arXiv:2212.07677.
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.
Wang. S., Li, B. Z., Khabsa, M., Fang, H., and Ma. H. Linformer: Self-Attention with Linear Complexity, June 2020. URL http: /wwpvv/aa/vvv//aa///a//eaa/aaaaa wwtg/bs///////ooo.eoo...o..eesse 2006. 04768. arXiv:2006.04768 [es].
Nath, S., Khadilkar, H., and Bhattacharyya, P. Transform- ers are expressive. but are they expressive enough for regression? arXiv preprint arXiv:2402. 15478, 2024.
Ramapuram, J.. Danieli, F., Dhekane, E., Weers, F., Bus- bridge, D., Ablin, P., Likhomanenko, T., Digani, J., Gu, Z., Shidani, A., and Webb, R. Theory, Analysis, and Best Practices for Sigmoid Self-Attention, Septem- ber 2024. URL http: / arxiv. wrgg/abs//40/ 04431. arXiv:2409.0443) [cs].
Wang, Z.,, Wei, S., Hsu, D., and Lee, J. D. Transform- ers Provably Learn Sparse Token Selection While Fully- Connected Nets Cannot, June 2024. URL http: arxiv. org/ hbs//ab///// /2os/2206..0 06893. arXiv:2406.06893 [cs, math, stat].
Wei, C., Chen, Y., and Ma, T. Statistically meaning- ful approximation: a case study on approximating tur- ing machines with transformers, 2023. URL http:
Sanford, C., Hsu, D., and Telgarsky, M. Representa- tional Strengths and Limitations of Transformers, Novem- ber 2023. URL http::/araa /awvvv...vvvv/////////ea. org arg/abs/2306. 02896. 2.XXv:2306.02896 [cs, stat].
/ www.iv.org/ea.. http:/ab///100// .31663
Yang, H., Kailkhura, B., Wang, Z., and Liang, Y. Train- ing Dynamics of Transformers to Recognize Word Co-occurrence via Gradient Flow Analysis, Octo- ber 2024. URL http: wrgg//s////a//// 09605. arXiv:2410.09605.
Shin, Y. Effects of depth, width, and initialization: A con- vergence analysis of layer-wise training for deep linear neural networks. arXiv, 2020. doi: 10.48550/arXiv. 1910.05874. UtLhttp:// http::///wxvvvvrrg/oe/e 05874.
Yao. S., Peng, B., Papadimitriou, C., and Narasimhan, K. networks can process bounded hierarchical languages, 2023. http:://axxi.../////// /ar//bs// 2 1...1.11..1
Song, B., Han, B., Zhang, S., Ding, J., and Hong, M. Un- raveling the gradient descent dynamics of transformers. In Advances in Neural Information Processing Systems (NeurIPS), 2024.
Yun, C., Bhojanapalli, S., Rawat, A. S., Reddi, S. J., and Kumar, S. Are Transformers universal approx- imators of sequence-to-sequees ary 2020. URL http:://aaxiiiii wwwp//rggg/bbbbeeeee.eeee abs/1912. 10077. arXiv:1912.100) [cs, stat].
Su, J. Lu, Y., Pan. S., Murtadha, A., Wen, B., and Liu, Y. RoFormer: Enhanced Transformer with Rotary Position Embedding. arXiv preprint arXiv:2104.0988 04409944, November 2023. doi: 10.448550/axxx.2214400090 URL http://
functions?, Febru-
12

---

A Theoretical Study of (Hyper) Self-Attention through the Lens of Interactions
Zeng, J., Lau, T. T.-K., Lin, S., and Yao, Y. Global conver- gence of block coordinate descent in deep learning, 2019. URL http: / arxiv. org httg/abs/1803 00225.
Zhai, X., Zhou, R., Zhang, L., and Du, S. Trans- formers are Efficient Compilers, Provably, Octo- ber 2024. URL
14706. arXiv:2410.14706 [es].
13

---

A Theoretical Study of (Hyper) Self-Attention through the Lens of Interactions
A. Notation and Definitions
Consider discrete domain (or "vocabulary") S - {ax, 3, w, with cardinality |S]. In our setting we have tuples of elements (sequences of length L) from the domain, denoted by X' and entries of which are uniquely indexed by the integers
in [L]. Here. [i] denotes the set {0, ....., i- 1 for any E Zt, positive integer. We define the function, X [L] + S assign each index i the corresponding element X (t) S. Thus,
write A' (X' (0) X' (1) ...... X (L- 1)), which is distributed according to X' ~ D. We also have tuples Yr length of which depends on the specific task we have, with elements from a corresponding relatively small set Sy. The tuples are distributed according to a task distribution (X,3) ~ Dxxy. When needed we use D and x to denote the same distributions for specifically tuple length of L. Similarly, D'L means the distribution covering all possible lengths. In training dataset, have B such pairs that (x'(7), ))(()) Dxxy, which are uniquely indexed by the elements in the set B = [B]. We also define, B3 as the set of training indices that contain
the element μ. We denote the number of times an element appears in tuple X²(x) as sj (n) We define the corresponding
s ((m)
5
(n)
(n)
S
(s())
s (2)
{B) BB and Sg, = [ s(x) s(n))...) ....IEB,, nEB.
matrices.
In order train neural network, we map each element of S d-dimensional embedding space via function : S + Rd and each element of Sy to corresponding vector scalar depending the task. We define the domain embedding matrix
x (a) x (B)
B =
(6)
Additionally, we stack the embeddings of the elements in N' and ) as rows of X E BR and Y E L matrices, which we say are distributed according to (X, Y) ~ P For training sample it can be written as,
x (X (O)
x
xT (L)
x
X
x (X (L 1))
where in the last equality we denote the embedding of the i-th element as x; == x(X (i)) E Rd, to reduce the notational cluttering.
We denote matrices and vectors by bold characters. Let M Rdixdd, Rd be any matrix and vector respectively. We denote k-thh row of M MR,: ma, similarly denote k-th column M. m We denote k-th entry of as my and (ks, ()-th entry of M Mat Similarly, if vector is defined in terms of blocks explicity state it and denote each the blocks as w T
w ...]] The same notations naturally extend to tensors, e.g., we denote (i.j. k....).tt entry of tensor T E ddxxxxx... as T Tijk...
In addition we denote tth eigenvalue of matrix M as A (M), where A (M) 2 A2 (M) 2 ..... ....iaalyr we denote the tth singular value as or (M). Lastly we have some operators diagonalization
W1
diag (w) =
wa
and Kronecker product of two matrices A E mxn, B E Raxq
aanB
a1 B
ai B a2
B
ag2 B
A B
ami
ame B
amn
B
where each entry di in multiplied by the entire matrix B, which results in matrix of size (mp) (nq).
14

---

A Theoretical Study of (Hyper) Self-Attention through the Lens of Interactions
B. Representation Abilities of Linear Self-Attention
Proof of Theorem 3.1 (Representation Ability of Linear Self Attention). We first show sufficiency of (8]. can define an orthonormal embedding x INN succh that
x(a)
x(3) [(a)(((3)
da,g Va,bEs,
where da,b is the Kronecker delta. Recall that (2) Dxxy are tuples whose elements indexed from the set [L]. Also, recall that we let 8 [L] + S map each index to its corresponding symbol X' (i) S. We arrange the embeddings x(X (i)) row-wise into X E R [x
Goal, We wish to represent the family of functions
Σ (xx x()) for each i E [4], SE[L]
Yx(()
using a single-layer linear self- dimension d = |S|. Here, f:S affects another, and x()) E Rdd2 encodes how that influence expressed (e.g., direction vector or contribution to subsequent feature).
S x S - measures how strongly one entity
Recall that single-layer linear self-attention be written
Attn Un (X)
(XCXT) XW"
where C e ddd captures the attention scores (keys x queries) in a linear setting, W E [ddds represents the values transformation.
Constructing C and V. We define and WV to satisfy:
x(a) Cx(B3 f(a. and x(a) W
Wa-
Such C and V exist because, (x(a)) forms an orthonormal basis in Rd due to d (S]. Concretely, C can be chosen that its bilinear form on basis vectors x(a,, x(3) equals f(a B). Likewise, WV can be chosen that x(a) maps to w..
Verification. Given sequence of length L, the matrix X E IR Lx (S| is
x(x (1)
X
Thus,
(0)
1(x X (T. (1)
XCXT
f(x - x))
f(x(L- - 1) (L - 1))
and
XWV.
x(11)
W WX(L-1)T
Multiplying these terms in the linear self eeffaattention expression yields, for each row E [Z]:
1-1
[XCX]) X xw",
Σ (xx (i) wxo)-
1=
15

---

A Theoretical Study of (Hyper) Self-Attention through the Lens of Interactions
This matches the desired function F, Ejet (i), (i) wxy)- Hence, a single-layer linear self-attention with dimension |S] can represent any pairwise interaction function of this form.
Now, we focus on necessity of d 2 |S|, Remember, f x R represent any pairwise interaction function. For fixed emheddings (x(a) )aEs and any matrix C Rdddd the product X C is at most rank d. Formally, if we stack all dictionary embeddings x(a) into matrix X E RlSixd, then
rank(X S d.
Thus, any pairwise function f(a, b) = x(a) Cx(b) produces an |S| x [S] matrix with rank at most d.
Consider the pairwise function (a, b) whose corresponding matrix F* e [|S) is full-rank, i.e,, rank (F*) = |S]. For example, take F [ss (the identity matrix), corresponding to f (a, b) 6.6 (the Kronecker delta).
If d < (S], then any matrix XCX has rank S and hence cannot equal F", which has rank(F") (F*) ) = |S] > d. Therefore, the self-attention mechanism cannot represent (a( b) exactly when d
|8|.
Since single-layer linear self-attention mechanism of dimension d < [S] cannot represent the full-rank function f², it follows that d 2 |S| is necessary to exactly represent all pairwise functions f(a.b).
As a consequence of the above Theorem, it requires O((S))) parameters to exactly represent any such sequence to sequence interaction mapping seen in (2). Further, the output dimension, d2, plays a largely peripheral role in the self- attention mechanism's is ability to capture pairwise interactions. Its primary function is to align with the desired output whether it be the dimensionality of subsequent features or the final embedding size- wwithout restricting the expressiveness of the attention scores. The latter dictated by setting interactions (a, B) can be effectively captured. Thus, d2 should not be viewed bottleneck; it simply design choice for how the represented interactions ultimately projected or stored.
representation whetee
[S], ensuring that all necessary pairwise
Corollary B.1 (Orthogonal Transforms Preserve Representational Capacity). Under d= 8), let x(a) be the orthonormal embedding constructed therein. For any orthogonal matrix Q Rdxdd, define the new embedding x' (a) Q((a). Then the same pairwise function f (a, 3) can be represented exactly by redefining
='=QQQ' and W QWW.
Hence, any orthonormal transformation of x(a:) leaves the representational capacity of the single-layer linear self-attention unchanged. Since the construction in the Proof of Threorem 3.1 (in Appendix B) relies only on the orthogonality of x(a). the same argument applies any embedding x' (a) = Q x(aa) with Q E Rddd orthogonal. Thus, representational capacity is invariant to the choice of orthonormal basis.
Proof of Theorem 3.2 (Efficiency of Linear Self Attention). We count the minimum number of parameters needed for a fully connected network.
Step 1: Because f(a, 3) can be chosen arbitrarily for each of the |S|² ordered pairs (a, 9). the model must be able to realize at least 2 independent scalar parameters to represent f itself.
Step 2: For a fixed position i, the quantity
Yx() = (1x wx
F=1
sums over 1,... L. Although there may be some degeneracies as (X' (X' for some j, kt, or f (2' (i) ,X ()) wxo) + + (X (i), X (k)) Wx(a) = (X' (1) (m)) w + (x)
wx(k) = vx)
wx())- that reduces the total number of parameters, we analyze the most general case. In the most general case, each (X (1) X ()) wx(g) in the summation should be calculated separately. Seeing that there are L such terms in the summation, fully connected network with no build-in parameter sharing cannot collapse these L terms at cost. Each summand could be different and must be learned with its own parameters. Hence, even for representing one output yx()).
the network needs ([. |
16

---

A Theoretical Study of (Hyper) Self-Attention through the Lens of Interactions
Step 3: The network must simultaneously produce ( ((()))).))))))) Without additional structure shared weights across output positions, fully connected network pays separate parameter cost for each output (x()))
Therefore, any linear fully connected network that realizes all such pairwise interaction mappings with zero error must have at least {2 ( parameters.
Theorem B.2 (Approximate Representation Abilities of Single-Layer Linear Self-Attentionn. Recall S is finite set and f x S - IR. is any pairwise interaction function. For each symbol μ E S, recall that wn E R2 is ( (value) representation. Suppose the embedding dimension is less than the domain size, d S (S). Then, there exist an embedding x S + R2, and parameters C E IR axd and WV E IRdxd2 for a single-layer linear self-attention mechanism such that, for any sequence
8 :: [L] + S, the output of the linear self-attention block
SA (X) = (XCX)) XWV,
approximates the "pairwise-sum" mapping
1-1 Yx() = Σ (1x, wxt.
(8)
3=0
such that for all, i 0, II,
LLo0t1 (F),
d2 S d < 18
[SA lin (X) Yxcalle <
LLa041 (F) + S2L/ Ede
Lindt1 (W)
d< d2 < S
GTaat (F) + 12 Disdti of (W).
| S d2,
where Ç1 maxpes [wlll C2 max dES One/ and (F) i-th singular value of F such that 0 o1 2 o2 2
(F).
Proof. Recall is the embedding matrix seen (6). Form an |8| x |S| matrix F such that Fa = s(uD) VU,eES. We have Rdddd so
Č BCB R Si(ss
an arbitrary matrix of rank most d. Similarly, let W E RlSixd2 such that W M4: Was and W BWV E Risixds Thus, for each i [L], we can write,
Yx( = Σ (((()x wx)
Σ Fx(),x0) Wxy).
(9)
JE[L]
JE[L]
As d < [S] and we can freely choose the embedding, we can choose the embedding such that the embedding base is orthonormal, i.e. T I, we can write
SA 1. = CX BUBB T B TBTBWB BW
Σ
Ex(0xx0 WV
W
(10)
3=0
We start the approximation by writing the singular value decomposition of F as
o (F),N,
where (F(F) ä-th singular value of such that o (F) 2 o2(F) .... 2..
We can set Ö to
Č= Σ o (F)uu,
17

---

A Theoretical Study of (Hyper) Self-Attention through the Lens of Interactions
which satísfies the only constraint have on C, that it is of rank d. Consequently,
S
C
Σ
o. (F
F
==++1
From classical linear algebra we get
max [Fg - Ccul S F - C oF).
(1I)
We can choose W to minimize |W W122. Note that the only constraint on WV is it of rank at most min (d, d2), because W = BW where w E Rd can be freely chosen and B E I2lSxdd is full column rank. Therefore, there exists a W such that WV W upper bounded by the min(d, d2) + I'st largest singular value W. Then, using the identity |||]] 22 || ||2 for any A matrix,
max E(Wi) W,y)2 IW
WW1,,
we have,
0,
d2 s d < [8|
max Eany - w1y) <
i=d+1 0. (W,
<< d2 < [S|
(12)
d= 0, (W)
< |S| < d2
Returning to Equations 9 and 10, the error can be written as
S Ji -x(())
Crouxs W PX(S), Wxos)
Σ
(Cx00.x60-Fxx00000 Wx6). + CXOLXO (Wren: Booh:-WWag Wx6x))
|SA lin yx(0)l22 Σ
(x(o) Fx(),00) |xxo)lll + +|xx00,800 W Wxox
Letting S1 max || Eo = max,, [mm]]
substituting Equations 11 and 12,
|SA Jin yxcal22
Σ
od+i (F) | (rroslll+ |xxxxxx0
Wr x()): WxO1
1=
(1oo4 (F),
d2 d |S|
GLaat1 (F) + S2L V Lizd4] 0i (W),
d< d2 < [S]
(Laaa (F) + 12 V Σ 2i=d41 0i (W),
d << |S| < d2
Justification for the d d (S Assumption. A common concern may arise from theoretical results, which assume the embedding dimension d equals the domain size (S]. While this may seem restrictive for large vocabularies, this assumption is well-motivated for the following reasons:
Clarifying the Core Mechanism and Simplifying Analysis. Our primary goal is to study how self-attention models interactions between entities, independent embedding dimension constraints. Setting d [S] ensures an
18

---

A Theoretical Study of (Hyper) Self-Attention through the Lens of Interactions
exact orthonormal representation, making both representational power and training dynamics fully transparent. This choice highlights the fundamental ability of self-attention to encode all pairwise interactions while simplifying the theoretical analysis without losing generality. By removing extraneous complexities, we preserve the core insights into representation, convergence, and generalization.
Establishing Natural Theoretical Baseline. The assumption d |S| serves an idealized yet expressive starting point in theoretical analysis, providing one-to-one mapping from domain elements to embeddings. This eliminates unnecessary confounding factors, allowing clean study of self-attention's 's structural properties. Future work can systematically extend these results to cases where d < [S], exploring compressed or approximate embeddings.
Scalability to Lower Dimensions. Although we analyze d |8], our insights extend to d < |S] through approximate orthonormal embeddings. Techniques such as random projections (e.g,, via the Johnson Linionn-Lnddesrruuus lemma) allow for efficient lower-dimensional embeddings while preserving essential properties. Thus, our results remain applicable in practical settings with small approximation errors.
In summary, the d |8] assumption is deliberate choice to make analysis transparent and tractable, enabling exact theorems that clarify the core design principles of self-attention. While not always practical, the insights gained from this assumption shed light on why self-attention mechanisms are so effective in learning interactions, thereby paving the way for future research on more approximate and scalable extensions.
Overview and Motivation the Following Examples this appendix, we present several illustrative examples that showcase how single-layer linear self-attention can capture important pairwise interactions across diverse domains: multi- agent collision settings, time series forecasting, genotype-phenotye mapping, simple vision tasks, and more. Although there exist many possible configurations, we focus relatively straightforward, yet representative cases that make it clear how to embed domain-specific features into our theoretical framework.
B.1. Colliding Agents Environment
We consider L identical agents a cylindrical grid of size [N] x [N], with initial position vector r, [n ny E [NT2, where y axis is looped, that is, the distance between n. = 1 and n. = N - is just 2. An analogy for such grid world is that ants moving on the surface of water pipe. Each agent is modeled as a circle of radius A executes a simple "move-right" policy (one step to the right per time step if there is space to move, n.." < N 1, otherwise stays where it is). We denote the value function for agent i as V,, which corresponds to the expected return (sum of discounted rewards) from a particular configuration.co Our goal is to capture how each agent's value function Vi depends on the initial states (positions) of other agents: whenever agent collides with agent j (distinct), receives a penalty of -1. Leveraging Theorem 3.1, we show how this reward structure (and hence the value function if continuing in time) can be exactly represented by a single-layer linear self-attention mechanism.
Under this setting, adding 1 bias to all value functions for simplicity, the value function for each agent can be expressed as
VE,
Σ
Imin (nn n N I n²)) 2R} (-1)
(13)
JE[L]
J
Seeing that the value function depends only on the y-coordinates, we focus our discussion on a one-dimensional case for simplicity. The extension to value functions with higher dimension dependence follows naturally and illustrated after the one-dimensional case discussed here. In addition, we provide two versions of the similar representation construction for different positional embeddings.
1.1. ONE-HOT EMBEDDING
One of the most straightforward approaches is to embed each agent's 's position n; E [N] as the standard basis vector e,, E R Concretely, n,-th entry of en, is one and the rest are zeros. This guarantees e, eny = 6ngmy, making the emhedding orthonormal.
Representing the Collision Value Function. By Theorem 3.1, there exists a single-layer linear self-attention model (dimension d N) that encodes the collision-based value function VÚ via an appropriate choice of C E RNN and
19

---

A Theoretical Study of (Hyper) Self-Attention through the Lens of Interactions
W IR-x1, To represent the value function in Eq. (13) using single-layer linear self-attention mechanism, we explicitly construct the attention weight matrix C and value projection matrix WV. Define W RRNx as vector of all -1s
w 1N [-1
(14)
This ensures that the output of self-attention sums over the interactions weighted by C. The interaction matrix C RNNN is defined to capture the penalty for collisions:
Cmn = 1, min(Im - m/, N - mm - n|) S 2R,
10, otherwise.
(15)
Here, Cun = whenever the y-coordinates m and n are within radius of 2R, accounting for cylindrical wrapping. The resulting attention computation effectively sums over all nearby agents within the collision range.
B. SINUSOIDAL EMBEDDING
We now consider sinusoidal embeddings, inspired by various positional embedding techniques that leverage sinusoidal representations. These include absolute positional embeddings from (Vaswani al., 2023) and the more recent rotational embeddings in (Su et al., 2023). Specifically, assuming N is an even number, we embed the position of the i-th agent as:
x (r;) = p. v2
sin (2mk ns)
cOs
(2N n:)
V2
cos
2T N
14)
v2
cos (T m.))
N 2
]
E RR
(16)
It is simple exercise check that p; Tp;
N 2
8s,5
The main result of this section is that: due to Lemma B.4 and Threorem B.6, single layer linear self-attention 1 with wv
1 0 ...] E NN and diagonal E R NxN, such that
N (2R + 2 sin 2n (2R+ +
if n 0.
Can
siu N m
if n odd,
2
22++
if n even,
sin (9)
can represent the value functions at Eq. (13) exactly, for any L, which is plotted at Figure 1. Definition B.3 (Discrete-Time Fourier Series (DTFS)). DTFS of a function f : [N] - defined as
N-1
F = Σ Tinle-1334
2=0
Lemma B.4 (Discrete-Toe Tinerett-Timeeeeee Fourier Series Expansion of Window Function). Let f be:
f|m] = [|ml| < 2R]
Then the DFS, F is:
sin (21+ sin
i
F[k]
34
(2R+5)
i
N
Proof. Straightforward.
Lemma B.5 (Real Valued, i.e. Sinusoidal, Expression of Discrete- Tameette-immeaee Fourier Series). The Discrete Fourier Series (DFS) of periodic discrete function æ[n] with period is given by:
N-1
x|n] = Σ X
km
A=
20

---

A Theoretical Study of (Hyper) Self-Attention through the Lens of Interactions
0.12
0.10
0.08
0.06
Cnn
0.04
0.02
0.00
-0.02
0
30
60
90
120
150
180
210
240
270
300
330
Matrix Index
Figure 1. Diagonal entries of the interaction matrix for N 360 agents with radius I 5. of collision dynamics in the agent movement model. The matrix indices are from 0 to 1.
The pattern emerges from Fourier analysis
Letting as [k] and bk - Im [X]],, the same function can be expressed
ag
2T kn .N.
2T
km ))
Og COS
+ by sin
forr odd N
2
<[n]
a0
ON/2
COS
2x N
Ti
Og c0s
wkv + by sin
2TT
kn
for even
2
Proof. Using Euler's formula, the complex exponential term can be rewritten as:
2T
cos
kn
+ +isin
kn
N
N
Substitute this expression into the DTFS equation:
N-1
x [n]]
X[k]
cos
kn
+ isin
km
N
N
Separate the real and imaginary parts the equation:
2T
2T
))
[n]
Re(X(k)} cos
km
[m]xX[A]]
sin
kn
N
N
2n kn
2n
[m(X[A]] cos
[e{X(]] sin
kn
N
in] is real function, so the imaginary part sums to zero. Therefore, for odd N we have:
lm{{[0]]
[m([[]]} + -Im(X[N- k} 0 because cosine function has period of
21

---

A Theorctical Study of (Hyper) Self-Attention through the Lens of Interactions
[e[]]] [e[[[[ ki}} 0 because sine function has period of
As for the even N have additional requirement:
[m(X[N/21 0
Thus z(n] for odd N is:
2T km
2T
km )):
ar []] [e(X
2 [e( cos
2 Im
[ sin
N
N
As for even we have:
u[n] Re(X (e
2TT
(2 kn ))
Re((X[1)] cos
km
( sin
N
Letting as = 2 Re([(() and by 2 Im ( we get the final form
a0
2nT N
2
))
0g
km
+ by sin
kn
for odd N
2
N
[m]]
00
2
ON/2
2
CO8
2T N
N
cos
2TT
N
km
+ by sin
2n
N
kmn
)
for even N
1=1
Theorem B.6. Let us denote DTFS of function f(r as F(k). Defining au = 2 2ee[F[k] and by -2 attention score matrix C of the form
00
01 b
bj
a1
(17)
aN/2-1
b
bN/2-1
ON/2-1
ON/2
represent any function f[n ny] P.CpJ. where p; is given Eq. (16).
Proof. Setting C as in (17),
40
ON/2
2T N
2T
2nT
Cp
cos
N 2 n
cos
kn
+ by sin
knn
2
2
N
N
A=1
That is equal to [m] owing Lemma B.5,
Remark B.7. f is symmetric, then the corresponding C is diagonal.
22

---

A Theoretical Study of (Hyper) Self-Attention through the Lens of Interactions
B. 1.3. MORE COMPLEX COLLIDING AGENTS ENVIRONMENTS
Value Functions That Depend Both Coordinates. Assume the same basic grid setup described earlier, but now suppose each agent's value function depends both coordinates. A trivial example is when agents receive huge penalties - -10 if they collide even though initially they are far away, i., dist(n4, ny) 2 R2 for some R2 R and any dist(-) function. They receive small -1 penalties, if initially they are very close, escaping from the collision is difficult. Thus, the value function becomes
Vi
Eum = 2R) (1 +1+9 I(distt,,,, ny) S R2))
where the x--cordiinate condition encodes temporal proximity. This value function, along with similar ones, can he expressed in general form as follows. Consider L agents on two-dimensional [N] x [M] grid, with each agent occupying a cell at integer coordinates r, the form
[ng n!] [N] Each agent's value function is then influenced by pairwise interactions of
V Σ JELL] j/l
Mr, (i--r) Wr;
En - ng. n n Way
JELL
where f [N] R measures how agent (via its relative position) influences agent i. To represent exactly linear self-attention kernel (as in Theorem 3.1), we embed each 2D position into vector of dimension N2, defined by the Kronecker (outer) product
P. P
p E N
Here, P E RN are the ID sinusoidal embeddings from Equation (16), applied separately the and y-coordinates. By construction, {pi]-r spans an orthogonal set in RVV, with one vector per distinct grid cell.
From 1D to 2D Discrete- Time Fourier Series. Recall from Lemma B.4 and Theorem B.6 that any function g(n) on a ID grid [M] can be written as p Cp, for suitably chosen matrix C. Precisely the same reasoning applies in two dimensions via 2D Discrete-Time Fourier Series (DTFS). Specifically, writes
N-1
N
fn - nn n - n) = Σ
Σ
F [K ky] e 2x (Ks (of-nn))+h (xx (x))
hg 00
and then rewrites each exponential in terms of sines/cosines matching the tensor-product embedding P 6 p.. Consequently, there exists block-structune C I N N² such that
p. Cp, = (1))-
Hence, by choosing V that p. + Wr, single-layer linear self-attention (dimension d = N2) recovers exactly the mapping
V, Σ s(r.- -ry) Wry- jti
All the ID collision arguments from earlier carry over: once the domain is embedded into R², Theorem 3.1 implics that single-layer linear self-attention can represent any pairwise function f(r, - -r)). Of course, this comes at the cost of embedding dimension 2 so the resulting kernel has size N N2,, 21) interaction.
N2,iie i.e an O(N4) parameter count for fully general
Non-Identical Agents. One can likewise handle agents with different behavior or policies. For example, suppose half of the agents always move right until they reach the boundary, while the others always move up. Label these two behaviors (or policies) via discrete set S, = (R, U}. and let each agent carry extra label y; Sy. Then the value function is
VeL.e = Σ >>(r Ij. 91. 93 Wr
(18)
JELL]
23

---

A Theoretical Study of (Hyper) Self-Attention through the Lens of Interactions
Following steps similar the value functions that depend both coordinates example, we now view the domain of each agent
8 Sq x Sz X Sy
where S and Sy are each [N]. Its cardinality is [S] 2 N2 in this simple example. We then embed each agent's label and position as a vector in I For instance, if q: R we might set
[
qi
P E RN.
2, = q P
P E
R2N
Likewise 9; U. we flip those two bits q: By expanding the definition of f(r; T 9s: 9j) via a suitable DTFS, again obtains matrix C of size (2N2) (2N2) that captures all pairwise interactions. Thus a single-layer linear self-attention with d 2N² dimensions suffices to represent Eq. (18). The parameter count grows to ((4N4) in the fully general case, but the construction exactly parallels the identical-agen -agent scenario.
B.2. Genotype-Phenotyy Mapping Task
Each allele (or gene variant) in the domain S is labeled with unique integer and embedded using one-hot vector. We consider a DNA sequence of length L in which every position corresponds to unique allele. In other words, each allele appears at most once in the sequence (no duplicates). Our experiments randomly sample activation relations: an allele E is activated if another allele y exists somewhere in the sequence. Symbolically, we might store these relations in a dictionary of the form
je [11, V2.....
meaning "allele i is activated by the set of alleles-vg" v: [] (an empty list), then allele is always active, while alleles not present in the dictionary behave like redundant or inactive genetic material.
Constructing C and W To model these activation patterns via single-layer linear self-attention we build C dxd and W E ddx1 follows (assuming each allele is one-hot embedded into Rd, with d {8)):
For every dictionary entry of the form i: [i...... Jmm] set
Ci = 1/m for each k: = 1,...,
and set all other entries in row i to zero.
For entries (i.e., allele is always active), assign each entry in row i 1. This ensures allele gains a constant contribution from the entire sequence.
Set every entry V (i.e., W E gdx1 is vector of all ones).
example dictionary may be [1:[3), 2:[], 4:[2]]. Seeing that we have one hot encoding
0
0
0
0
1
0
1/L
1/L
1/L
1/L
1/L
0
0
0
0
This is an example task for which single layer linear self-attention cannot length generalize. However, simple dense layer with ReLU activation addition after single layer linear self-attention, trivially enables it generalize any length
B.3. Vision Task
In this example, each loken entity corresponds to single pixel in image. Suppose there d possible pixel positions in the image, each with positional embedding p: E Rdd. We also have binary indicator by {0, 1} denoting whether pixel is black (6; = or white (6: 0). We embed each pixel jointly as
x; [b; pi]
1+d
24

---

A Theoretical Study of (Hyper) Self-Attention through the Lens of Interactions
Thus, the first coordinate captures color, and the remaining coordinates capture position. We want detect whether specific pattern of black pixels occurs around the position p;- Formally, want detect if pixels in set of relative offsets
A {Ai, .
are all black around position i. For example, might define a small pattern (e.g., 3 x cross), such that for each AS E A, the pixel p; + Ag must be black for us to declare "shape present at i."
Block-Structured C Matrix. Consider single-layer linear self-attention of dimension d + 1. Let C E [((+1)x(d+1) be stock-structured, meaning:
0
0 01xd
C
Odx1
Caxd_
where 0 denotes a zero block (ensuring that the binary coordinate b; does not directly alter which positions are relevant). want to detect shape around p, by checking offsets A (Ai....,Am. S R2, then for each i (representing p; in the submatrix), we set
1, if is P + A,
Ci.
0. otherwise.
This ensures P; attends to exactly those pixel positions P, that lie within the shape region around i.
Capturing the Binary Color. To incorporate the notion that only black pixels (by = 1) contribute, we define W R(d+1)x1 so that its entries corresponding to the binary part of x, are nonzero, while its entries corresponding to the positional part are zero. More formally,
1 0a
WV
I+d
Hence, when we multiply x, by WV. the outcome is simply by. In other words, by = the pixel contributes; if by 0, does not.
Overall Operation. Putting it together, single-layer linear self- self-attention
(x (xCx)) X V
behaves follows: (i) C identifies the relevant offsets py around each p,, i.e., it checks which pixels could participate in pattern (ii) W converts the embedding [bj. Py] into bj. effectively blackness indicator. (iii) Summing across the image yields, for each position i, the count of black pixels at the appropriate offsets A.
If this count matches the size of A, we conclude that the shape is present around pixel i. Thus, the linear self-attention mechanism can recognize patterns of arbitrary size and structure without changing the kernel size or other architectural hyperparameters.
CNN Versus Transformer: Theoretical Insight. A single-layer Convolutional Neural Network (CNN) with a fixed x 3 kernel cannot detect patterns larger than 3 within that same layer. Extending the receptive field would require either deeper networks or larger kernels. However, we do not know even the task of a layer in a large and deep neural network. Therefore, generally we do not know the required kernel for the task in advance, we just cross validate different over different trials. This design constraint makes CNNs less flexible when the optimal pattern scale is not known priori. By contrast, Transformers can attend to any subset of positions in the input- wwether nearby or distant- in single layer. In our example, the shape offsets A might be large or irregular, yet the same C submatrix can be adapted to capture those long-range relationships. Consequently, Transformers provide more versatile framework for shape detection (which is simply learning how different parts image interact with each other) or other vision tasks where the required pattern scale or geometry may vary significantly from one scenario to another.
B.4. Time Series Prediction
Consider a univariate or multivariate time series [m[t]]/] [-] where each m|t] E dR is the observed value at time t. We assume m(1 depends on a set of specific past delays = (1,,22,.. 12.... C N, along with scalar multipliers {ar] and
25

---

A Theoretical Study of (Hyper) Self-Attention through the Lens of Interactions
linear transform A Rd2xda capturing how past values affect the current state:
ag A mlt k]. m|d
For instance, if D [2,5]. then m|t] 3 A 3mm 2] 7 A ml 5]. For example, if D {2,5], we get m[!
3 A mlt - 2] + 7 A m
To embed each time step as an entity, define
[m[t], plt]] Rd+ds
where m]t] E I is the observed state, and p[t] E R a positional embedding (e.g.. one-hot or continuous encoding). An indicator-based formulation ensures the attention mechanism recovers delays in D:
m| +1
k)) mlj).
JELL]
RED
Our goal is to show how a single-layer linear self-attention can represent this dependency structure exactly, following Theorem 3.1.
We treat each time step as a distinct entity in the sequence. Its embedding x, E 1Rd+d combines:
[m[],, p[[]
where:
m[t] E Rd is the observed state at time (univariate or multivariate).
p[t] E Rd a positional embedding encoding the index This could be one-hot vector of length L, or a sinusoidal
embedding.
Define block-structured matrix C (4++)) separate the m[{ coordinates from the positional coordinates p(t). We can denote:
0 dg xd2
dgxd
C
dxd2
Caxd]
so that the positional part Č encodes which time delays matter, while the m[t] portion does not directly determine which indices to attend to. Concretely, let Ču,e if position v valid activator for position u under one of the delays in D, and 0 otherwise. Equivalently, can define
Ca,7
Σ anl uu--u--a
RED
if we index the positional embedding such that E (1....,A, L}. This ensures that time step attends to time step if is exactly one of the valid delays k behind u.
Next, we define W E (x to extract the actual state m|t] from each token:
A
W
0
dx
where E RRda is precisely the transformation from the autoregressive model. This construction means that when we multiply x; by WV, we obtain m|t), and the positional coordinates are ignored in this step (since their block is zero). Putting all together, a single-layer linear self-attention computes
(x (XCXT) XWV
For the row corresponding to the final time step I. + 1, the multiplication by C picks out those time steps j such that (L (1+1)-1 jjjj je D. Then multiplying by WV retrieves A mmj]]. Summing the contributions yields precisely
m| +1]
Σ az A m T. + k).
kED
mirroring the autoregressive formula.
26

---

A Theoretical Study of (Hyper) Self-Attention through the Lens of Interactions
C. Proof of Theorem 4.4: Convergence to Zero Training Error
Recall that B E RI is the embedding base matrix whose rows are embeddings of each element in the domain. We start with the following simple observation.
Lemma C.1. If the domain embeddings are orthonormal, that is (I(a), x(3)) = da,, V a, 3 E S, then X X diagonal in the embedding basis, and BX B diag(s(m)), where sy the number of times the element p appears in the n-th sample.
Since set d =|S|, we freely adopt orthonormal domain embedding, ensuring that
(B.., BB.) -
For the remainder of this section, we conduct all calculations in the domain embedding basis. To formalize this, we define the following orthonormal transformations:
X (n) one--hoo (
B
Cone-hot hot
BCB
W one-hoo Bw.
For notational simplicity, we omit the one hot superscripts the rest of this section. This will not cause any confusion as are always referring to the one-hot transformed versions. That whenever write X C, w, they actually represent X (1)) one-hot Coue-hot hot won--bot hot Also, seeing that B is orthonormal matrix, when we establish the convergence of the one-hot parameter representations, it directly implies the convergence of the original parameters, which can be recovered by applying the inverse transformation in the B basis. What we do is simply change our perspective to how we look at coordinate system. Lastly, in this section, we denote ep E R S as unique one-hot encoded vector for all E S, i.e. the base vector.
We will firstly derive the gradients of the loss function with respect to the parameters than we will state lemma that will be useful for the proof of Theorem 3.1.
Gradients of the L MSE (C, w) with Respect to C and w. For convenience, denote WV to verify the following equation:
R Rd.
It easy
Oe MSE (C, w)
1 B
(M)]
ac SA
2 SAlin
SA lin (x("i),
OL OLMSE (C, w)
1
D (())
2 Ow
SA
lin (x())
UC
dw
B
Since d2- the linear self-attention in Eq.1 can be written
SA lin (x(1:)
(xCx') Xw.
where w E Rdd We have
OSA lin (x(1i)
X, T
dCpr
Hence,
aL MSE (C, w)
2 B
x (m) ((1) (n) w], (x(!)) D(n).
dcn w
B
n=1
Similarly,
OSA
(X (n))
(XCXT) X.a:
Dwa
MSE (C, w)
2
(x()T)
(x()) CT x(x m(m)
owa
B
n=l
27

---

A Theoretical Study of (Hyper) Self-Attention through the Lens of Interactions
We write the same gradient equations as
aL MSE (C,w)
2
x
D w (x) x(),
8C
B
aL MSE (C, [C,w]
2
X (n)
X (m) C x D(")
Ow
B
Lemma C.2. If choose initial parameters as C(O) and wa (0) 2 b 0, then wa (1) 2 b> 0, Ya and Vt 2
Proof. Firstly, we will show that ua (1)² 2 wa (0)2, Vt and Vi, than we will prove the statement in the lemma. We can copy the previous gradient derivations and gradient flow equations
dC dt 17 0L MLE (C, w)
2 =-1 Σ
x
D
xx())
ac
dw ML (C, w)
2 =B Σ
x (m)
X m1)
dt 1]
Ow
Let A be matrix that is diagonal in the embedding base B. However, we again abuse the notation. We do not rewrite the one hot in A one- hot BCB" and denote it just as A in the rest of the proof. We can now write
CT dc
A
-1 Σ
x
(n)
D(x) W X (1) Tx(1)) A,
dt
B
n
Ti C dc dt
A = Σ
Tr
X
(1) D w x T A}.
A dw
T
=1
2 B
Σ
dl
Tr A dw w
T
Σ
Tr C _ (m) x(1)
D xx(m) (x(m)) A].
=
dl
B
n
Thus, we have
TecTdC } =Tr A dw
dt
dt
w
s
Th dC
ACT = Tr w dw
(19)
dt
dt
Seeing that A is diagonal A = A. Thus, from Equation 19 we can get
d
(IICACT)- - Tr(wT T Aw)) =
di
Ir IN(C(E)AC()T]) Tr(w (HWW((WA((() = T+(C())C(()) -r (())A(()))
Letting A = diag(e.), where ea is the unit basis vector corresponding to we reach to
2 = ( + (t) /C (0)12 w0(0)) + (t)..
where the last equality follows because C(0) 0. As result we reach to
(t) 2 2 (0) 2 6²
(20)
Seeing that dw, is finite Vt, w. (t) is continuous. As a result if w. (0) 2 b > 0. then (t) 2 b, Vt which can be proven by de contradiction. Assume 3t > 0 such that wa wa((t) S b. By Equation 20, wa (.()) < -b < 0. By intermediate value theorem Br E (0, (") such that wa (.(7)) = 0, so ( < w (0) > 12. which contradicts with (20)
28

---

A Theoretical Study of (Hyper) Self-Attention through the Lens of Interactions
Proof of Theorem 4.4 (Convergence Zero Training Error). Gradient Flow for the Residuals and the Loss. We define the residual (error) on the n-th example
D (
SA lin (x(r))
y(m)
Let / denote the (continuous) gradient-descent time, with
dC
0L
dw
0L
dt
8C
dt
=
11 Ow
Consider the time derivative of the residual
dD (m)
OSA lin (x(m)
(m))
dC
ÜSA
lin
(x(m))
dw dt
dt
aC
dt
dw
Expanding each term, we substitute
OSA lin (X!m))
w and OSA liu (x(m)
X/(ma)
[x(m)
T ((m)
(x(m) Cx(1) T) x(m)
8Cpu
Swa
As for the gradient updates we subsitute
dCw,
2n
(n)
X
[w] (x(1) D(n) and
dwa
2n
Σ B
B
x T) (x(*) Cx(1) D(
dt
B
dt
n=1
n=1
Thus, we arrive
dD (m)
X (m) (m) T ((m)
(-
27
x
(n)
x
(1)
1/www (x(x) (()))
dt
B
x (m) Cx(m)) T) ((m))
(-
2
x(n)T) (x (x(()))((
B
n=1
Rearranging terms,
(m)
217
( w x (m) T (m()) x(m) (())
dt
B
x (m) C
x (m)
x T Tx(x) C T ((n)
Seeing that the term in the parenthesis is scalar, we can write the same equation in terms for kronocker product for future convenience, which leads to
(m)
(m)
2n
Σ
B
X (m) T x (m) (m) ()) @ (x(m)
w
dt
B mm
(x(x + + c (m) (mm))(()) Tx(") x()) D(v) (21)
Stacking different samples with the following definitions
D =
D
M =
(x (x()) & (1)
M2 = (1(
29

---

A Theorctical Study of (Hyper) Self-Attention through the Lens of Interactions
can write the Eq. 21
dD
2n
[M
M2M D.
dt
B
We write the derivative of the loss
dL MSE (C, w)
2
dD (m)
41 1
D (m)
T
D
MM + MMM D.
dt
B
dt
m=1
Clearly, both MM and 2,M2 are positive semidefinite, so
dI, d., (C, w)
4 S - B
DJ MM D.
(22)
dt
Now, we will write Eq. 22 differently by re-expressing D. Thanks to the realizability,, we can write,
D (n) = (x (1) Cx(2) T) x(1) w (x(") C* x T) (()) w"
Due to Lemma C.2 w, + 0, so w"; s/w, is defined for all E [d]. Thus we can define, diag ww"
to be the diagonal matrix,
whose entries are w* s/W; in order.
D (n) (x T) ( w -(x(m) C* (()) x ding
W
In the orthonormal basis, (()) (x) is diagonal, which allows reordering to obtain
D (n) [c C diag w
(n)) ((1)
Vectorizing (using vec(A XB) (B A) vec(X)) yields
D(n) = (()) vec C C* diag w )}
Stacking over n produces D = Mvec(C C - C*'dia(w"" /w)). Thus, Eq. 22 can be written as MSE (C, w) dt <
4n B
MTMM D = vec
4n
C - C* diag w )] M T MM Mvee
C
C diag w )
B2
Using the Lemma C.3, the same inequality can be written
dL MSE (C,w) w)
4n
Amin (MMM) |[Moc[[ c C* diag w )]]l =
4n Amin (M M) |D]]3 Ba
S B2
dt
where Amin MM is the minimum eigenvalue of M Thus, if there exists constant & such that Amin (M (t))()))= v 0, Vt, then the training loss stops decreasing only when D reaches to all zero vector, i.e training loss stops decreasing only when it reaches to zero, which is stated more rigorously in Lemma C.4.
Lower Bound on the Eigenvalues of M. M. We can show that
Amnin (M M) O (M
M)
min u:
Mu
(23)
ul/a=]
where the first equality follow because M M is symmetric and positive semi definite. We also know
M Σ (a) x ww (n) x(m) @ (() (x))
Defining
Σ up
WES
30

---

A Theoretical Study of (Hyper) Self-Attention through the Lens of Interactions
where each Up R2,
| =
4 12 = 1.
(24)
#ES
Recalling
X
ex((i
(() TooTTxe (x()) as a projection matrix onto the space {ex(a)) ex(-)) Thus, using the mixed -roducct
ex(L-1))-
property of Kronecker product, write
M
Mu
Σ WEB [E
Σ
(1) [X()
ww ( T (x) ux(0)) @ ex(())
(25)
M Mul
EΣ Σ DEB
(
Tx(m) un
8/ (m)
Recall the definition B,, =In B: B: }(m)).50
MM IMMMul = Σ Σ
(s(() [x())x((m) (1) ww X (1) (n)Txe Tx())
un
2 e
(26)
WES B.B,
(n) ( ww ( (m))
11
PES nEB,
Σ (n) ddag (s(m) ww T diag (s(ii)
2
11
PES nEB,
Σ
diag (w) (()) diag (w) un
PES
n
diag (w)
Σ nE
((m) (()))(())
diag (w) un
(27)
Recall the SB, [... s(n)
EEB and define
diag (sp.) =
(n)
nEB,
Thus, we reach to Repeatedly applying the identity |Az|2 mmin (A) 2/12, 2, where A and are any matrix and vectors with suitable shapes,
| Mu
Σ
diag (w) Sb. diag (s,) SB, diag (w) un
MES
[ 2 2 Σ -t {diag (w)} o {diag (s on (Sv,) ||n
WES
Due to Lemma C.2, 2i {diag (w)) 2 82 > 0. By definition, o {diag (sw)} 2 1. By Assumption 4.2, oi.n (Sp 2
< 0. Because of the Equations 23 and 24, we reach to
Amin (M M) 2 6²g >
31

---

A Theoretical Study of (Hyper) Self-Attention through the Lens of Interactions Lemma C.3. For any matrix M, and any vector x such that Mx is defined, then
x MMM MM Mx 2 Amin (M M) ||x]]*
(28)
where Amin (M') corresponds to minimum eigenvalue of M M matrix.
Proof. Obviously A (M M) is symmetric and positive semi definite matrix, it can be diagonalized as A QAQ
and its square root A = A à defined uniquely A
QA QT. It follows that
x A = x A
= A QAQ T A
- A QQ A
Amiul Q A xx Amin Ax = Amial M
Lemma C.4 (Convergence Lemma). Consider the equation
x(() xtt)==nA(t(x())
(29)
Assume the following conditions hold
(i) A(t) is symmetric for all t.
(ii) The eigenvalues of Att) are lower bounded by positive constant, i.e,, Amin (A(()) 2 + 0, all for some sb 0.
Then, x(t) 0 as co.
D. Generalization Analysis of Linear Self-Attention
Let's denote the parameters we get from training as Ć and W. Also, to simplify the notation, just for this section, we define
Cpu x (n) Cx (v),
W = x (v) W.,k,
D.1. Proof of Theorem 4.6: Generalization
Remember that B is the domain embedding matrix seen in (6). Also, remember that (WVt.Co Ct} represent set of parameters that generalize to population distribution.
Proof of Theorem 4.6. Let Ć and WV be the parameters we get from the training. The zero training error condition corresponds to Y B
X (n) WV = xx WVt,
writing the same equation for each column separately, we get
x (") (x(
x C x (m) (1)
where wh is defined as k-th column of W Vt, Using B I, we write it in the domain embedding base
18
B BCB
T
BX (8) (1) (T Bw* BT B BX (1) (x) Bw**
By Lemma C.I.
(1) T (T diag ((()) (n)
58 )...)
32

---

A Theoretical Study of (Hyper) Self-Attention through the Lens of Interactions
Remembering the definition Õru x(p)) Cx(v) and via =x(a)* T w and similar definitions for Ct and W for any ,, E.
E
VES
WES Cj Chuwett =0, VHEX and V
Σs(r) (Cuorit
(30)
For each specific y and k, the terms the last equation parentheses can be construed as a vector with indices over v. Denoting that vector as ank and remembering SI, definition (from Appendix A), Eq. 30 can be written as
Sg, auk 0
Thanks to the Assumption 4.2, Sv, is full column rank so only solution to last equation a O, which corresponds to Currit = Che V u,, S, k E [d]. Consequently, for any X which is embedding of corresponding X D
ccxTxw's XC'x
Thus the learned parameters generalizes to all population, that is,
Ex || (xxXT)xW/X) =0
From the above proof, we can see that Assumption 4.2 not just plays critical role ensuring zero training error, but also leads to generalization to the entire population distribution. Specifically, this assumption ensures that any of parameters achieving zero training eтror must also yield zero population error, meaning there exists parameter set that perfectly fits the training data while still incurring some error at the population level.
D.2. Length Generalization
In the preceding analysis, showed that under mild assumptions, achieving zero training error leads to robust population-leve generalization for the specific length L from which training data is sampled. However, many of our inteacttoonbaase experiments naturally suggest length generalization: the outputs of these models are not inherently tied to fixed sequence length, nor did our experimental design depend on a specific number entities. That brings us to the Assumption 4.7. Despite this, our test-time generalization results do not formally guarantee -itt--dddittiuutionn generalization unseen sequence lengths. In this section, we analyze the conditions on D under which the parameters that generalize to the distribution DL" generalize to DVL
Remember that denote (C V.L) as the set of parameters that generalize to any length for the task of interest Also, we denote k-th column of the matrix V.T. as &.T. Let us first look at possibility of parameters that has zero error for XL DL but does not generalize to any other length J.. Writing them terms a specific length generalizing parameters and C w -defined accordingly to satisfy the following equalities-, O C. + C and W.LL" K.L. + w i E Xe1." and denoting k-th column of the true output for the input tuple X as ". (x*).
R. (x Uu
Σ
(C#t + Chte) (w.. + )
DEAL
Σ
(C + C C Ca w..
Cau w FL)
(31)
DENLI
Defining AL' = w.t + CA wh 7L + CA W.... vL, and combining the effect of biasses on the output,
ue
b (x())=
Σ
Co wy
KL
Σ A
pv
VEXLI
DEXLI
33

---

A Theoretical Study of (Hyper) Self-Attention through the Lens of Interactions
We write the bias on the function output that does not change the function output for the inputs such that | L", but may change the output for inputs with other I,,
Σ
kM
VEA
To illustrate this point, consider Ay.. and p,u
o nu, seeing that Eq. 31 is written μ X.
I--1
Σ
A = A + Σ
A =a- Σ
a
= 0.
L -
MEXL
"EXL"
MEN VF
However, when we feed an input X ~ D.. that L # L", we get
R. (x%)=
Σ
Σ
AL"
us
HEXL
VEXL
4/1 +
A 1. JAU
VEXL
A L
A L
1/2
+
VEAL
8 +
1
vE
L
1/4 + L
L" L
In particular, the last equation shows that an unseen sequence length + L incurs an additive deviation of from the desired target o L so the model generalizes every length if and only if this bias term vanishes, i.e., 0. This will be useful in the following proof.
L* 1
Proof of Theorem 4.8. To generalize to any length we should make sure that the population distribution for any length I** does not allow such a bias, that is, A 0, V p, v. From the previous discussion, for the set of parameters that generalize to population distribution DL" we know that,
Σ VE
A pv =0 0, XL DL
(32)
For each μu, we can think of Eq. 32 as a linear system of equations. and an infinite sample extension of SB, that is
Defining, 8T. =
AAL' 4ax
A 43
A 44
...]
E RIS.
S/ [... st
(33)
where 1/ is such matrix that each row of it sums to I.", Eq. 32 can be written as
S Sgz 8" 0, V S.
If S8= is full column rank for all μ, which is satisfied by Assumption 4.2, then A 0. Thus, generalizes any length.
Seeing that Assumption 4.2 inherently encompasses "S5, is full column rank", may seem that test generalization would always lead to length generalization, without any assumption. However, is important to note that Assumption 4.2 is not the minimal requirement for ensuring test generalization.
34

---

A Theoretical Study of (Hyper) Self-Attention through the Lens of Interactions
Remark D.I. For clarity, let look example class of tasks that for which $ is not full column rank. If there is constraint on the distribution D that the elements within X' tuple are unique, than S is not full rank since the column of 8. that corresponds element μ will be all vector. Which is means, that there are some possible parameters that ensure zero error on DL" but does not generalize to DL for any L.
Remark D.2. Under the realizability assumption, skip connections do not affect the values of the residues D allowing the same proof on generalization to apply in the skip-connected scenario.
Corollary D.3. Defining
Cpu x (1) Cx(v), (V),
Wek = x (V) W.,
follows from the proof of Theorem 4.8 that any C, WV that generalizes VL satisfies
Cav Wy
bk = W. uk
Consequently, you apply nontrivial transformation to the parameters, all of the length generalizing parameters lead to specific matrix that depends on the task at hand.
If two sets of parameters for linear self-an elffaattention lead to the functionally equivalent self seff-attentions, i.e. they will lead to the same outputs for the same inputs for any input output pairs, then under this kind of nontrivial transformation they lead to the same matrix. Thus with this transformation we simply show that although the parameters we get after training are the different than the length generalizing parameters we designed they are functionally equivalent to the length generalizing parameters we have.
E. Justificatiin for Data Versatility Assumption
In this section we justify Assumption 4.2, by showing it holds under an even milder assumption shown below. Assumption E.1 (Positive-Definite Covariance and Bounded Norm). Let {s(") j c. RS be ii.. random vectors.
Suppose there exist constants Smin > 0 and M > 0 such that:
(A1) Positive-Definite Covariance: The covariance matrix
Σ Cov(s(") [s(
-B(s
satisfies Σn S I.
That is, Amin (Σ)
0.
Sminn
(A2) Bounded Norm: The centered vectors satisfy
||s(m) - E|s < M almost surely.
(34)
Theorem E.2 (Full Column Rank with High Probability). Under Assumption E.1, let
s (n)
S
=
IR
BX(S
(n)
Then there exist positive constant y > 0 (depending on M, Smin and (S]) such that for all sufficiently large B
P Frank(()) < [ss]
< e BB
Equivalently, is full column rank with probability at least
B
35

---

A Theoretical Study of (Hyper) Self-Attention through the Lens of Interactions
Proof. Step 1: Center the rows. Define an : g(m)
E[s(()), so that E(a,]] and
Cov(an) a E.
Stack these centered rows into
a
a2
Bx|SS
=
E
ag.
Since each row of S differs from by a constant shift, rank(S) = rank(X) Hence it suffices to show X is full column rank with high probability.
Step 2: Expected Gram matrix lower bound. We have
B
A A
T
a
n=1
Taking expectation,
B BAT A = Σ
a = BE.
n=1
By Assumption E.I(AI), E 2 hence
E A] = B 2 I.
Step 3: Concentration via Matrix Bernstein. Define the centered matrix
Z == a Σ.
Note Z 0. Summing.
A
T Σ) (a,a,
Σ Zn
n=1
n=l
Each Zn is bounded in operator norm since
a lop
||an 12
M2 DEalpp
|| (finite).
Thus for a constant R,
Zn llop
S a 1lo + -1[llop R.
In addition,
lopp
| |Zmnlepp S R²,
Σ
E
BR
ap
Hence by a standard matrix Bernstein inequality (self-adjoint version) from (Tropp, 2015), there exist constant y > 0 such that
P P[|ATA - EAATA|II 2 B =
Σ Zm
2
22
Smin
In other words, with high probability, A A stays within half its expected value in spectral norm.
Step 4: Weyl's inequality implies strict positivity. On this high-probability event,
Amin (A AA 2 Amin (E[A A))
A A
E A
A Al
2 C2 2 B 22
Hence A T A is strictly positive-definite implying rank A) = []. Consequently, A is full column rank with probability at
least e->
36

---

A Theoretical Study of (Hyper) Self-Attention through the Lens of Interactions
Remark E.3 (Justification for Assumption E. In many natural data-generation processes, these assumptions hold:
Count Vectors from a Dictionary. Suppose each sample (((1)) is tuple of L elements drawn from vocabulary S. The row vector s(*) may represent counts (sa"), (a) ..... of how many times each element a, 3,... appears. If we (n) focus on the subset B of samples that contain μs, then sp 2 1, while the other 1 slots of the sequence are drawn from S \ {u} according to some distribution.
Positive-Definite Covariance. When these (I. - "remaining" elements are distributed a non-degenerate way (e.g., at least some variability in how the other vocabulary items appear), the resulting count vectors s(n) will have covariance whose minimum eigenvalue is strictly positive. For instance, under uniform choice of the I, 1 positions among the [S]- possible elements, straightforward calculations show each coordinate has nonzero variance and Amiu [) 0.
Bounded Norm. Since 0 S (w) < L for each element S, the count vector a, is trivially bounded by v L in Euclidean norm. Thus we can take M / S satisfying Assumption EA1(2
General Distributions. Even more general scenarios (e-g.. non-uniform sampling, correlated draws) satisfy the same assumptions, provided negative correlations are not too extreme to force Σ have zero eigenvalue. In practice, real-world data tends have enough variability so that Cov(s!")) is well-conditioned, meeting the requirement Amin(2)
Smin for some Smin > 0.
F. HyperFeatureAttentinn
F.. Motivation
The preceding discussions in Appendix lon value functions that depend on single coordinates, both coordinates, and both coordinates with nonidentical agents reveal fundamental pattern: as the number of features describing agents increases, the embedding dimension sufficient fully capture pairwise interactions grows exponentially, As a quick recap of representations:
For a single coordinate (e.g., 2), the embedding dimension is proportional to |Sz| N, the number of possible positions along the r-axis.
When extending to two coordinates (ar and y), the domain becomes S Sz x Sy, resulting in an embedding dimension of [8] 2 reflecting all possible 2D positions.
Adding agent-specific policies (e.g., S, (R. U}) introduces an additional multiplicative factor, so the domain expands Syy Sz x Sy, with |S| 2N22
We can even add new feature called "species", from a different nature, such as species E (H, P}. which would make the domain size even larger.
Now let us look at the colliding agents environments from Appendix B.1 and Appendix B.1.3, with a slightly more complex example, to motivate the novel HyperFeatureAttention
Non-Identical Agents Revisited. Consider L agents on S, [N] [N] grid, each with initial coordinates r; [nT n²]] [N]2. The agents have identities from & Sapes (H, P). The Hs get +1 reward if they catch (collide with) a P. but the Ps get -1 reward when they caught. The agents also have fixed policies qi S, {R, UJ. that agents with policy R always moves to right and policy U always moves to up. From our earlier step by step results in Appendix B.1.3 the value functions for the agents can be written as
Vi = Σ f(e l, n3 es) Wnz.ng.ar.3-
(35)
JELL) 14t
With our earlier discussion (Appendix B), we know that a linear atlf-attention needs (p(S)))S parameters to represent such functions, which is exponential in the number of features.
37

---

A Theoretical Study of (Hyper) Self-Attention through the Lens of Interactions
However, after careful thinking on each case in our experiment, one can write the value functions
V = Σ
[16 114 = P, = H| (q: = R, q, = U} (1 n n n - =n n
JE(
+1[4 = H, f = P) I (q: = R, qj -) n
+1(4, P. E H| I {q: = U, 93 = -1
+I(G- H, 4 P) T {q: U, q R] (1
+144 = P, 2 = H] I {q: = R, q = R| R]_[n==n]]
+I(4, H. E I {q: = R, 9j R) R]](n==]]]
+I( P, f H1] {{: U, q U31[1[=nj]
+I H. E I I (q:
U, 4 = ()1 (T P] (H)]
Defining
fay (4, 61 1 = -1
P]
fhr (4. 93) I (9: -
= =R}
Say (ri, r2) I [n," -nj = nn"="""""
-y)),
fha (L,, 4j) 1 1(4 P, = H, P}
for (q: 9₁) = 1l [g: = R,
the (n², m I nn)),
pho (Li, (2) I [4 PP = + +I = H, P)
fhr (q,, 9/) = [(g: -0;=UU--U)) UU
Jas (n,, n3) TI [n, ~ =n)).
why (4,) = 11 [C, = PP 1 = H},
and H = (h1, 22.,2,20, ha). 7 {a1. 0z) the same equation can be organized into
Σ NEN
Σ [JE(T.]
II fa (oa.n NaEA
II aaEd
w (1as))
(36)
where oh 0% Vh are the corresponding features picked by the corresponding functions." 10 Owing to our discussion from Appendix B, we can easily conclude that the functions flh be represented exactly with an attention score matrix of Ch
0g a, E [x|Spp] similarly for Sh we need C E R RRIS,I Sel and for f we need Ch e RIS+ As result 02
total number of parameters required is O((Sspes| + S + [8,12) which is linear in the number of features, much better than linear self-attention which was exponential. We can calculate the exact number of parameters instead of the big-O versions. For N 360, approximately 106 parameters is sufficient for ExperfeatureeAttetioon while self-attention requires approximately 10 parameters.
Implications for Attention Mechanisms. While the linear self-attention mechanism discussed in Theorem 3.1 can represent pairwise interactions exactly, its parameter requirements also scale with the embedding dimension d. This limits its applicability in cases where the number of features (or their cardinality) is very large. For instance, in scenarios with additional discrete features such as temporal information, behavioral categories, or hierarchical roles, the exponential growth in SS quickly becomes bottleneck.
The exponential growth observed here highlights the need for alternative attention mechanisms that can efficiently handle high-dimensions domains without explicitly embedding all feature combinations. This sets the stage for the introduction of
Equation 36 is more general than the toy example discussed above: in that example single (a, h) pair selects the same feature for its keys and queries, whereas the equation is written accommodate cases where the selected features may differ. Therefore, we used different symbols Φ
38

---

A Theoretical Study of (Hyper) Self-Attention through the Lens of Interactions
novel attention module HyperreatuueAlteetionn, designed specifically address exponential embedding growth while preserving the ability to model complex interactions across diverse features.
Also, one may concern that in practice we use layers of multi-head attention, which may possibly express Eq. 3, without exponential embedding dimension. However, we briefly go over in Theorem F.6 and the following justification that even two layer multihead linear self-attention cannot express (3) (which is easily expressed by a single layer single head HypeefeeaturcAAtenniinn)
E.2 SxpeeFeeaturAAtteniiie Definition
The non-identical agents revised discussion was just a toy example for setting the stage for our novel HyperFeature Atention model. Let us first generalize the discussion. We have & as the set of all features and M = |$| as total number of features in our setting that are distinct in nature. For feature Φ, denote its domain Sg. domain size |Spl, and allocated embedding size dg. From the previous discussion, represent any function of the form Eq (36) the total embedding dimension for
linear self-attention grows exponentially as d II |Spl and the corresponding number of parameters O (Ioco |8p))) However, using a function of the form,
(
(ii xW )] AEEA
6
HFA lin (X)
Σ
II x
LEEA
we only need embedding dimension of d=d=- = Epeo |So] and the corresponding number of parameters grows linearly in the number of features (M).
Remark F.1 (Note on Approximate Embeddings). Although the following discussion is somewhat perpendicular to main focus on how entities (or features) interact, we include it briefly for completeness. In principle, self-attention may require an embedding dimension exponential in the number of features, but in practice, one often leverages the Johnson-Lindenstrauss lemma: in nigh-dimensional spaces, random projections yield vectors that are approximately orthonormal with embedding dimension only linear in the number of features. Concretely, each feature Φ typically contributes Ollog (S&1) dimensions rather than ((Sa)) ). so total embedding dimension becomes d = O( 12 However, in HyperFeatureeAttentt this same Lindssn-Lindssstrauss argument implies a dimension requirement of Olog Φl) (rather than O({)))) Hence, even though both methods rely approximate embeddings, the exponential gap remains: standard self-attention requires dimension linear in the number of features, whereas our module reduces it to logarithmic.
module,
After all these motivations, we can now formally define the Multihead HyperFeature Attention. First, we provide the definition of Multihead Self Attention in (Vaswani et al., 2023) here for comparison.
Definition F22 (Multihead Self- Self-Attention). Let X E R denote the input sequence of T tokens, where d is the embedding dimension. Multihead self-attention computes sequence of contextualized embeddings as follows:
SA h = Softmax (T*) Va,
vh E fL.....H).
(37)
MHA(X) = (SA ..... SA WWO
(38)
where:
"In this comparison, we deliherately bias the setup toward standard self-artention by pitting two-layer, multi-head SA model against a single-layer, single-head HFA.
12Of course, some features more crucial than others and thus allocated more dimensions. In addition, while simpler ordered features (c-g. spatial coordinates) can often be embedded in far fewer dimensions. For example, spatial x-coordinates, are intrinsically one-dimensional, allowing them to be embedded into a much lower-dimensional vector space than [S.]] This is because z-coordinates form an ordered set with a linear relationship between positions. Conversely, features like the nucleotide bases A. G. T', and C' lack such linear relationships- -there is no linear relationship between "adenineness"" or "guanineness" - and therefore, these features tend to accupy 4-dimensional vector space. Some features, such as color, lie somewhere in between. Scientifically, single frequency (e.g.. 400 484 THz) is sufficient to specify the color "rose red," but practical encodings like RGB, it is represented by three integers (c.g.. [255, 3, 62).. However, in the language it even more complex. As explained in (Jensen, 2022), the qualities of the color red, such as its warmth or contrast with green, cannot be deduced solely from its frequency as an electromagnetic wave. Even less can its emotional associations -scch romance warmth- be reduced to property of the wave. Instead, these properties emerge from the collective processes generated by light absorbed through the eyes, which trigger hierarchy of neural processes in the brain. These processes ultimately lead to thoughts and emotions that we experience as color perception.
39

---

A Theoretical Study of (Hyper) Self-Attention through the Lens of Interactions
Q XWe", K XW and V XWW are the query, key, and value matrices for the h-th head, respectively.
d, #
d is the dimension of each attention head.
w w W E Rddd, and W E Rdxd are learnable weight matrices.
Softmax(-) (-) is applied along the last dimension.
Definition E3 (Multihead HyperFeeauueAAttentinn)) We define two versions of Multihead HyperFeature-Atteniinn, "value-
product" and coon-value-rroduct respectively. Let X E Rxxd denote the input sequence of 'I' tokens, where is the embedding dimension.
Softmax
πI aE[A]
Q (1
( ( (())
IT aE[A] V(h.o), if value product,
HEA h
(39)
Softmax
IT
Q (h)aa) (K(h,a) T
v(h, otherwise,
aEIA]
MHFA
Concat
HFA
HEA
wo
(40)
where:
Q (h,a) XwO Khh,a) XWk(ha) and (hh.a) XWVhh.) are the query, key, and value matrices for the
h-th head a-th attention score, respectively (V(h) XWV( for no value product case).
For each head we specify d, such that Σn dn = d and the attention size for that head is d = dz./A. A.
WQthe) w E Rdddd" wV wv Rdddd and Wo Rdxd are learnable weight matrices.
I represents Hadamard product of matrices and [A] [I....,4}
Softmax(-) is applied along the last dimension.
Remark F.4. In the above definition the no value product HFA has the same number of parameters SA (assuming same d), yet value product version has slightly more parameters depending on the orders.
Remark F.5 (Rotary Positional Embedding). One can easily incorporate rotary positional embedding into this module by applying the corresponding rotation matrices as RQ(haa) and R.K(ha,) keys and queries just as they are explained in (Su et al., 2023).
Lastly, one may concern that in practice we use layers of multi-head attention, which may possibly express Eq. 3, without exponential embedding dimension. However, we show in the following remark that even two layer multihead linear self-attention cannot express (3) (which is easily expressed by a single layer single head HypeFeeatureAAtention)) comparison, we deliberately bias the setup toward standard self-attention by pitting a two-layer, multi-head SA model against a single-layer, single-head HFA.
this
Remark F.6 (Limitations of Two-Layer Multihead Linear Self-Attention. Two-layer multihead linear self-attention cannot represent factorized cross-feature interaction functions of the form
()) or Σ b) or similar variants,
(41)
where the token embedding is defined x; concat b,).
Brief justification of Remark F.6. Consider two-layer multihead linear self-attention model. Each layer consists H attention heads, where the output of each head is computed as:
4
SA (h)
Σ
[x] ((( for m 1,..., H. H,
j=1
40

---

A Theoretical Study of (Hyper) Self-Attention through the Lens of Interactions
with C E RRd the attention matrix for head h, and w(()()) linear map. The outputs of the heads concatenated and optionally projected using weight matrix W For single-layer multihead attention, the overall output for token i is linear combination of bilinear terms of the form:
MHA;
T (())),) (w))
In two-layer model, the first layer computes:
I Σ (x) 1, I,..., H..
h; LinearCombine
and passes (hr as input to the second layer. The second layer then computes:
L 20h C(T ha) (ho), for p = 1,.... H.....H. H2.
SA." (p) = (h,
1=1
By definition, h, is a linear combination of sums of bilinear terms in x; and Xy. Therefore, h, remains of bilinear expressions across (x,, x,
The second layer operates on h, and computes terms of the form h Ch Since h, itself is bilinear, this results in expressions that are billier in x,, Xj. Xx. However, does not introduce multiplicative interactions between independent subsets features (c.g., as vs. b,, by)
Factorization is absent: The target function E; (ax az) ((2) (b;, by) requires the output to be a product of two independent terms: one depending solely on (ai, aa) and the other (b., by). Multihead attention combines bilinear terms additively, not multiplicatively, it cannot achieve this factorization.
Suppose (1)) and f(2) are chosen such that f()) .,) is orthogonal to (b, In this case, any additive combination of bilinear terms cannot approximate the product (()) ( (b,, by). regardless of how many layers or heads are used.
Even with two layers of multihead linear self-attention, the mechanism remains additive and cannot express functions requiring multiplicative factorization of independent feature interactions. This limitation highlights the inability of layer multihead self-attention to represent cross-feature factorized interactions such as ( (as, ag) (2) (b;, by) its variants.
(
G. HyperAttention
G.1. Defining HyperAttention
Generalizing the Definition 6.1 to order n,
Aijiin-JJan
Σ
Cocite-.Can Xia X
as Cam
WV E162..
Ei
HA
Σ
Aijujam-nnn Visiannin-iT.
ji Sis
where C, WV E pd and we denote (i, fi, .... I-th entry of a tensor as Tej Similar to how self-attention
implements low rank approximation for efficiency, i.e,
R w /g
C= w (W and Cap Σ
W

---

A Theoretical Study of (Hyper) Self-Attention through the Lens of Interactions
where Wº and W RdxR are chosen low rank R d, where is the maximum rank can x d matrix have, can have low rank approximation of HyperAttention
Cacilamonn-1
Σ
w W Wk2 Wh--1 no 5io $20r... S2o...Wh
Sn-1a
R Σ
WV Eita--Ln-11
W Eio We
Wn-1o W
where each WΩ, WK W E RdxR Similarly, we choose less than the maximum rank can an dimensional tensor have. Finally adding the non-linearity, the full definition becomes the following.
Definition G.1 (HyperAttention with parameter sharing), Let X TR. Txd be the input sequence of T tokens, where d is the embedding dimension. For the n-th order HyperAttention, define:
Q XW E RR'XR
K XW" ERTXR
V XW E ERTXR.
V W E RdxR
We also define permutation mask M R such that,
Mi 0o (1 1í 2 j2 2nn-1))
where 1 is the indicator function that is equal to if the condition satisfied, 0 otherwise. Then, for each token index and output dimension T,
R Σ 0=1
A Softmax (1 da-))
Misiimnan
Qio Kjn, K Kin ... K Kin-1.0
R
Vl
Vl
Vl
V2 Jn-1.0 1.0-
Juio
12.0
The HyperAttention output is computed as:
T
(X),(X)
Σ
fn-----1111 ml
which is equivalent to
T
HA,, (X)
Σ
A Virnndo-1,.
For multihead HyperAttention, compute multiple heads indexed by h E {l...., H each with independent learnable weights w Wk* WVa. and wh. The multihead HyperAttention output is given by:
MutiHeadHA (X) Concat HA (X) HA " w
where HAA (X) Txd, d, d/H, and wo E dxd is learnable projection matrix.
We also have another version which very similar to the previous definition but the parameters corresponding different keys and values not shared.
Remark G.2. To increase the implicit bias one could use Mi = -oo (1-1111) I[ > f2 > ...>>> jn- instead the mask stated the definition. In this version the block would be more specialized to learning n- n-way interactions instead of lower order interactions.
42

---

A Theoretical Study of (Hyper) Self-Attention through the Lens of Interactions
Definition G.3 (HyperAttention without parameter sharing), Let X E RRxd be the input sequence of 7 tokens, where d is the embedding dimension. For the n-th order HyperAttention, define:
Q XW R
KT XW ERIXA,
Vm E (l,..., 1}
V XW E RRXR
Vm {l..... 12 1},
V = w E RdxR
Then, for each token index and output dimension T,
R k2
A As.rennnan
Softmax ha-daal)
Mi Mishinnan
Σ
Qi K ji 12.0... Kgr
1.0
Vn Vinnronn-117
Σ
V! V2 Vn-1
V
T,0-
The rest of the definition is the same the previous definition G.I.
G.2. Representation Abilities of Hy AlypeAAttettion
Theorem G.4. A single layer of order linear HyperAttention (without parameter sharing), with embedding dimension
d = | can represent any function of the form
F; Σ
(i))..., ..., (fn-1)) Wa(h))
Jn 16(4]
for all elements in the sequence, ie,, i E [T.. The parameter-sharing variant of HyperAttention can express the same class of functions provided that (i) the weight tensor w is fully symmetric, i.e. invariant under any permutation of its indices, and (ii) the kernel is symmetric its last n arguments, X (j1) ,..., (jn-1).
Proof. Seeing that d = [S], the embeddings can be orthonormal. Consequently, the same arguments of the Proof of Theorem 3.1 in Appendix follows.
G.2.1. SKIP- TRIGRAM BUG
Let us now illustrate how higher-order dependencies may arise with a more practical example on skip-trigrant
Next-Token Prediction A common strategy for training language models next-token prediction: given a sequence of 2 tokens (X (0) X' (1) ......... X (L- 1)), the model learns to predict the next token. In our setting, the label for training
X' (L 1). For simplicity, focus the final row of the softmax self-attention output (corresponding to X' (L 1)).
Concretely, the model produces probability distribution over the vocabulary, defined as:
Esele exp(f(X (i), (i), wx()
Ejqyeex
(i))
During inference, the next token ý is then sampled from this distribution.
As shown by (Elhage et al., 2021), self-attention can learn skip-trigrams. For example, in a sentence fragment such as ....koep... in []." the model might predict the next token "mind," completing the phrase ". keep.... in mind." In the context of our work, we can interpret this phenomenon in two steps: (1) self-attention identifies that "in" is influenced by "keep" (i.e., (in, keep) is large), and (2) it leverages that influence to generate the token "mind."
However, as shown in (Elhage et al., 3021), the same mechanism that raises the probabilities of the correct skip-trigrams keep.... ...... in mind" and "... keep .. at bay" also inadvertently increases the probabilities of the erroneous skip trigrams keep....... in bay" and " .... keep ...p...ai at mind." This phenomenon, known as the "skip-trigram bug." arises from how
43

---

A Theoretical Study of (Hyper) Self-Attention through the Lens of Interactions
attention influences these completions. From our interaction perspective, increasing the probability of".. keep ... in mind" be done in two ways (1) Increasing fiin, keep), which unfortunately also boosts the probability of".. keep....................... in bay." (2) Modifying Wkeep to bias the model more strongly towards "mind," which reduces the probability of"".. keep.... at bay."
Either approach makes it challenging for the model to consistently prefer the correct completions without also amplifying incorrect ones, thereby explaining the skip-trigram bug.
Hyper-Attention for Avoiding Skip-Trigram Bugs. The crux of the skip-trigram bug is that a single self-attention head (or pairwise interaction) tries to capture the entire phrase "... keep..... ... in mind" by boosting f(in, keep) alone. This inadvertently increases the probability of other completions like " keep. in bay" whenever Wkeep also points toward "bay." However, many real-world contexts contain additional tokens that disambiguate the correct completion. For instance, the sentence "..kkepp the deadline in [ I" strongly suggests "mind" over "buy".
In our framework of hyper-attention, one can introduce a ternary interaction term
Min, keep, deadline)
that focuses specifically the triplet {"in", "keep", "deadline"), allowing the model to favor "mind" without simultancously boosting "bay." Concretely, if we let
f (x (1) (R:) and (
govern three-way effects (rather than just pairwise fin, keep)), the probability of "mind" can be increased via a higher- order interaction [in, keep, the theddead) specifically tailored that context. In doing so, we need not raise all completions of "...koep... ... in []." and thus avoid inadvertently increasing "... .....e.p...... ..ep....e in bay."
Hence, by modeling triplet or higher-order interactions, hyper-attention more flexibly captures context-specific phrases like "keep the deadline in mind," while suppressing incorrect ones like "keep the deadline in bay," mitigating the skip-trigram bug highlighted.
G.3. Efficient Strategy to Mitigate O(L") Computation Complexity
For simplicity, we focus on third order HyperAttention but the same arguments generalize to any order. Let's first look at linear version with recalling the definition of third order linear HyperAttention (Definition 6.1) in the tensor decomposition format of Definition G.I.
Aisi.z
Qi. KJ K2 j2.00 Σ o=1
Vindar
1/ 122 V3 ja.0 7.0
HA X
Σ
Aujuz Viser.
J132
Here, each equation has O(),3R) computational complexity, so the total calculation has O(I,R) complexity. We can write the same expression
HA lin (X)
Σ
Q
K
K2 2a
KE
v
V2
V3 12.0 7.
(42)
jn.0
juoo
fid2
Changing the order of summations (take the summations over js first),
R
R
L Σ
L |
lin HA!
(X) = Σ
Qia d=18=1
K2 Vl mii
n }
V2
12.0 vv3,
(43)
d1
d2
its computational complexity can is reduced to O(LP)). Generally R < L because R simply corresponds to attention head dimension. Thus, computational complexity reduces significantly.
44

---

A Theoretical Study of (Hyper) Self-Attention through the Lens of Interactions
As for the softmax general nonlinear version, use techniques similar those in (Katharopoulos al., 2020; Choromanski et al., 2022). For general nonlinear case Eq.42 can be written as,
Enis sim Qi.,, Kn. KZa:)) {E> Vi V2 V3 Σni sim (Ois K} K).." (2:)
HA li (X)
52.0 7.
where sim(.) is classical non- con-linarittees (for softmax it is exponentiation of the attention scores). This can be approximated with function of the form
Enisa (Egz (Q
{E V V2
1210 V7.0
H (X)
f2 Σj Eoe (Q()) (
where Φ IR R2 a nonlinear transformation chosen accordingly to the sim and R2 E z is ((R). (Alman Song, 2023) show that if entries of the input matrices Q, K are less than of Mog L) than for = 1/poly(L.)
max 1,7
HA! lin
lin HA,
<
Consequently, the same summation order change trick (43) applies for nonlinear HyperAttentions, too.
G.4. HyperAttention Learning
For simplicity prove the convergence of order three linear HyperAttention. However, after this proof, extension to any order is trivial. Recall Definition 6.1, which is copied here.
Definition G.5 (Third order Linear HyperAttention),
A
Σ
CaciseXo Xia XaxX,ns X1ss X36
a0122
Vistar
X X WV
E1E2T
S:E2
HA li (X) = Σ
Ashiza Vintar
ir
$1
where denote (i.j, ktt entry of a tensor T as Tiyk and C ddxadd, WV pdxaxds
Seeing that our main aim is understanding the attention scores, the core mechanism defining self-attention, choose d2 to simplify the convergence analysis. Thus, W is two dimensional tensor which we denote as w in this subsection. Assumption G.6 (Weak Realizability). The task is realizable, i.c, there exist C* and w' that perfectly fits the training data. Theorem G.7 (Convergence of HyperAttention to Zero Training Error), Let the dimensions == |S] and d2 = 1. Also, let initial parameters C(t) = 0, - (0) 2 b> 0, Vi. Then, under the assumptions G.10 and G.6, gradient flow on
B
MSE (C, W =
1
Σ n0
HA C. wr (x(m)) - r(ml
B
converges to zero training error.
Before proving the theorem we will derive the gradients and state some lemmas that are going to be useful the proof.
Gradients with Respect to Cand w.
0L MSE (C, w)
2
Σ
B
HA lin (x(mi)-
-y(n))
OHA (x(1))
6c aCpua
B
aCwea
n=
45

---

A Theoretical Study of (Hyper) Self-Attention through the Lens of Interactions
H lin (x(1))
ΣΣΣΣ
x X
(n) (m) (m) Xjy Kko ko wiy
X
85k
x/00 x ) (xix.)) T D
0L MSE (C, w)
8c
B
2
Wyy
ΣΣ
ko ju X3
(1)
70
JSk
Similarly we can find the gradient with respect to w.
MSE (C, w)
OHA lin (X (m)
Σ
HA
(x(1)) - -s((n)
Owyo
B
Owye
n=1
OHA lin (X
(XiuX XKo Cpevo XjnXe Xko
Ow-o
JSk
OT,MSE (C, w)
Ow.e
B
2
Σ E
Opve
ΣΣx
ju
(1)
x
37
(1) (1)
Xo
(X(x)T) D(m)
pva
jSk
In this subsection, we will change our perspective and prove the things in the one hot encoding basis, similarly to what we did in Section C. That is, we define
X (n) hot
x-(1)
Buk-
ik
h
Cape
Cone-hhot hot
Σ
Bys Buj Bakk
ijk
cone-bod hot
Σ
B BayBayWay.
and use the one hot encoded versions. However, again, we abuse the notation and omit the subscript in this subsection, e.g. we write C' but mean the one hot version Cone-hot in the rest of this subsection. Lastly, in this section, we denote C₂ R [i as unique one-hot encoded vector for all μ S, i.e. the base vector.
Now we state some lemmas which are anologous to Lemmas C.1 and C.2. (11)
Lemma G.8. In the embedding base, Σe Ejst
(x) x(11) x-()) is diagonal in the sense that it can be written as ju
ko jo
ΣΣ k JSK
(n)
iu jy ko
x (n)
x
(m)
x(m) -1w duy
where
r(x)
ΣΣ
vo
# 1Sk
and 8 is kronocker delta function, that is,
1, ifv=
6uy
0, i
Proof. Seeing that we are in the embedding base,
ΣΣx#'
(n)
(1)
x
(m)
(1)
(excn1(o), [exmuaee (exmer) [exmnll,
ko
k
JER
b jcc
ΣΣ 0x010
JSk
46

---

A Theoretical Study of (Hyper) Self-Attention through the Lens of Interactions
ΣΣ A JSK
8 6x0_)))000000))))))
óuzdan
the last equality follows from the identity 61y0kk = 8zj0zk.
Lemma G.9. If we choose initial parameters as C()) = 0 and was (0) 2 b> 0, then Was(t) 2 b> >0, 0, Va, 3 and Vt 2 0.
Proof. Firstly, we will show that (t)² 2 a (0)², Vt and vi, than the statement the lemma will follow similar to the proof of Lemma C.2. Using the previous gradient derivations and Lemma G.8,
dC dl -1 8Cuv
ML (C, w)
ΣΣ Who 70
ΣΣ k JSk
((x) x (()) ko x ) (xxxe)
D
-1
ju
n
=1 Σ Σ
Wio Wxo X(v) X
30 Tuodurdan
(x(il) T
D(m),
B 78
dw
-1) LL LL MSE (C, w)
2 ΣΣ
ΣΣ
(n)
fe x x
(m)
(x(xo)
D
Cuvo
di
Owig
100 n
A ISA
ΣΣ pUB
Cuvo vndurdan Co (X(m)T)
D
=
Let A and A be matrices that are diagonal in the embedding base B. However, we again abuse the notation. We do not rewrite the one - hot A a,bone-hot
BCB T and denote just as a. in the rest of the proof. We can now write
Cpeo
dCywo A A
= =
2 ΣΣ Cuvo
A
Σ 70
wooT Doy
(x
D
dt
2 =1
ΣΣ
Cuvo W A
r(x) i0
(X()TT
D
=
para
Σ 70
wyo dl
dwip
-11
2
Σ
A Abg why
Cuvol &
wo Sey
(X(1)T)
D(
70
pur
2
CHeo W Ao ((x) (X())T
D
=
Consequently we have
dw-0
dC dCpwo
Σ 70
A Ano = =I Cuvo
Ao Ab.
w
uuo
Win W Ag
Σ
C2
Aa A
dt
dt
puo vy
70
Σ
w (t))(
Σ
w²
+ Cion
Cie (0)Ag
70
70
pvo
par
Letting A diag (ca) and A diag (es),
wh (t) w² (0) - || (t)) - (0)l + (t]
where the last equality follows because C(0) 0. As result we reach to
w² 22g(() (t) 2 2 (0)
(0) > 2
(44)
47

---

A Theoretical Study of (Hyper) Self-Attention through the Lens of Interactions
Seeing that dwod is finite VL, was (I) is continuous. As result if (0) > then was (L) 2 vi which can be proven de
by contradiction. Assume ht > 0 such that wa (t*) Σ b. By Equation 44, Was((") S - 0. By intermediate value
theorem 3r E (0,t*) such that Wa (T) = 0, so w (T) = 0 < (0)
(0) 2 b2, which contradicts with (44)
Proof of Theorem G.7. Seeing that d2 = 1 we denote two dimensional reduction the three dimensional tensor W V as w. Thus the HyperAttention formula becomes,
Casisa XiaX X )
HA lin (X)
Σ
Σ
S.12
(5152
Gradient Flow for the Residuals and the Loss
dC
aL (C.w)
dw
OL MSE (C, w)
1|
dt -1
dt
aC
Following similar steps in the proof of Theorem 4.4,
dD!
M. (C, w)
Σ
x(m) (m)
ΣΣ
X (m)) x((e X
(m) (m)) (mm)
dl
= =-
wwo
8C 8CHUO HuO
R jik
OL MSE (C, w)
Σ
x(m)
x ju
(mm) x((m) Cuevo x(m)) x(m))
Iw-o
k jSk
Substituting the gradients
m))
21
Σ
xm(m Waror
ΣΣ
((m)
((m)) x-
(m)
x-(m)
dt
B
ju
kor
jrd
kor
JSK
xfo x!!!) x x ) (x(m)) T
Σ
ΣΣ
D(m)
x
wyy
70
iSk
2n
Σ
{
(x(m))
Oprero
ΣΣ
(mmm) x ((m) x(m)) x((m)
B
jer
p'v'o'g0
# isk
x ) (x(e)) D
ΣΣ Ouvo
ΣΣ
x(xa) x(m) x x(=))x /0/
JUV
jsk
By Lemma G.8,
dD("))
2
Σ
x(m) in
Wyy I Say Σ
[(m)
who T (2) uo Suyd00 (
(x(1) (()))
=- 1]
dt
B
8'
70
2
(mm) CH'vo (m))
ΣΣ
Cwva (n)
bo doydoo (X(W)) D(x)
B
n'v'a'n0
sp'
n.
2
x ((m))
(m))
Woo ((m)
Σ Wwol ((a) (x(m)
((m)
1|
B
2
Σ
X(mm)
Sworrfmi 70
Σ Guyer(u) 70
(x(m)T)
(m)
"1 B
R.:
p''0
Now let us define,
M(nn) xx(1)
((n)
Wove
luvo
Da
48

---

A Theoretical Study of (Hyper) Self-Attention through the Lens of Interactions
Also define matrixize Min as M such that first dimension of M is vectorization n and i the second dimension vectorization of μr U, M BLxd There exists similar matrix M2 such that
dD dt d MM + M
Similar to what we in the proof of Theorem 4.4, it follows that
d. MSE (C, w) 4n DMM B²
S
(45)
dt
Now, we will write Eq. 45 differently, reexpressing D. Thanks to Assumption G.6, i.e. the realizabilityy we can write
D. = Σ / x!!) X Cuvo x(1) x Way - Σ by
x(1)) x(()) x
Cavo x(xx X w.
ju
poayo
avay0
By Lemma G.8,
D Σx Xip (CrwoT vo Wvo - C
D [(n)
uuvo vo Wio
By Lemma G.9, 1/Wor defined, so we can write
D
Exutro Wyo (Cwor
Civa
Woer Wvo
Σ
(Cwo
Cuuv
Wor Woo
pva
Now again we can vectorize along n, and vectorize along μl, v, a which leads to
Mvec C (c- C
w
w
Following the same steps as in the proof of Theorem 4.4,
d.. (C, w)
4n B
DJ MM D
4n vec C C* diag ]] M MM Mvee
c M
C diag w= w
Using the Lemma C.3, the same inequality can be written as
d.E (C, w)
S
4n B2
min (M'M) ||Mvc[[ C C* diag w w
)]]
4n Ba
Amin MM) |D|]2
where Amin (M is the minimum eigenvalue of M Thus, if there exists constant & such that Amin (M (t))()))= > r 0, Vt, then the training loss stops decreasing only when D reaches to all zero vector, iee training loss stops decreasing only when it reaches to zero, which is stated more rigorously in Lemma C.4.
Lower Bound on the Eigenvalues of M. M.
Amin (MMM) = Omin (M (M M) = min
M Mu
(46)
where the first equality follow because T is symmetric and positive semi definite and u E R We also know
M M
ΣΣ
x I Weo x(x) I wor Wor..
pvo o'
SEIL]
For ease of notation we can tensorize the things back to the u,v, V. Thus,
[u|
Σ
2
49

---

A Theoretical Study of (Hyper) Self-Attention through the Lens of Interactions
follows that
M Mu] = =EE E
x ((()) iip
T(o) upw v'o Wu
(47)
REB (E[L] W'v'
Remembering
Σ
XinXin
Σ
RE|L]
iE(2
Eq. 47 becomes
M Mu]
= Σ
p(n) Wyo
E
Σ FELLI
8x(0
puo
nEB
ΣΣΣ
p(a) Wwor o'a (U
nEB LE(L)
Recalling the definition B = {n B: E ), we do the same trick we did when we were getting Eq. 26 form Eq. 25, so we get
M Mu
pur Σ
s(t) Σ
((m) Woo I worerrrr uuwo
MES nEB,
Vectorizing along v,a a and v/, o' we reach to
Mu-
Σ WES
diag (w)
Σ nEB
(1)
vec (T(w) vec (nlw)) upp-
(48)
Notice the similarity between Eq. 48 and 27. Thus, defining
ZB
vec (LVx))
nEB,
we follow the same steps seen after Eq. 27 and reach to
Amin (MM) M) 2 6²5g
where we used the bound Weo b and the Assumption G.10 -0 (Zs,)) 2 2 Assumption G.10 (Training Data Versatility). For all S,
ZB, = vecT (N())
nEB,
full column rank.
H. Comparison Between the Attention Models
We have introduced two novel models (HyperFeaturreAAtennio in Appendix F, HyperAttention in Appendix G) and mentioned some approximations to reduce computational complexity (in Appendix G.3). In this section, letting embedding dimension to be d, sequence length to be L, we compare those models terms of number parameters, computational complexity, and abilities in Table H. too.
50

---

A Theoretical Study of (Hyper) Self-Attention through the Lens of Interactions
Table 3. Comparison Between Attention Models
Computational
Model
Captures
Complexity
Self Attention
+ T.2
Mutual interactions
HyperFeaturer AlypeticatureAAteeniio
θ (L.)
Couplings of mutual interactions
HyperAttention
@ (I.)
n-way interactions
of order n
Linear Self Attention
(L)
Mutual interactions (approximate)
Linear HlppeFeature Linear HyperAttention of order n
Couplings of mutual
θ (1)
interactions (approximate)
θ (L) n-way interactions (approximate)
Starting with self-attention, it captures mutual interactions between entities." 13 If has multiple heads, it can capture summation over mutual interactions between features of the entities. has @(d²) parameters, and its computational complexity is ( In order to reduce the computational complexity ( people came up with approximations called "Linear Attention" (Katharopoulos et al., 2020; Wang et al., 2020). However, despite the name, the method is generally used to approximate softmax self-attention.
HyperFeetuureAtteniinn captures couplings of mutual interactions between features." 14 If it has multiple heads, it can capture summation over couplings of mutual interactions between features. Same as self-attention, HyperFeature (d²) parameters, and its computational complexity O(L²). The same Linear Attention approximations can be applied HyperFeatureAAtention, reducing its computational complexity to @(L). Seeing that the main goal of the paper is not this approximation for HyperFeature Atteetio,, we did not show it explicitly.
has
As for HyperAttention of order it captures up to th order interactions." 15 If it has multiple heads, it can capture summation over to th order interactions between features of the tokens. It has (df) parameters, and its computational complexity (L"). Using similar Linear Attention approximations, in Appendix G.3, we explained how to reduce computational complexity of HyperAttention to (()).
One might contend that standard self-attention can, in principle, capture these complex interactions "in surprising ways." The key difference is that our modules achieve comparable expressiveness with far fewer parameters- and therefore lower memory and compute overhead. While we do not advocate replacing conventional self-attention with AtterAttention or HlyperFeeaureeAttentioo we propose these mechanisms complementary enhancements. In a typical multi-head architecture, certain heads may employ standard self-attention while others utilize HyperTeaturreAtteniio (of varying orders) or HyperAttention to capture richer, higher-order interactions. Depending on the computational constraints, the HyperAttentions may leverage the linear approximations described in Appendix G.3.
Figures
"Refer to Theorems 3.1, 4.4. 4.6, 4.8
"Refer to Section 5 and Appendix F Refef to Section 6 Appendix
51

---

A Theoretical Study of (Hyper) Self-Attention through the Lens of Interactions
(a) Learned
(b) Devised C
0
0
50
0.6
50
0.10
0.4
100
100
0.08
0.2
150
0.06
0.04
200
-0.2
250
-0.4
250
0.00
300
300
-088
0.02
350
350
100
200
300
200
300
Figure 2. Comparison of learned vs. devised parameters for sinusoidal embedding: (a) Devised matrix C 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

---

A Theoretical Study of (Hyper) Self-Attention through the Lens of Interactions
Cuu
50
50
1.0
100
I
1.0
100
0.8
0.5
150
150
0.6
0.0
200
200
0.4
0.5
250
250
0.2
-1.0
0.0
300
300
350
350
50
100
150
200
250
300
350
50
100
150
200
250
300
350
(c) CnuV,
(d) C
50
50
0.0
0.0
100
0.2
002
150
0.4
150
-0.4
200
-0.6
200
0.6
250
0.8
250
-0.8
-1.0
1.0
300
300
350
350
0
50
100
150
200
250
300
350
0
50
100
150
200
250
300
350
Figure Equivalence of learned parameters with one-hot embedding domain embedding base (here the parameters are already in the domain embedding base so we did not transfer them): (a) Cu.r Icarned parameters in domain embedding base, (b) CVL devised parameters in domain embedding base, (c) C... Wun the interesting matrix in domain embedding base. (d) Transformed CML WX using original parameters. The mean squared difference between (c) and (d) is (100 (110-)), demonstrating functional equivalence despite different parameter organizations.
53

---

A Theoretical Study of (Hyper) Self-Attention through the Lens of Interactions
(a) Cuo
(b) Cup
0
50
50
1.0
100
100
0.8
150
150
0.6
200
200
0.4
250
0.2
0.0
300
350
350
50
150
200
350
150
200
350
(c) CuvVe
(d) V
50
50
0.0
100
0.22
100
-0.2
150
0.4
150
-0.4
200
-0.6
200
-0.6
250
0.8
250
-0.8
-1.0
1.0
300
300
350
350
0
50
100
150
200
250
300
350
0
50
100
150
200
250
300
350
Figure 4. Equivalence of learned parameters with sinusoidal embedding domain embedding base: (a) C,v. Iearned parameters in domain embedding base, (b) CVL devised parameters in domain embedding base, (c) Srr the interesting matrix in domain embedding base, (d) Transformed CPP w using original parameters. The main squared difference between (c) and (d) is O demonstrating functional equivalence despite different parameter organizations. Additionally side note, comparing (b) with Fig. 2 (b), observe the advantage of sinusoidal embeddings in terms of their parameter efficiency within the w matrix, particularly when important than absolute positions.
relative positions
54


Reviews:
[{"review_id": "de7WLHrCew", "reviewer": "Reviewer_N655", "summary": "The paper introduces a broad theoretical perspective to analyze the capabilities of self-attention mechanisms, particularly focusing on the interactions between entities. The paper extends the traditional pairwise self-attention to higher-order interactions and presents two novel mechanisms: HyperFeatureAttention and HyperAttention. These mechanisms capture feature-level and multi-entity dependencies, respectively. The authors provide a comprehensive theoretical analysis demonstrating how self-attention learns and generalizes mutual interactions, with guarantees for out-of-distribution (OOD) generalization. The paper also includes experiments validating these theoretical claims, showing that the learned parameters align with the theoretical predictions.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "LINK (please open in a private window): https://drive.google.com/file/d/1lJ3HYR6i02jpm3CAxg4cu4J6icQXubJ8/view?usp=share_link\n\n*RESPONSE 1* (On Computational Complexity of Models and Response to Question 1): In our appendix, we showed that by leveraging linear self-attention approximations, the computational complexity of HyperAttention with even softmax activation function can be reduced to $\\mathcal{O}(L)$. We suggest looking at \"RESPONSE 6\" part of our reply to reviewer xG3k, where we detailly answered this question and what kind of revisions we will do.\n\n*RESPONSE 2* (to Question2): For self attention, our main goal is to provide rigorous theories for the understanding of the existing self attention mechanism, as opposed to conducting large-scale experiments (which has already been done on many literature as we cited). Our current experiments validate the theoretical framework of linear self-attention. \n\n*RESPONSE 3* (Regarding emprical evidence for Hyper(Feature)Attention): We agree experimental verification of HFA and HA are important. As this work is primarily theoretical, we now present small-scale experiments while working on large-scale versions in a following paper. In our small-scale experiments, we evaluate next-token prediction under two setting. 1) 1-layer 1-head self-attention, HyperFeatureAttention with context window of 1024 but all of the rest of the hyperparemeters are the same as GPT-2 paper (e.g. embedding dimension is 768 etc.)2) 3 layer 3 head self-attention, HyperFeatureAttention experiments with all of the hyperparameters the same as GPT-2 (context window of 1024, embedding dimension of 768 and so on). 3) 1-layer 1-head self-attention, HyperAttention, HyperFeatureAttention with context window of 256 but all of the rest of the hyperparemeters are the same as GPT-2 paper (e.g. embedding dimension is 768 etc.)\nIn both experiments the networks we compare have the same number of parameters. Self-attention and HyperFeatureAttention networks have the same computational complexities but HyperAttention has $\\mathcal{O}(L^3)$ complexity (we did not apply the approximations reducing complexity yet). \nWe deliberately adopted certain design choices that do not favor our proposed models which implicitly favor self attention to ensure a rigorous evaluation. Although these results are preliminary, they consistently indicate that networks incorporating HyperAttention and HyperFeatureAttention achieve better perplexities and cross entropy looses compared to those based solely on standard self-attention.\nFor the comparison over the results, please refer to the *LINK*. As for large-scale experiments with comparisons to SOTA, we have deferred extensive, large-scale experimens for the new models to a forthcoming follow-up study because 1) this paper focuses on fundamental theoretical insights and 2) we have possible variations that preserve the essence of Hyper(Feature)Attention models yet may enhance empirical performance, thoroughly exploring these refinements and different possible architectures involves extensive research.\n\nIn addition, in the various colliding agent example scenarios in Appendix B.1.3 and \"Non-Identical Agents Revisited\" in Appendix E.1, with several examples, we step by step induce how HyperFeatureAttention is a natural construction from the theoretical insights on self-attention. Similarly, we explain in Section 6 how HyperAttention is natural construction from our self-attention theories. It is also worth noting that HyperFeatureAttention and HyperAttention are designed to supplement rather than replace existing self-attention mechanisms. For instance, in a multi-head architecture, some heads may employ standard self-attention, while others integrate HyperFeatureAttention (to capture cross-coupled feature interactions) some employ HyperAttention (e.g., order-3 or order-4) to capture higher order interactions -even combination of HyperFeature and Hyper Attention is possible. \n\n*RESPONSE 4* (the interpretability of parameters with sinusoidal embedding and response to question 3): We believe that the confusion was merely due to a narration problem. It was stated \"..., the learned parameters do not overlap with the parameters we originally devised, especially for the sinusoidal embedding, seen in Figure 2 -these learned parameters lack easy interpretation ... as discussed in Corollary D.5, this outcome is a natural consequence of the generalization theories ... Therefore we focus on\" transformed versions of the parameters ... Further our generalization theories are on those transformed versions. \"As shown in figures 3 and 4, these matrices are indistinguishable from the theoretical counterparts. With only ${\\Theta}(10^{-4})$ mean square distance between their entries. Thus, in this simple setting, we can fully interpret the meaning of the parameters\". We will fix narration.\n\n*RESPONSE 5*: For references look at RESPONSE 1 to reviewer Ct39.", "claims_and_evidence": "This paper has given a clear representation and proof.", "methods_and_evaluation_criteria": "The introduction of HyperFeatureAttention and HyperAttention extends the self-attention mechanism by capturing higher-order interactions, a potentially useful contribution for complex multi-agent systems and tasks involving feature dependencies. And it demonstrates that the proposed linear self-attention framework converges to optimal solutions under mild assumptions and generalizes well across varying sequence lengths and tasks.", "theoretical_claims": "The paper provides a clear and unified framework to interpret self-attention mechanisms through the lens of mutual interactions across various domains. It offers new insights into how self-attention works and generalizes, specifically with respect to out-of-distribution shifts and interaction learning", "experimental_designs_or_analyses": "Although the theoretical claims are supported by experiments, the experiments mainly focus on simple toy problems (e.g., colliding agents). More real-world and complex experimental setups are necessary to fully assess the robustness and scalability of the proposed methods in practical settings.", "relation_to_broader_scientific_literature": "This paper has made a broad literature.", "essential_references_not_discussed": "Regarding high-order interaction among multi-agent reinforcement learning, an important work should be considered in the introduction or related works section: NA2Q: Neural Attention Additive Model for Interpretable Multi-Agent Q-Learning, ICML, 2023.", "other_strengths_and_weaknesses": "While the introduction of HyperFeatureAttention and HyperAttention is conceptually valuable, the increase in complexity might hinder the practical applicability of these extensions for large-scale problems. The computational cost and potential trade-offs between expressiveness and efficiency are not fully addressed.", "other_comments_or_suggestions": "The paper emphasizes the interpretability of the learned parameters, but in some cases, the learned parameters (especially with sinusoidal embeddings) lack clear, intuitive interpretations. Further exploration on how to make these parameters more interpretable in complex settings would strengthen the practical relevance of the work.", "questions_for_authors": "1. The HyperAttention mechanism captures higher-order dependencies, but its computational cost scales cubically. How do you plan to optimize this mechanism for large-scale applications? Are there approximations or heuristics you are considering to make it more efficient in real-world settings?\n2. While the experiments validate your theoretical findings on simple tasks like colliding agents, how does your framework perform on more complex and realistic datasets (e.g., NLP tasks, computer vision, multi-agent reinforcement learning)? Can you extend the experiments to such tasks to further validate the scalability and generalization of your methods?\n3. While you discuss the interpretability of learned parameters, some experiments (especially those with sinusoidal embeddings) reveal that the learned parameters do not always align with intuitive expectations. Could you provide further insights on how you plan to improve interpretability in more complex settings or for larger models?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "8NQhnKDi03", "reviewer": "Reviewer_xG3k", "summary": "This paper is separated into two broad sections. The first is a theoretical study of linear self-attention, which explores the expressivity and generalisability of a single linear self-attention layer. The second is more empirical, proposing two new architectures based on self-attention. The performance of these models are demonstrated experimentally.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "LINK (OPEN IN PRIVATE WINDOW): https://drive.google.com/file/d/1lJ3HYR6i02jpm3CAxg4cu4J6icQXubJ8/view?usp=share_link\n\n*RESPONSE 1* (the results of one-hot embedding): The results were explained as \"negligible error $\\Theta(10^{-7})$ on test and out of distribution data\". However, we agree and for complenetess we will add the learned parameters to the paper (see LINK). \n\n*RESPONSE 2* (additional experiments for theory validation): We experimented the theories on the genotype phenotype mapping task (explained Sec. 3 Example 2 and Appendix B.2) and got same results $\\Theta(10^{-7})$ error on test and OOD data.We may add them to paper.\n\n*RESPONSE 3* (the figures in the appendix \"which are neither discussed nor referenced in the main text\"): discussed in Sec.7 as \"shown in Figures 3 and 4, these matrices are indistinguishable from the theoretical counterparts\"\n\n*RESPONSE 5*: Sanford et al. shares our $\\mathcal{O}(L^3)$ complexity. The footnote 5 is unnecessary and will be removed.\n\n*RESPONSE 6* (Comparison Between Attention Models): We will add the following discussion and the attached table (LINK) to the paper. Letting embedding dim to be $d$, sequence length to be $L$, we compare those models in terms of number of parameters, computational complexity, and abilities. \n\n- For self-attention, it captures mutual interactions between entities (cf.Thms 3.1,4.4,4.6,4.8).If it has multiple heads, it can capture summation over mutual interactions between features of the entities. It has ${\\Theta}(d^2)$ parameters, and its computational complexity is ${\\Theta}(L^2)$. In order to reduce the computational complexity to ${\\Theta}(L)$, people came up with approximations called \"Linear Attention\"\n(Katharopolus et al 2020, Wang et al 2020). However, despite the name \"linear\", the method is used to approximate nonlinear selfattention. \n\n- HyperFeatureAttention captures couplings of mutual interactions between features (cf. Sec.5, AppendixE). If it has multiple heads, it can capture summation over couplings of mutual interactions between features. Same as self-attention, HyperFeatureAttention has ${\\Theta}(d^2)$ parameters, and its computational complexity is ${\\Theta}(L^2)$. The same Linear Attention approximations can be applied to HyperFeatureAttention, reducing its computational complexity to ${\\Theta}(L)$. Seeing that the main goal of the paper is not this approximation for HyperFeatureAttention, we did not show it explicitly. \n\n- As for HyperAttention of order $n$, it captures up to $n^{th}$ order interactions (Refer to Sec.~6 and Appendix~F). If it has multiple heads, it can capture summation over up to $n^{th}$ order interactions between features of the tokens. It has ${\\Theta}(d^2)$ parameters, and its computational complexity is ${\\Theta}(L^n)$. Using similar Linear Attention approximations, in Appendix~F.3, we explained how to reduce computational complexity of HyperAttention to ${\\Theta}(L)$. We will add the requirements on the query and key matrices that if their entries are less than $o(\\sqrt[3]{\\log L})$ then the infinite norm between the actual outputs and approximate outputs is less than $1/\\mathrm{poly}(L)$.\n\n- While we do not advocate replacing conventional self-attention with HyperAttention or HyperFeatureAttention, we propose these mechanisms as complementary enhancements. In a typical multi-head architecture, certain heads may employ standard self-attention while others utilize HyperFeatureAttention (of varying orders) or HyperAttention to capture richer, higher-order interactions. Depending on the computational constraints, the HyperAttentions may leverage the linear approximations described in Appendix~F.3. \n\n*RESPONSE 7* (\"the violations that make expected guarantees not generally true in the real world\" and  \"why dont we have zero test errors and what happens when $d<N$\"): When we only have $d<N$ assumption, we start to get nonzero errors i.e. approximations to the exact solutions to the task (which is the practical real world). This is explained in both at the end of Sec. 3 \"*Why d=N?*\" part and in Thm B.4. Another key assumption in our analysis is the (weak, strong, universal) realizability. Although these conditions may not hold in practical scenarios, implying that a single layer, single-head self-attention mechanism may not fully capture the complexities of real-world tasks, it is important to note that SOTA models typically employ multiple layers of self-attention blocks. Such architectures can approximate the desired functions even when the strict realizability assumptions are violated.Actually, the realizability and d=N assumptions are very similar in essence because when letting d large enough, we simply showed in Appendix B that realizability is satisfied (with several example scenarios such as colliding agents, genotype phenotype mapping, vision task, time series prediction). A thorough investigation of these approximations, lies beyond the scope of this work.", "claims_and_evidence": "Following on with the two broad sections of the paper:\n\nThe theoretical portion of the work appears very rigorous, with claims well justified and all assumptiosn laid out clearly and justified. While I was unable to robustly verify every proof, due to expertise in this area, I believe what I have checked holds up.\n\nI think the experimental section leaves slightly more to be desired. The theory is tested for one indicative problem setting, with two different types of embedding. I may be missing something, but while there is discussion of performance for the 'One-Hot Embedding' problem, I am unable to find these results in the paper. Figure 1 applies to Sinusoidal Embeddings, but showing the theoretical results to allow us to compare would be useful. I think demonstrating these findings on more than one problem setting would also be good, although I appreciate that I lean more on the empirical side and this is a strongly theoretical paper.\n\nOne claim I did not see justified was in footnote 5: that the approach in this paper has greater representational capacity *while maintaining comparable efficiency* - it is later mentioned that HyperAttention in this paper is $\\mathcal{O}(L^3)$, and so it would be good to demonstrate that this does not lead to drastic computational increases compared to the low-rank approximation of prior work.\n\nOn a slightly separate note, a lot of the appendix is filled with figures which are neither discussed nor referenced in the main text. If these plots provide evidence or information, it would be good to at lesat have an in-text reference for them in the main body of the paper.", "methods_and_evaluation_criteria": "I have sort of discussed this above. I think additional experimentation, using more than one problem setting would be good, but I think it is worth bearing in mind that the key contribution of this paper reads more theoretical than empirical and thus the bar for experimental results should, rightly, be lower.\n\nThe motivation of the theory is good, and all simplifying decisions and assumptions are well justified. \n\nI personally found the introduction of the methods somewhat hard to follow - for a less theoretically-minded person like myself, a short statement explaining, in words, what the HFA and HA layers actually do and how they differ from SA would be helpful.", "theoretical_claims": "I attempted to verify a number of the proofs, though was unable to check every single one due to the sheer length of the paper and time constraints (@AC, see comment). What I checked seemed to be correct.", "experimental_designs_or_analyses": "I think additional experimental settings could be good as a means to improve the paper, but as stated I do not think there is a desparate need for that as a principally theoretically-minded paper. The experiment that they do include would benefit from some additional discussion in the main body of the paper, rather than purely relegating that to the appendix, and I am unable to find the results for one-hot embeddings.", "relation_to_broader_scientific_literature": "The paper seems well researched and placed in scientify literature, although I am not well placed to contextualise this work.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "I found most of the paper well written and clear, and feel it is clearly of a high quality. That said, I found a few points that I wanted to raise.\n\n- I found the examples used (particularly the contextualising example about alleles) a little bit counterintuitive/out of nowhere. Finding a way to ground an example in language would be good, given it is the field which has arguably seen the largest breakthroughs as a result of self-attention.\n- It would be nice in the main paper to highlight with a bit more discussion the effect of not having $d=N$, as this introduces some level of compression and thus may violate some of the approximations despite being a more practical system.\n- I found line 248 ('In short, ...') confusing English.\n- I found the HyperFeatureAttention notation a bit confusing - what are the curly brackets for, are they just used as normal parentheses?\n- The frequent tense changes in the paragraph starting 'Setup: Colliding Agents on a Cylindrical Grid.' made the text quite hard to follow.", "other_comments_or_suggestions": "See above.", "questions_for_authors": "- Can you please explain how you can verify that HyperAttention is comparably efficient to prior work in this area, which uses low rank approximations?\n- Given this theory, what are the violations that make the expected guarantees not generally true in the real world - as in, why do many systems in practice **not** have zero error and perfect generalisation to new data and completely different lengths? \n- Can you please explain what the use of HyperFeatureAttention and HyperAttention are over self attention, given the guarantees already present for self-attention?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "T5CT95wBth", "reviewer": "Reviewer_Qpd5", "summary": "The paper studies the self-attention mechanism that is central to many of today's ML models (such as in NLP, computer vision and multi-agent systems). Instead of Transformers (which involve several layers of multi-head attention and other components), the paper examines a simplified model that consists of a unique linear self-attention head (linear = no softmax). Most application examples are toy multi-agent systems. The paper describes some mathematical properties of this simplified self-attention model and verifies them empirically; additionally it proposes two generalisations of self-attention, called HyperFeatureAttention and HyperAttention.\n\nThe mathematical properties are that, given some assumptions (claimed to be mild in practice):\n* Self-attention can represent any pairwise interaction of tokens (theorem 3.1),\n* and does so more efficiently than any fully-connected neural network (theorem 3.2);\n* gradient descent converges to zero training error (theorem 4.4),\n* which also means perfect fit on a test set from the same distribution (theorem 4.8),\n* and perfect fit on sequences that are longer or shorter than in the training set (theorem 4.10).\n\nThe two proposed extensions of self-attention are supposed to generalise the pairwise interaction property:\n* HyperFeatureAttention can represent interactions between several features of the same two tokens. The authors claim that even two layers of multi-head self-attention cannot do this.\n* HyperAttention can represent interactions between more than two tokens at a time.\n\n## update after rebuttal", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "*RESPONSE 1* (the concerns on practicality of proposed models and what is their use while self-attention works in NLP): We agree that traditional self-attention architectures can also represent these complex interactions \"in surprising ways\". However, the main distinction is that the proposed models can represent those with fewer parameters. For instance, it is discussed  in Appendix E.1 and Appendix E.2's \"a short note on approximate embedding\" paragraph. We agree that we need to carry some of those discussions to the main text and make it clear in the main text, which will be done in the revised version. Another point is we do not advocate replacing conventional self-attention with the proposed models. For more details we strongly suggest referring to \"RESPONSE 6\" part of our reply to reviewer xG3k.\n\n*RESPONSE 2* (insightful experiments): As for the small-scale experiments, we have promising preliminary results, please refer to \"RESPONSE 3\" part of our reply to reviewer N655. \n\n*RESPONSE 3* (the concerns on proof of Thm B.4): We agree with your concerns and we think that old version was not clear. Therefore, we completely changed the theorem statement and the proof, keeping the essence the same as old version. In the new version, we use low rank approximations to the matrices that would solve the task with zero error if embedding dimension were large enough. We bound the infinity norm between the output of the linear self attention having $d<N$ and the correct labels. The bound is in terms of singular values of the matrices that would solve the task with zero error if embedding dimension were large enough. Unfortunately, it is not allowed to provide whole theorem and proof with anonymous links.\n\n*RESPONSE 4* (\"earlier works often do not delve into interpreting the roles of the learned parameters beyond attention patterns\") While making that statement we were mostly thinking about the papers not only theoretical but also \\emph{mathematical}, with rigorous theories expectations and validations of those experiments. We apologize for the confusion and in final version we will clarify. In more detail, our approach is different from conventional mechanistic interpretability approach that our approach is rigorous/mathematical and our experiments are for validating our predictions. Their approach  is like \"phenomenology\", and our approach is \"fundamental\". \n\n*RESPONSE 5* (About the scepticism on assumption 4.2): In the revised version of the paper we will add a section to the appendix that justifies Assumption 4.2. In short, assuming $\\mathbf{s}^{(n)} \\in \\mathbb{R}^{|\\mathcal{S}|}$ are sampled from a distrubution such that covariance of $\\mathbf{s}^{(n)}$ is positive definite, we will use matrix Bernstein inequality and Weyl's inequality and prove that the statement in the Assumption 4.2 hold with high probability: for some $\\gamma >0$, B is the number of data samples, $\\mathbb{P}\\left(\\mathrm{rank}(\\mathbf{S}_{{B}\\mu}) \\le |\\mathcal{S}|\\right)\\le e^{-\\gamma B}$\n\n*RESPONSE 6* (real LLM's not falling to skip trigram bug): We agree that LLMs as a whole do not have such bugs. As you mentioned, the skip connections from earlier layers help to approximately get rid of those problems and by adding more layers, the approximations gets better. In our analysis, we focus on self-attention itself (not a large neural network) and compared it with our new modules (small modules not large networks). We strongly suggest looking at the RESPONSE 6 part of our reply to reviewer xG3k (especially the last paragraph of it), which we will add to the paper.\n\n*RESPONSE 7* (On the question about the usefulness of HyperFeatureAttention (HFA)): Both HFA and self-attention have same complexity, so we compared them by parameter count,since even MLPs can represent any function with enough parameters. Our intentially unfair comparison used two-layer multihead self-attention against a single-layer single-head HFA. A fairer comparison (single-layer single-head vs. single-layer single-head) shows HFA captures self-attention. We acknowledge that some interactions require two-layer multihead self-attention, but for more on HFA’s utility, please see “RESPONSE 3” in our reply to reviewer N655.\n\n*RESPONSE 8*(connection between theoretical results and the proposed modifications): Various colliding agent example scenarios in Appendix B.1.3 and \"Non-Identical Agents Revisited\" in Appendix E.1, we introduce how HFA is a natural construction from the theoretical insights on self-attention. Though seemingly unrelated, they were stepping stones. Thank you; we’ll clarify. \n\n*RESPONSE 9*: For essential references please refer to \"RESPONSE 1\" to reviewer Ct39.", "claims_and_evidence": "The theoretical claims are well supported, both by mathematical proofs and by experiments. An exception is the claim that everything generalises to $d<N$ (see below about theorem B.4).\n\nThe proposed extensions of self-attention are justified theoretically, but not put into practice. However, it is conceivable that more traditional self-attention architectures can also represent these complex interactions, perhaps in surprising ways. (After all, LLMs use standard self-attention and are very good at modeling language!) An insightful further experiment would be to train and compare toy models with and without Hyper(Feature)Attention.", "methods_and_evaluation_criteria": "The mathematical claims are proven and tested empirically, which is good. For the proposed extensions, see the previous point.", "theoretical_claims": "I checked the following proofs:\n\n* proof of 3.1: no issue\n* proof of 3.2: correct\n* proof of B.4: The \"for every $\\varepsilon$\" claim is not proven and in fact seems to be wrong. In the proof the $\\varepsilon$ is introduced by $\\|B_* -F\\| \\leq \\varepsilon$. But given $F$ and $d$, $B_*$ minimises $\\|B_*-F\\|$ over all rank-$d$ matrices, so $\\|B_*-F\\|$ is fixed! So the statement $\\|B_* -F\\| \\leq \\varepsilon$ breaks down for any $\\varepsilon$ smaller than the fixed $\\|B_* -F\\|$.\n\n    The theorem in its present formulation should therefore be removed from the paper. To save the claim that the $d<N$ case is reasonably similar to $d=N$, the authors should reflect carefully on what the Eckart-Young theorem and/or the Johnson-Lindenstrauss lemma actually imply for the question at hand. It may be possible to replace an \"always\" statement with a \"with high probability\" statement.\n\n* proof of 4.4: in the equations on line 1278 I think $1/B$ should be $2/B$, but this does not affect the validity of the proof (as ultimately it is about when these things are zero).\n\n    I did not check the rest of the proof in detail.", "experimental_designs_or_analyses": "Looks good to me, but I did not thoroughly check them.", "relation_to_broader_scientific_literature": "The most relevant literature tries to gain a deeper mathematical understanding of Transformers. For example, the paper cites a work that shows Transformers to be Turing-complete. As a part of understanding Transformers, many works also try to understand their training process, i.e., how the training loss converges. Both threads are continued in the theoretical contributions of this paper.", "essential_references_not_discussed": "The paper cites Elhage et al. 2021, which shows that the authors are at least partly aware of the \"mechanistic interpretability\" literature. While it is only tangentially related to this paper, it could be valuable to consult and cite it more.\n\nIn particular, the claim that earlier works\n\"often do not delve into interpreting the roles of the learned parameters beyond attention\npatterns\"\n(l. 73-75 col. 2)\nseems a bold statement given papers like https://arxiv.org/abs/2412.11965 or even the Elhage paper itself. (These papers describe the idea of expanding the parameters of attention heads in language models to represent token interactions.)\nAnother point about the same sentence: to my knowledge attention patterns are not the state of the art in interpreting the behaviour of attention heads  (https://icml.cc/virtual/2024/poster/32735)\n\nMore generally, surveys on mechanistic interpretability of language models could be valuable resources: https://aclanthology.org/2020.tacl-1.54, https://arxiv.org/pdf/2405.00208, https://arxiv.org/pdf/2501.16496.\n\nThe submission attempts not only to theoretically understand attention, but also to generalise or modify the mechanism.\nPrevious studies have also attempted this, but none of them is cited here.\nTheir motivations are various and not directly related to the present ones, but I think it would still make sense to briefly mention them.\nI am aware of the following (there are probably many more):\nhttps://arxiv.org/pdf/2006.03654, https://arxiv.org/abs/2410.05258, https://arxiv.org/pdf/2410.02703.", "other_strengths_and_weaknesses": "The theoretical results are really nice!\n\nHowever, I doubt that the assumptions are as mild as the authors claim.\nI am particularly skeptical of assumption 4.2:\nIn the case of language, some tokens are very rare, and (depending on their joint distribution) it is quite possible that two of these rare tokens never co-occur. As I understand the definitions, this would lead to a column (?) of zeros, contradicting full rank.\n\nThe proposed generalisations of self-attention are also valuable ideas.\n\nBut, in my opinion, this does not mean that standard self-attention is as weak as the authors claim.\nFor example, in my understanding, the \"skip-trigram \"bugs\"\" (Elhage et al. 2021, quotation marks original) are essentially a theoretical construction that does not seem to occur in real language models. Real language models clearly \"know\" that \"keep ... in mind\" and \"keep ... at bay\" are correct but \"keep ... in bay\" is not. \nI assume this is because the attention output of \"keep\" is not the whole output: the attention head usually also attends to other tokens to some extent, such as the current token \"in\"; and there is a skip connection that enables direct usage of the embedding of \"in\" (which may encode bigram statistics, compare Elhage et al.'s section on zero-layer transformers).\n\nThis questions to what extent HyperAttention is really more useful than more standard mechanisms.\nBut again, whatever may be the case, it is definitely a valuable idea!\n\nFinally, I feel that the connection between the theoretical results and the proposed architectural modifications is a bit loose. Both parts would be valuable on their own. If they are to appear in the same paper, the authors should better emphasise how they are connected.", "other_comments_or_suggestions": "Typos, grammar and clarity:\n* Footnote 1: what is k and L?\n* l. 176: \"self-self attention\"\n* l. 228: \"let Let,\"\n* l. 241: \"Let ... as\" -> \"Let ... be\"\n* l. 242: comma -> full stop\n* l. 268: \"converges\" -> \"converges to\"\n* section 4.1: please state the assumptions before the theorem\n* l. 248 (col. 2): \"than\" -> \"then\"\n* l. 322: \"showed\" -> \"show\"\n* eq. (3): what is A? I could only guess it when I read appendix E.\n* l. 309 (col. 2): \"Remark completeness\" -> \"remark for completeness\"\n* l. 370 (col. 2): \"a circle of radius R executes\" -> \"a circle of radius R that executes\"\n* l. 1623: I guess the second H should be an A.", "questions_for_authors": "You have given an example of an interaction that standard two-layer multi-head attention apparently cannot represent, but HyperFeatureAttention can. Conversely, are there interactions that HyperFeatureAttention cannot represent but standard (two-layer multi-head) attention can? This is quite important if we want to know how useful HyperFeatureAttention really is. And whatever the answer, you should talk about it in the paper.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "No concerns."}}, {"review_id": "sUxBxFAxSx", "reviewer": "Reviewer_DnSa", "summary": "This paper proposes a theoretical framework viewing self-attention tokens as interacting entities. The key theoretical findings include proving the representational power of single-layer linear self-attention for pairwise interactions, demonstrating convergence of training under mild assumptions, and establishing generalization guarantees to both within-distribution and out-of-distribution settings. Additionally,  the authors introduce two innovative extensions: HyperFeatureAttention, designed to capture couplings between different feature-level interactions, and HyperAttention, which models higher-order (multi-entity) dependencies.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "LINK (please open in a private window): https://drive.google.com/file/d/1lJ3HYR6i02jpm3CAxg4cu4J6icQXubJ8/view?usp=share_link\n\n*RESPONSE 1* (On the experiments for \"further validation in more complex, real-world scenarios\", \"more complex or empirical\nscenarios\", \"well-established benchmark datasets\"): For self-attention, our main goal is to provide rigorous theories for the understanding of the existing self attention mechanism. Consequently, our current experiments primarily validate the theoretical framework of linear self-attention, offering strong empirical support as opposed to conducting large-scale experiments on self-attention (which has already done on many literature as we cited). That being said, we have done large-scale experiments such as famous many body problem where we predict trajectories of bodies (please refer to LINK)\n\n*RESPONSE 2* (\"clarity regarding symbolic definitions and intuitive explanations of mathematical formulations could be further improved\" and \"presentation of theorems and formulations ... with clearer definitions and intuitive explanations\"): We made the symbolic definitions more distinguishable (for instance we will replace $s^{(n)}(i)$ \"index to corresponding element mapping\" function with $\\mathcal{X}^{(n)}(i)$ since the former version may be confused with $\\mathbf{s}^{(n)}$ \"count vector\") and we further improve the mathematical formulations. Further, in the final version of the paper we will provide clearer definitions and intuitive explanations\n\n\n*RESPONSE 3* (on the references on \"Transformer interpretability\"): Please refer to RESPONSE 1 of our reply to reviewer Ct39.\n\n*RESPONSE 4* (on the concerns and questions on complexity and practicality of Hyper(Feature)Attention): please refer to the \"RESPONSE 6 (Comparison Between Attention Models)\" part of our part of our reply to Reviewer xG3k.\n\n*RESPONSE 5* (Regarding empirical evidence for Hyper(Feature) Attention): Please refer to *RESPONSE 3* in our reply to reviewer N655.\n\n*RESPONSE 6* (to Question 2): When we only remove the $d<N$ assumption, we start to get nonzero errors i.e. approximations to the exact solutions to the task (which is the practical real world situation). This is explained in both at the end of Section 3 \"*Why d=N?*\" part and in Theorem B.4. Shortly, \"... Our goal is to understand how self attention captures mutual interactions, and d = N ensures orthogonal domain embeddings, yielding an exact and transparent representation. Compressing to $d < N$ is perpendicular to this focus and can be addressed separately using standard techniques... Starting with $d = N$ allows us to establish theorems that elucidate how self-attention captures pairwise interactions, while reducing to $d < N$ merely introduces a small approximation gap without altering the core theory. For completeness, we provide.. (Theorem~B.4)\". That is being said, we runned experiments to quantify this sensitivity on the same colliding agents environment with $d<N$. As a result, we had nonzero errors (train, test, out of distribution). As the embedding dimension approached to the dictionary size the errors approached to zero. Although it is an important insight, that discussion is orthogonal to the theories for this paper,so we left those results for a future work. However, we may add them to the final version of the paper.\n\n*RESPONSE 7*: Lastly, we are thankful for pointing out the typos, formatting issues and symbol explanation issues. Considering the length of the paper, unfortunately we made those small errors which are easy to fix and will be totally fixed in the final version of the paper.", "claims_and_evidence": "The authors support their claims with rigorous theoretical proofs and empirical validation using a simplified “colliding agents” scenario. However, as the experimental results are confined to synthetic environments, further validation in more complex, real-world scenarios is necessary to fully support the claims.", "methods_and_evaluation_criteria": "The theoretical methods employed are appropriate and contribute notably towards improving interpretability and potential performance of self-attention mechanisms. However, the evaluation primarily uses synthetic environments, and extending experiments to more complex real-world scenarios or well-established benchmark datasets could strengthen empirical claims.", "theoretical_claims": "I reviewed the proofs in the Appendices, which are the key contributions of this theoretical paper.  The proofs  are basic sound. However, clarity regarding symbolic definitions and intuitive explanations of mathematical formulations could be further improved.", "experimental_designs_or_analyses": "The experimental design is sound but might not be adequate. Additional experiments in more complex or empirical scenarios are lacking, which could further enhance confidence in the generalizability of the findings.", "relation_to_broader_scientific_literature": "This paper addresses gaps such as the interpretability of the attention mechanism and out-of-distribution generalization.", "essential_references_not_discussed": "The paper cites many relevant studies, but might lack a detailed discussion of recent advances in Transformer interpretability. A more detailed comparison with current studies on Transformer interpretability would better highlight the contributions and novelties of this paper.", "other_strengths_and_weaknesses": "**Strengths**:\n- The authors introduce a novel perspective for understanding the self-attention mechanism.\n- The generalization of attention mechanisms to novel HyperAttention modules is innovative and well-motivated.\n- The authors provide clear examples to demonstrate the ability of self-attention to capture mutual interactions.\n\n**Weaknesses**:\n- Complexity: While HyperAttention may capture higher-order interactions, this comes at the cost of increased computational complexity. The necessity of such complexity is questionable, especially given some research suggesting that higher-order interactions can be approximated using weighted pairwise interactions.\n- Limited empirical validation: The paper primarily focuses on theoretical contributions, with experimental results limited to controlled synthetic environments. The authors do not provide empirical evidence demonstrating HyperAttention’s superiority in practical tasks. More diverse empirical demonstrations would enhance the credibility of the findings.\n- Presentation: The presentation of theorems and formulations could be enhanced with clearer definitions and intuitive explanations.", "other_comments_or_suggestions": "- Lack of clear symbol explanations: For example, Eq. (3) and $f_a^h$ (Line 279 right column).  \n\n- Formatting issues: Line 228 contains \"let Let\"; Line 232-233 uses wrong punctuation.\n\nOverall, while this is an interesting and meaningful study, it feels more like an intermediate-stage work. The authors provide rigorous mathematical foundations, but the lack of empirical validation beyond toy examples limits its impact. Improved readability, more detailed and intuitive theoretical explanations, and broader experimental validation would elevate the paper’s contribution.", "questions_for_authors": "- Q1: How does the complexity of the HyperAttention scale when capturing very high-order interactions (e.g., four-way or higher)? Would this limit practical applicability? Can HyperFeatureAttention and HyperAttention mechanisms practically scale to large datasets?\n\n- Q2: How sensitive are your theoretical guarantees to changes in embedding dimension (specifically when d < N)? Could empirical experiments be performed to quantify this sensitivity?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "avIArovS0v", "reviewer": "Reviewer_Ct39", "summary": "The paper presents a theoretical study of self-attention mechanisms, specifically focusing on their representation, training, and generalization capabilities through the lens of mutual interaction among entities. The authors introduce a novel perspective called \"interacting entities,\" demonstrating that a single layer of linear self-attention can effectively represent, learn, and generalize functions that capture pairwise interactions, even in out-of-distribution scenarios. They also propose two extensions: HyperFeatureAttention, which captures interactions between features, and HyperAttention, which models higher-order interactions among multiple entities.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "*RESPONSE 1* (About the references): \nIn the introduction we referenced several works on \"theoretically understanding attention\" but we agree that attention modifications could be discussed more. In the final version of the paper we will mention these approaches, i.e, the papers such as (DEBERTA) https://arxiv.org/pdf/2006.03654; (Improving sampling by modifying the effective diffusion) https://arxiv.org/abs/2410.05258;  (Selective Attention) https://arxiv.org/pdf/2410.02703. \n\nIn addition, we will expand the discussion with the \"mechanistic interpretability\" literature such as (Tranformer Circuits) https://transformer-circuits.pub and previous studies attempted to understand and modify attention and modify attention. \n\nAlso, We will briefly mention NA2Q (ICML, 2023) and other relevant methods in the revised version of our paper.\n\n*RESPONSE 2* (Use of HyperFeatureAttention and HyperAttention in MARL Settings):Our work views tokens as interacting entities—a perspective that naturally encompasses agents in multi-agent reinforcement learning (MARL). In MARL, interactions are often more complex than simple pairwise relationships, and our proposed extensions are well suited to address such challenges. In particular, HyperAttention is designed to capture higher-order (e.g., three-way or n-way) interactions, which are common in collaborative or competitive multi-agent environments where an agent’s outcome may depend on the joint behavior of multiple agents. Similarly, HyperFeatureAttention enables the coupling of different feature-level interactions (such as spatial positions, velocities, or task-specific attributes), providing a more expressive representation of agent dynamics. Although our current experiments primarily focus on controlled settings, the theoretical framework and empirical evidence presented in Sections 5 and 6 of our paper indicate that these modules can be naturally extended to MARL scenarios. In future work, we plan to investigate and validate these extensions in MARL benchmarks, which we believe will further demonstrate the versatility and potential impact of our approach in such applications.\n\n*RESPONSE 3* (Potential Drawbacks or Challenges for Larger Datasets and More Complex Tasks): We strongly suggest you to refer RESPONSE 6 of our reply to reviewer xG3k where we summarize the potential drawbacks in terms of complexity of models and how to overcome them.", "claims_and_evidence": "The claims made in the paper are supported by a combination of theoretical proofs and empirical experiments. The authors provide evidence showing that self-attention can generalize well across different distributions and sequence lengths.", "methods_and_evaluation_criteria": "The proposed methods, including HyperFeatureAttention and HyperAttention, are well-grounded in theoretical constructs and are evaluated against established benchmarks. The evaluation criteria make sense for the tasks at hand, focusing on representation and generalization across different scenarios.", "theoretical_claims": "I did not check the proofs.", "experimental_designs_or_analyses": "The experimental designs are sound and validate the theoretical findings.", "relation_to_broader_scientific_literature": "The key contributions of the paper build on existing theories of self-attention and representation learning. The authors relate their findings to prior works on Transformers and attention mechanisms, positioning their contributions within the broader context of machine learning literature.", "essential_references_not_discussed": "I think there are many attention variants in recent years, but this paper does not mention much.", "other_strengths_and_weaknesses": "The paper exhibits strengths in originality and clarity, providing a fresh perspective on self-attention mechanisms while effectively communicating complex ideas. However, some sections could be more concise, and additional examples could enhance the understanding of the proposed extensions.", "other_comments_or_suggestions": "NA.", "questions_for_authors": "1.\tHow could the proposed HyperFeatureAttention and HyperAttention be used in MARL settings?\n2.\tAre there any potential drawbacks or challenges when applying your methods to larger datasets or more complex tasks?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper introduces HyperFeatureAttention and HyperAttention which are used to factor in higher-order information into the network layers. AC finds this to be a useful contribution that can be important in certain applications. The delivery of the paper is also clear and makes the contributions apparent. Reviewers unanimously accept the paper. AC complies. The authors did not respond to one of the reviewers' comment. I strongly suggest to address this as well as including all the other feedback in the main paper.
Decision: Accept (poster)