Abstract: In this paper, we show that structures similar to self-attention are natural to learn many sequence-to-sequence problems from the perspective of symmetry. Inspired by language processing applications, we study the orthogonal equivariance of seq2seq functions with knowledge, which are functions taking two inputs—an input sequence and a "knowledge" set—and outputting another sequence. The knowledge consists of a set of vectors in the same embedding space as the input sequence, containing the information of the language used to process the input sequence. We show that orthogonal equivariance in the embedding space is natural for seq2seq functions with knowledge, and under such equivariance, the function must take the form close to the self-attention. This shows that network structures similar to self-attention are the right structures to represent the target function of many seq2seq problems. The representation can be further refined if a "finite information principle" is considered, or a permutation equivariance holds for the elements of the input sequence.
Introduction
Despite the unprecedented success of Transformers in fields ranging from natural language processing to protein folding, the architecture's core—the dot-product self-attention mechanism—was largely developed through heuristic intuition. Unlike Convolutional Neural Networks (CNNs), which are mathematically grounded in the principle of translation invariance (the idea that a feature's meaning remains constant regardless of its position in an image), the Transformer has lacked a rigorous theoretical justification for its specific functional form.
In this work, Chao Ma and Lexing Ying provide a mathematical foundation for the Transformer architecture. They argue that self-attention is not merely a clever engineering trick, but a "natural" and necessary consequence of the symmetries inherent in sequence-to-sequence (seq2seq) problems.
The Symmetry of Sequences
To understand why self-attention works, the authors analyze seq2seq functions through the lens of Symmetry and Group Theory. They propose that any robust seq2seq model must respect certain fundamental symmetries in the embedding space where tokens (words or amino acids) are represented as vectors.
1. Orthogonal Equivariance
The authors argue that the "meaning" or relationship between tokens should not change if the entire embedding space is rotated or flipped. This is known as orthogonal equivariance. If you apply an orthogonal transformation to the input sequence, the output sequence should undergo the same transformation. This ensures the model's logic is independent of the specific coordinate system used for embeddings.
2. Functions with "Knowledge"
In a typical seq2seq task, the model uses learned parameters (like grammar rules or vocabulary) to process an input. The authors represent this as a "knowledge" matrix ($Z$). Crucially, they assume this knowledge exists in the same embedding space as the input sequence ($X$). For the system to remain symmetric, any transformation applied to the input must also be applied to the knowledge.
3. The Finite Information Principle
To make the model computationally feasible, the authors introduce the "Finite Information Principle." This assumes that the model must be describable by a fixed number of parameters, regardless of the length of the input sequence. This constraint prevents the model from growing infinitely complex as the sequence length increases.
Theoretical Derivation of Self-Attention
By applying the First Fundamental Theorem of Invariant Theory, the authors derive the general form that any function respecting these symmetries must take.
The General Form
In Proposition 2, the authors prove that a symmetric seq2seq function with knowledge must follow the structure:
$$f(X, Z) = Xg_1(X^T X, Z^T X, Z^T Z) + Zg_2(X^T X, Z^T X, Z^T Z)$$
This result is profound because it shows that the output must be a linear combination of the input elements ($X$) and the knowledge ($Z$), where the coefficients ($g_1, g_2$) are functions of the inner products (dot products) between the inputs and the knowledge.
Connecting to the Transformer
When we simplify this general form by treating $Z$ as the learned parameters for Queries and Keys and focusing on the most informative terms, the expression reduces to:
$$f(X, Z) \approx Xg(Z^T X)$$
This is the skeletal structure of the self-attention mechanism. The term $Z^T X$ represents the dot-product interaction between the input and the model's learned "knowledge" (the $Q^T K$ interaction), and the multiplication by $X$ represents the weighted sum of values ($V$).
Key Insights
- Why Dot Products? The theory explains that dot products are the simplest possible way to relate vectors while maintaining orthogonal equivariance and a fixed parameter count. This provides a first-principles justification for the $Q^T K$ structure.
- Permutation Equivariance: If the order of tokens in a sequence is irrelevant (or handled by separate position encodings), the attention matrix is further restricted to a form that closely mirrors the Softmax-based attention used in modern Transformers.
- Multi-Head Attention: The paper suggests that Multi-Head Attention is a natural extension to increase the capacity of these symmetric functions without violating the underlying symmetry requirements.
Conclusion and Future Work
This research moves the field away from trial-and-error architecture design toward a principled understanding of deep learning structures. By showing that self-attention is a mathematical necessity for symmetric seq2seq problems, the authors provide a rigorous answer to why Transformers have become the dominant architecture in AI.
While the paper successfully justifies the attention mechanism, the authors note that other components, such as Layer Normalization and specific non-linearities (like GELU), require further theoretical exploration. Additionally, the theory suggests that while dot products are the simplest quadratic form, other kernels (such as RBF kernels) are mathematically valid and could lead to the development of new, specialized attention mechanisms.
Summary updated