Positional Encoding

Table of Contents

1. Learning Objectives
2. Prerequisites
3. Notation
4. Core Intuition
5. Permutation Equivariance of Attention
6. Desiderata for Positional Encodings
7. Sinusoidal Encoding: Derivation
8. Properties and Proofs
9. Absolute Position Injection
10. Learned Position Embeddings
11. Rotary Position Embeddings (RoPE)
12. ALiBi: Attention with Linear Biases
13. Comparison and Extrapolation
14. Worked Examples
15. Connection to the Broader Curriculum
16. Common Pitfalls and Misconceptions
17. Research Perspective
18. Summary of Takeaways
19. Exercises

Learning Objectives

After reading this chapter, you should be able to:

1. Prove that Self-Attention is permutation-equivariant and explain why position information must be injected.
2. State desiderata for positional encodings (uniqueness, bounded norm, relative expressibility, extrapolation).
3. Derive sinusoidal encodings from the relative-shift property using rotation matrices.
4. Prove that $\text{PE}(t)^T \text{PE}(t')$ depends only on $t - t'$.
5. Contrast absolute (sinusoidal, learned) vs. relative (RoPE, ALiBi) position methods.
6. Explain why RoPE dominates modern LLMs and how it connects to RoPE in LLMs.

Prerequisites

• Self-Attention — attention formula, Q/K/V
• Eigenvalues & Eigenvectors — rotation matrices (optional)

Notation

• $n$ — Sequence length
• $d$ — Model (embedding) dimension
• $\text{PE}(\text{pos}, 2i)$ — Sinusoidal encoding at position $\text{pos}$
• $\mathbf{E} \in \mathbb{R}^{n \times d}$ — Positional encoding matrix
• $\mathbf{X} + \mathbf{E}$ — Position-augmented embeddings

Core Intuition

Self-Attention computes outputs as similarity-weighted sums of values. Dot products $\mathbf{q}_i^T \mathbf{k}_j$ are invariant to permutations of token order — the model treats input as an unordered set. Language, code, and time series require order: "dog bites man" $\neq$ "man bites dog".

Positional encodings break permutation symmetry by making each token's representation depend on its index $t$. Methods range from adding position vectors to embeddings (sinusoidal, learned) to encoding position in attention itself (RoPE, ALiBi).

Modern LLMs overwhelmingly use RoPE (RoPE), which embeds relative position directly in query–key products — compatible with KV Cache and length extrapolation.

Series context. Chapter 8, Part II (Chapter 12 in full curriculum) in Volume II.

Permutation Equivariance of Attention

Theorem 1 (Permutation Equivariance). Let $\mathbf{P}_\pi$ be the permutation matrix for permutation $\pi$. Then:

Proof. $(\mathbf{P}_\pi \mathbf{Q})(\mathbf{P}_\pi \mathbf{K})^T = \mathbf{P}_\pi \mathbf{Q}\mathbf{K}^T \mathbf{P}_\pi^T$. Softmax is row-wise; permuting rows and columns consistently preserves structure. $\mathbf{A}(\mathbf{P}_\pi \mathbf{V}) = \mathbf{P}_\pi(\mathbf{A}\mathbf{V})$. $\blacksquare$

Corollary 1. Without position information, shuffling input tokens shuffles outputs identically — the model cannot use order.

Desiderata for Positional Encodings

Definition 1 (Positional Encoding). A function $\text{PE}: \mathbb{Z}_{\geq 0} \to \mathbb{R}^d$ maps position $t$ to a $d$-dimensional vector.

Desiderata:

• D1 (Uniqueness): $t \neq t' \implies \text{PE}(t) \neq \text{PE}(t')$
• D2 (Bounded norm): $\|\text{PE}(t)\|$ bounded as $t \to \infty$
• D3 (Relative shift): $\exists$ linear map $\mathbf{M}_k$ with $\mathbf{M}_k \text{PE}(t) = \text{PE}(t+k)$ for all $t$
• D4 (Smoothness): $\text{PE}(t)$ varies smoothly in $t$
• D5 (Extrapolation): Defined for $t > T_{\max}$ (training max length)

Sinusoidal Encoding: Derivation

Seek $\text{PE}(t)_{2i} = \sin(\omega_i t)$, $\text{PE}(t)_{2i+1} = \cos(\omega_i t)$ satisfying D3.

Lemma 1 (Angle Addition).

The matrix is a rotation $\mathbf{R}(\omega k)$ depending only on offset $k$.

Definition 2 (Sinusoidal PE, Vaswani et al.).

Frequencies $\omega_i = 10000^{-2i/d}$: low $i$ → high frequency (fine position); high $i$ → low frequency (coarse position).

Properties and Proofs

