Simulate Sinusoidal Positional Encoding

1. Background Knowledge

Positional Encoding addresses Transformer's permutation invariance: self-attention treats all tokens equally regardless of order, lacking inherent sequential awareness. The original Transformer uses sinusoidal positional encoding to inject position $i$ information into $D$-dimensional embeddings via periodic sine/cosine functions with increasing frequencies $10000^{k/D}$, creating unique, wavelength-diverse encodings. This deterministic approach ensures fixed-length extrapolation and relative position learning via phase differences.

Prerequisites: Basic trigonometry ($\sin$, $\cos$), array indexing (0-based), floating-point math. $D$ even ensures paired sin/cos dimensions.

2. Algorithm Approach

Direct formula implementation: for each dimension $k \in [0, D-1]$,

Key insight: Even indices use $\sin$ with frequency scaling $2k/D$; odd use $\cos$ shifted by one pair $(k-1)$. Precompute powers via log(10000) * k/D for numerical stability.

Common technique: Vectorized NumPy/PyTorch loops or broadcasting over $k$.

3. Step-by-Step Strategy

1. Initialize zero vector $p$ of shape $(D,)$.
2. Loop over dimensions $k = 0$ to $D-1$:

• Compute angular frequency: $\omega_k = 10000^{-k/D}$ (use exp(-log(10000) * k/D)).
• If $k \% 2 == 0$: $p_k = \sin(i \cdot$\omega$_k)$.
• Else: $p_k = \cos(i \cdot$\omega$_{k-1})$ where $\omega_{k-1} = 10000^{-(k-1)/D}$.

3. Return $p$.

Vectorized Python example:

import numpy as np

def positional_encoding(i: int, D: int) -> np.ndarray:
 p = np.zeros(D)
 div_term = np.exp(-np.log(10000.0) * np.arange(0, D, 2) / D) # Even freqs
 p[0::2] = np.sin(i * div_term) # Even: sin(i / 10000^{k/D})
 p[1::2] = np.cos(i * np.roll(div_term, -1)) # Odd: cos(i / 10000^{(k-1)/D})
 return p[:D] # Truncate if needed

Note: np.roll(div_term, -1) shifts for odd indices; slice [:D] handles even $D$.

4. Common Pitfalls

• Off-by-one indexing: Odd $k$ uses $(k-1)/D$, not $k/D$—easy mix-up.
• Numerical instability: Direct 10000 ** (k/D) overflows; use exp(log(10000) * k/D).
• Even $D$ assumption: Code fails if $D$ odd (last dim unpaired); constraints guarantee even.
• Integer division: Use float exponents (k/D, not k//D).
• Range errors: $i < 1000$, $D \leq 512$ safe, but verify no overflow in sin/cos args.
• 1-based vs 0-based: Formula uses 0-based $i \geq 0$.

5. Time & Space Complexity

• Time: $O(D)$ per call—single pass over dimensions with constant-time trig ops.
• Space: $O(D)$ for output vector + $O(D/2)$ temp array; optimal as output required.
• Batch optimization: For sequence length $N$, precompute matrix $O(ND)$; here single $i$.

This yields exact original Transformer encoding, enabling position-aware attention. Test: positional_encoding(0, 4) → $[0, 1, 0, 1]$.