# Yekun's Note

Machine learning notes and writeup. We summarize the positional encoding approaches in transformers.

## Summary

PE Relative Trainable Each Layer Extrapolation
Sinusoidal
T5 bias
RoPE
ALiBi
KERPLE
Sandwich
xPos

## Position Encoding

### Sinusoidal Position Embeddings

Sinusoidal position embeddings are constantly encoded vectors to be added on token embeddings of the first transformer layer.

where $\text{pos}$ is the position in the sentence and $i$ is the order along the embedding vector dimension. Assume this allows to learn to attend by relative positions, since for and fixed offset $k$, $\text{PE}_{\text{pos}+k}$ can be represented as the linear function of $\text{PE}_{\text{pos}}$ .

### Rotary Position Embedding (RoPE)

Rotary Position Embedding (RoPE)  proposes to use complex numbers as the base field of encoding space. Instead of working in $\mathbb{R}^d$, it uses consecutive pairs of elements of the query and key vectors in $\mathbb{C}^{d/2}$ to be a single complex number.

Specifically, instead of viewing $\mathbf{q}=(q_1,q_2,q_3,q_4,\ldots,q_{d})$ as a $d$-dimensional real vector, RoPE views it as $\mathbf{q}=(q_1+iq_2, q_3+iq_4,\ldots q_{d-1} + iq_{d})\in\mathbb{C}^{d/2}$. If $d$ is odd, RoPE pads it with a dummy coordinate to ensure things line up correctly. Alternatives, it simply increases $d$ by one.

#### Derivation

The complex number format of RoPE is written as:

It is convenient to convert into matrix equation:

where $M_j=\begin{pmatrix}\cos m\theta_j & -\sin m\theta_j \\sin m\theta_j & \cos m\theta_j\end{pmatrix}$ , $\mathbf{\Theta_m}$ is the block diagonal rotation matrix, $\mathbf{W_q}$ is learned query weights, and $\mathbf{X_m}$ is the embedding of the $m$-th token.

Due to the high computation cost of sparse matrix, it is implemented as:

where $\odot$ denotes the element-wise product (*).

• Extension to Multiple Dimensions

Difference from sinusoidal embedding

1. Sinusoidal embeddings apply to each coordinate individually, while RoPE mixes pairs of coordinates.
2. Sinusoidal embeddings add a $\cos(m\theta)$ or $\sin(m\theta)$ term, while RoPE uses a multiplicative factor.

#### Implementation

GPT-NeoX (PyTorch) implementation.

#### RoPE with Bias

 finds that RoPE w/ Bias can increase the capability of length extrapolation.

where $\boldsymbol{\mathcal{R}}_m, \boldsymbol{\mathcal{R}}_n$ are rotation matrix, $\boldsymbol{a}, \boldsymbol{b}$ are learnable bias.

NB: Pure self-attention softmax gets equivalent results with or without bias term, since it can be cancelled by the softmax normalization.

But reducing the bias term for self-attention with RoPE cannot obtain the same results.

### T5 Bias

T5 adds no position encoding to word embeddings. Instead, it add a learned, shared bias to each query-key self-attention score that is dependent on just the distance between the query and key. In which multiple different distances share the same learned bias, which might be beneficial for length interpolation. Specifically, a fixed number of embeddings are learned, each corresponding to a range of possible key-query offsets.

T5 uses a bucket of 32 learnable parameters and assign the relative position bias with a log-binning strategy:

 finds that T5 bias enables length extrapolation.

T5 uses 32 embeddings for all models with ranges that increase in size logarithmically up to an offset of 128 beyond which it assigns all relative positions to the same embedding. All position embeddings are shared across all layers in T5, though within a given layer each attention head uses a different learned position embedding.

### ALiBi (Attention with Linear Biases)

Length extrapolation allows transformers training on short sequences while testing on substantially long sequences, by means of relative positional encoding.

ALiBi adds a static, non-learnable bias to the query-key dot product. As is done in T5 bias and RoPE, it adds position information to keys and querys at each layer.

where $\alpha$ is a head-specific slope (fixed). For $i$-th heads, the value of slope takes $\alpha_i = 2^{\frac{-8}{i}}$.

ALiBi bias is not multiplied by the $\sqrt{d_k}$ scaling factor as in the original transformer.

It is observed that ALiBi and T5 bias show length extrapolation ability, while RoPE and sinusoidal position do not have.

### KERPLE

KErnelize Relative Positional Embedding for Length Extrapolation (KERPLE) proposes kernelized positional embeddings as follows:

where $r_1,\cdots, r_{\mathcal{l}}$ are learnable parameters.

Triangle kernel: $c-|m-n|$. It reduces to ALiBi.

### xPos

Extrapolatable Position Embedding (XPOS) proposes:

### Sandwich

The self-attention is calculated as:

The temporal bias terms is:

Sandwich

### Randomized Position

 introduce randomized position encoding that simulates the positions of longer sequences and randomly selects an ordered subset to fit the sequence’s length.

