Positional Encodings and Group Theory | 3Blue1Brown and Alok Puranik

Motivation and Core Hypothesis

• The analysis begins with the observation that disparate, widely-used positional encoding methods (specifically RoPE and linear attention variants) share a common underlying algebraic structure derived from group theory and representation theory.
• The author hypothesizes that the entire space of valid positional encodings can be characterized by a minimal set of mathematical assumptions regarding linearity and translation variance.
• Translation Variance Assumption: The influence of a query at time $t$ on a key at time $s$ must depend strictly on the difference $(t - s)$, not the absolute positions, mirroring Noether's theorem symmetries.

Mathematical Derivation of the General Form

• Linearity Constraint: Assuming positional modifications are linear operators, the transformation of queries and keys is represented by time-dependent matrices $F(t)$ and $G(s)$.
• The Bridge Matrix $A$: The attention score is defined by a matrix $A(t-s) = F(t)^T G(s)$, which acts as a "bridge" shifting keys from time $s$ to time $t$ to enable dot products.
• Group Homomorphism: Imposing the constraint that $A(0) = I$ (identity) and translation variance leads to the functional equation $A(t + s) = A(t)A(s)$, identifying $A(t)$ as an exponential map of the time variable.
• Resulting Form: The general solution is $A(t) = e^{tX}$, where $X$ is a constant matrix determining the dynamics of the positional encoding.

Classification of Dynamics via Eigenvalues

• Real Eigenvalues:
  • $\lambda < 0$: Corresponds to exponential decay, where influence fades as time distance increases (observed in some linear attention variants).
  • $\lambda = 0$: Represents time-independence, where the position has no effect on the interaction.
  • $\lambda > 0$: Implies exponential growth of influence with distance, which is generally unstable and avoided in practice.
• Complex Eigenvalues (Conjugate Pairs):
  • Purely imaginary eigenvalues ($\pm bi$) correspond to rotations (RoPE), where the encoding rotates the vector space over time without scaling magnitude.
  • Complex eigenvalues with a negative real part result in damped rotations (rotation with decay).

Non-Diagonalizable Cases (Jordan Blocks)

• When $X$ is non-diagonalizable (containing Jordan blocks), the matrix exponential $e^{tX}$ yields polynomial time dependence rather than exponential or trigonometric.
• A $2 \times 2$ Jordan block with eigenvalue 0 results in linear time dependence ($A(t) = I + tX$).
• Larger Jordan blocks can theoretically generate higher-order polynomial dependencies (e.g., quadratic acceleration).
• Recovering ALiBi: The ALiBi positional encoding, which subtracts a linear penalty based on distance, is shown to be mathematically equivalent to a specific non-diagonalizable construction where the input vectors are augmented with fixed components.

Practical Implications and Design Choices

• RoPE Implementation: RoPE is explicitly identified as the case where $X$ consists of a direct sum of $2 \times 2$ rotation blocks with purely imaginary eigenvalues ($X = \text{diag}(\pm i\theta_k)$), and no decay component ($\text{Re}(\lambda) = 0$).
• Frequency Selection: In RoPE, frequencies $\theta_k$ are typically chosen as a geometric sequence to ensure coverage of various temporal scales (fine-grained vs. long-range dependencies).
• Theoretical Completeness: The framework concludes that the space of plausible, stable positional encodings is effectively "exhausted" by combinations of exponential decay, pure rotation, and damped rotation, suggesting that undiscovered useful encodings would likely reside in the unstable (growing) or higher-order polynomial (non-diagonalizable) regimes.