Proposition 1 (Constant Norm). $\|\text{PE}(t)\|_2^2 = d/2$ for all $t$.

Proof. $\sum_i (\sin^2 + \cos^2) = d/2$. $\blacksquare$

Theorem 2 (Relative Position in Dot Product).

Proof. $\sin(\omega t)\sin(\omega t') + \cos(\omega t)\cos(\omega t') = \cos(\omega(t-t'))$. $\blacksquare$

Attention dot products $\mathbf{x}_t^T \mathbf{x}_{t'} + \text{PE}(t)^T \text{PE}(t')$ encode relative distance $(t - t')$.

Absolute Position Injection

Definition 3 (Absolute PE). Input to the Transformer:

Position is added before the first attention layer. Subsequent layers propagate position implicitly through representations.

Learned Position Embeddings

Definition 4 (Learned PE). Learn matrix $\mathbf{E}_{\text{pos}} \in \mathbb{R}^{T_{\max} \times d}$; row $t$ is position $t$.

• Parameters — 0 — $T_{\max} \cdot d$
• Extrapolation — Partial — Fails beyond $T_{\max}$
• Relative structure — Via dot product — Not guaranteed

Used in BERT, GPT-2. Works well within training length; fails catastrophically beyond.

Rotary Position Embeddings (RoPE)

Definition 5 (RoPE). Apply position-dependent rotation to Q and K:

where $\mathbf{R}_t$ is block-diagonal with $2 \times 2$ rotations at frequencies $\omega_i$.

Theorem 3 (Relative Position in RoPE).

Proof. $\mathbf{R}_t^T \mathbf{R}_{t'} = \mathbf{R}_{t'-t}$ (rotation composition). $\blacksquare$

Full treatment in RoPE. Used in LLaMA, Mistral, Gemma.

ALiBi: Attention with Linear Biases

Definition 6 (ALiBi). Add linear penalty to attention scores:

with head-specific slopes $m_h = 2^{-8h/H}$.

Properties: Zero extra parameters; explicit locality bias; extrapolates to longer sequences. Used in BLOOM, MPT.

Comparison and Extrapolation

• Sinusoidal — Via dot product — Partial — 0 — Original Transformer
• Learned — No — No — $T_{\max} d$ — BERT, GPT-2
• RoPE — Native — Yes (with scaling) — 0 — LLaMA, modern LLMs
• ALiBi — Bias — Yes — $H$ slopes — BLOOM

NTK-aware scaling extends RoPE to longer contexts by rescaling frequencies at inference — see RoPE.

Worked Examples

Example 1: PE Norm

For $d = 512$, $\|\text{PE}(t)\|^2 = 256$ for all $t$ — positions contribute fixed energy.

Example 2: Relative Dot Product

$\text{PE}(5)^T \text{PE}(8) = \text{PE}(0)^T \text{PE}(3)$ — depends only on distance 3.

Example 3: RoPE Attention

Positions 10 and 13 differ by 3; same attention score as positions 100 and 103.

Connection to the Broader Curriculum

• Self-Attention — base mechanism
• RoPE — deep dive for LLMs
• KV Cache — RoPE compatible with caching
• Scaling Laws — context length scaling

Common Pitfalls and Misconceptions

Pitfall 1: Assuming attention encodes order without PE.

Pitfall 2: Using learned PE beyond $T_{\max}$.

Pitfall 3: Confusing absolute PE addition with RoPE rotation.

Pitfall 4: Ignoring position in cross-attention (encoder–decoder).

Research Perspective

Sinusoidal PE (Vaswani et al., 2017). RoPE (Su et al., 2021) now standard. ALiBi (Press et al., 2022). Long-context research: YaRN, NTK scaling, position interpolation.

Summary of Takeaways

• Problem — Attention is permutation-equivariant
• Sinusoidal — Rotation-based relative shift
• Dot product — Depends on $t - t'$
• RoPE — $\mathbf{q}_t^T \mathbf{R}_{t'-t} \mathbf{k}_{t'}$
• Modern choice — RoPE for autoregressive LLMs

Next: Variational Autoencoders

Exercises

Exercise 1. Prove Theorem 1 (permutation equivariance).

Exercise 2. Derive (2) from angle addition formulas.

Exercise 3. Prove Theorem 2 (relative dot product).

Exercise 4. Prove Theorem 3 (RoPE relative attention).

Exercise 5. Compare parameter counts: learned PE vs. RoPE for $T_{\max} = 8192$, $d = 4096$.

Exercise 6. Why does ALiBi use different slopes per head?

Exercise 7. Explain failure mode of learned PE at 2× training length.

Exercise 8. Connect RoPE rotations to Eigenvalues of rotation matrices.