It allows transformers to generalize to sequences of unseen length (increasing test accuracy by 12.0% on average) across 15 algorithmic reasoning tasks.

### No Position

 observe that LMs without any explicit position encoding (NoPos) are still competitive with standard transformers across datasets, model sizes, and sequence length. It shows that causal LMs might derive positional awareness not only from the explicit positioning mechanism, but also from the causal mask effects.

Causal transformer LM can achieve competitive results with original LMs, while the bidirectional masked LMs fail to converge. This may be because that causal LMs can learn positions from the autoregressive nature (left-to-right) but masked LMs are order-invariant.

NB: LMs without explicit positional encodings (NoPos) are always slightly worse, suggesting the importance of inductive positional bias.

### Position Interpolation

Instead of extrapolation,  presents position interpolation (PI) that directly downscales the non-integer position indices (RoPE-based) so that the maximum position index matches the previous context window limit in pre-training.

It simply adds two lines of code.

SuperHOT-13B uptrained on scaling factor of 0.25, compared to base LLaMa 13B and a test LoRA trained on 6K sequence length with no scaling.

Note that PI requires further fine-tuning to take effects for length extrapolation.

### NTK-Aware Scaled RoPE

Background

1. “Simply interpolating the RoPE’s fourier space “linearly” is very sub-optimal, as it prevents the network to distinguish the order and positions of tokens that are very close by.”
2. “Scaling down the fourier features too much will eventually even prevent succesful finetunes (this is corroborated by the recent paper by Meta that suggests an upper bound of ~600x)”

NTK-Aware Scaled RoPE designs a nonlinear interpolation scheme using Neural Tangent Kernel (NTK) theory. It changes the base of the RoPE instead of the scale, which intuitively changes the “spinning” speed from which each of the RoPE’s dimension vectors shifts to the next.

Implementation 

Average perplexity of LLaMA-7B on a set of 40 very long prompts (12k+ context size).

### Dynamic Linear RoPE

Dynamic linear RoPE: set the scale to max_seq_len/current position length, which can slowly increase the scale.

### Dynamic NTK-Aware Scaled RoPE

Cons:

• Compared to dynamic linear scaling, NTK-Aware has higher perplexity for shorter sequences, but better perplexity at the tail end of the sequence lengths.
• NTK-aware RoPE suffers from catastrophic perplexity blowup, like regular RoPE and static linear scaling.

 introduces dynamic NTK-aware scaling. The scaling of $\alpha$ is set to:

This dynamically scales the $\alpha$ as the sequence length increases.

#### Partial NTK Scaled RoPE

Combine RoPE, Linear, NTK.

1. 1.Vaswani, Ashish, Noam M. Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser and Illia Polosukhin. “Attention is All you Need.” NeurIPS (2017).
2. 2.Press, Ofir, Noah A. Smith and Mike Lewis. “Train Short, Test Long: Attention with Linear Biases Enables Input Length Extrapolation.” ICLR 2022.
3. 3.Su, Jianlin, Yu Lu, Shengfeng Pan, Bo Wen and Yunfeng Liu. “RoFormer: Enhanced Transformer with Rotary Position Embedding.” ArXiv abs/2104.09864 (2021).
4. 4.
5. 5.
6. 6.
7. 7.Raffel, C., Shazeer, N.M., Roberts, A., Lee, K., Narang, S., Matena, M., Zhou, Y., Li, W., & Liu, P.J. (2020). Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer. JMLR.
8. 8.Press, O., Smith, N.A., & Lewis, M. (2022). Train Short, Test Long: Attention with Linear Biases Enables Input Length Extrapolation. ICLR.
9. 9.Chi, T., Fan, T., Ramadge, P.J., & Rudnicky, A.I. (2022). KERPLE: Kernelized Relative Positional Embedding for Length Extrapolation. NeurIPS.
10. 10.Sun, Y., Dong, L., Patra, B., Ma, S., Huang, S., Benhaim, A., Chaudhary, V., Song, X., & Wei, F. (2022). A Length-Extrapolatable Transformer. ArXiv, abs/2212.10554.
11. 11.Chi, T., Fan, T., Rudnicky, A., & Ramadge, P.J. (2022). Dissecting Transformer Length Extrapolation via the Lens of Receptive Field Analysis.
12. 12.Haviv, Adi et al. “Transformer Language Models without Positional Encodings Still Learn Positional Information.” Conference on Empirical Methods in Natural Language Processing (2022).
13. 13.Ruoss, A., Del'etang, G., Genewein, T., Grau-Moya, J., Csordás, R., Abbana Bennani, M., Legg, S., & Veness, J. (2023). Randomized Positional Encodings Boost Length Generalization of Transformers. ACL.
14. 14.
15. 15.Chen, Shouyuan, Sherman Wong, Liangjian Chen and Yuandong Tian. Extending Context Window of Large Language Models via Positional Interpolation. ArXiv abs/2306.15595 (2023).
16. 16.
17. 17.
18. 18.
19. 19.
20. 20.
21. 21.
22. 22.
23. 23.