Positional encoding

In deep learning, the positional encoding is a component of sequence models, especially Transformers. Input data such as text, images, or audio is converted to a sequence of numerical representations called tokens, and the position of each token is encoded as a vector. This combination of token embedding vectors and positional encoding vectors is a context window.

Positional encoding is used because the standard attention mechanism used in Transformers by default treats all tokens symmetrically over all positions (i.e. permutation-symmetric), thus effectively treating the input as a bag of tokens, rather than a sequence of tokens.

Typology

Absolute vs relative positional encoding:

• In an absolute positional encoding scheme, the position of a token within a context is encoded. That is, it matters whether a token is at position 1 or position 100. This was proposed in 2017, just before Transformer was published.
• In a relative positional encoding scheme, the relative position of two tokens within a context is encoded. That is, it matters not whether a token is at position 1 or position 100, and it only matters whether one token is in front of another token by 1 or 100. This property is also called translational invariance. This was propsed in 2018, just after Transformer was published.

Learned vs designed positional encoding:

• In a learned positional encoding scheme, the parameters of positional encoding are learned like any other parameter in a model, usually by backpropagation.
• In a designed positional encoding scheme, the parameters are not learned, and picked by the researchers. That is, they are hyperparameters.

For example, BERT used two levels of positional embeddings, one for the per-token position, and one for per-segment position. Both are absolute and learned. It was reported that learned absolute positional encoding generally perform better than relative positional encoding when there are special tokens that always occur in a specific location, such as the [CLS] token of BERT-like architectures. However, with learned absolute positional encoding, a model cannot process contexts longer than what it is trained for.

Other possibly desirable properties of a positional encoding scheme include:

• Symmetry: In a symmetric positional encoding scheme, the positional encoding of a token ${\displaystyle n}$ tokens before is the same as that of a token ${\displaystyle n}$ tokens after. This property only makes sense for non-causal Transformers, since in a causal Transformer, a token cannot pay any attention to its subsequent tokens.
• Monotonicity: In a monotonic positional encoding scheme, the positional encoding increases attention weighing on nearby tokens compared to far-away tokens.

Sinusoidal

The original transformer paper (Attention Is All You Need) uses a sinusoidal absolute positional encoding. Each token is converted to an token embedding vector ${\displaystyle x_{t}}$, plus a positional encoding vector ${\displaystyle p(t)}$.

${\displaystyle x_{t}}$ depends only on the identity of the token, not on ${\displaystyle t}$. That is, the token "the" would have the same ${\displaystyle x_{t}}$, no matter if it appears in the first or the last position. ${\displaystyle p(t)}$ depends only on the position of the token, not on the identity of the token. That is, the ${\displaystyle t}$-th token always has the same ${\displaystyle p(t)}$, no matter if it is "the" or "a".

Both the encoder and the decoder takes ${\displaystyle x_{t}+p(t)}$ as input. This is shown in the picture.

Both ${\displaystyle v_{t}}$ and ${\displaystyle p(t)}$ has the same number of dimensions, since they must be added. Both of them have even dimensions, since that is what the positional encoding vector requires.

Let the dimension be ${\displaystyle 2d}$, then the position encoding vector is defined as$${\displaystyle p(t)=(\cos(\omega _{1}t),\sin(\omega _{1}t),\cos(\omega _{2}t),\sin(\omega _{2}t),\dots ,\cos(\omega _{d}t),\sin(\omega _{d}t)}$$

where ${\displaystyle \omega _{k}=b^{-{\frac {k-1}{d}}}}$.

Here, ${\displaystyle b}$ is a free parameter that should be significantly larger than the biggest ${\displaystyle k}$ that would be input into the positional encoding function. The original paper uses ${\displaystyle d=50,b=10000}$.

More succinctly,$${\displaystyle p(t)=(e^{i\omega _{k}t})_{k\in 1:d},\quad ,\omega _{k}=b^{-{\frac {k-1}{d}}}}$$In typical implementations, all operations are done over the real numbers, not the complex numbers, but since complex multiplication can be implemented as real 2-by-2 matrix multiplication, this is a mere notational difference.

Radix interpretation

The positional encoding has been interpreted as implementing a base-${\displaystyle b^{1/k}}$ positional number system for representing real numbers:

Position	Frequency	Factor	Tokens per cycle ("wavelength")	Tokens per cycle at ${\displaystyle d=50,b=10000}$
Lowest	1	${\displaystyle e^{i\omega _{1}t}=e^{it}}$	${\displaystyle 2\pi }$	6.3
Next lowest	${\displaystyle b^{-1/d}}$	${\displaystyle e^{i\omega _{2}t}=e^{ib^{-1/d}t}}$	${\displaystyle 2\pi b^{1/d}}$	7.5
Highest	${\displaystyle b^{-(d-1)/d}}$	${\displaystyle e^{i\omega _{d}t}=e^{ib^{-(d-1)/d}t}}$	${\displaystyle 2\pi b^{(d-1)/d}}$	52261

The effect of base-${\displaystyle b}$ positional number system means the attention mechanism is to apportion its attention by coordinate. For low frequency (long wavelength) coordinates, RoPE implicitly states that these coordinates encode information that varies slowly over a sequence, and vice versa for high frequency (low wavelength) coordinates. Concretely, the first 2 coordinates are treated as encoding features that vary quickly every token, while the last 2 coordinates are treated as encoding features that vary slowyl over 10000s of tokens.

ALiBi

In the original Transformer, positions are encoded by a vector ${\displaystyle p(t)}$ that is added to the token embedding vector ${\displaystyle x_{t}}$, and the Transformer only sees their sum ${\displaystyle x_{t}+p(t)}$. ALiBi (Attention with Linear Biases) is a relative positional encoding scheme that partially decouples the position encoding from the token embedding, by injecting positional encoding directly into each attention mechanism block.

The attention mechanism block in the original Transformer is$${\displaystyle {\begin{aligned}{\text{Attention}}(Q,K,V)={\text{softmax}}\left({\frac {QK^{\mathrm {T} }}{\sqrt {d_{K}}}}+M\right)V\end{aligned}}}$$where ${\displaystyle Q,K,V}$ stand for the matrices for the query, key, and value vectors, ${\displaystyle d_{K}}$ stands for the dimension of the key, and ${\displaystyle M}$ stands for the mask matrix. Explicitly,$${\displaystyle Q={\begin{bmatrix}q_{1}\\q_{2}\\\vdots \\q_{\ell _{\text{query}}}\end{bmatrix}},K={\begin{bmatrix}k_{1}\\k_{2}\\\vdots \\k_{\ell _{\text{key-value}}}\end{bmatrix}},V={\begin{bmatrix}v_{1}\\v_{2}\\\vdots \\v_{\ell _{\text{key-value}}}\end{bmatrix}}}$$

The ALiBi attention mechanism modifies it to$${\displaystyle {\begin{aligned}{\text{Attention}}(Q,K,V)={\text{softmax}}\left({\frac {QK^{\mathrm {T} }}{\sqrt {d_{K}}}}+M+sB\right)V\end{aligned}}}$$Here, ${\displaystyle s\in \mathbb {R} }$ is a learnable scalar, and ${\displaystyle B}$ is the linear bias matrix defined by$${\displaystyle B={\begin{bmatrix}0&-1&-2&-3&\cdots \\-1&0&-1&-2&\cdots \\-2&-1&0&-1&\cdots \\-3&-2&-1&0&\cdots \\\vdots &\vdots &\vdots &\vdots &\ddots \\\end{bmatrix}}}$$in other words, ${\displaystyle B_{i,j}=|j-i|}$. The idea being that the linear bias matrix is a softened mask. Just as ${\displaystyle 0}$ represent full attention paid, and ${\displaystyle -\infty }$ represents no attention paid, the linear bias matrix linearly decreases the attention logit. Note that in the causally masked Transformer, any attention paid to the future is blanked out by the causal mask matrix$${\displaystyle M_{\text{causal}}={\begin{bmatrix}0&-\infty &-\infty &\dots &-\infty \\0&0&-\infty &\dots &-\infty \\0&0&0&\dots &-\infty \\\vdots &\vdots &\vdots &\ddots &\vdots \\0&0&0&\dots &0\end{bmatrix}}}$$so the upper triangular part of ${\displaystyle B}$ does not matter.

ALiBi allows pretraining on short context windows, then fine-tuning on longer context windows. Since it is directly plugged into the attention mechanism, it can be combined with any positional encoder that is plugged into the "bottom" of the entire network (which is where the sinusoidal encoder on the original transformer, as well as RoPE and many others, are located).

More generally, is a more general version:$${\displaystyle {\begin{aligned}{\text{Attention}}(Q,K,V)={\text{softmax}}\left({\frac {QK^{\mathrm {T} }}{\sqrt {d_{K}}}}+M+B\right)V\end{aligned}}}$$where ${\displaystyle B}$ is a Toeplitz matrix.$${\displaystyle B={\begin{bmatrix}b_{0}&b_{-1}&b_{-2}&\cdots &\cdots &b_{-(n-1)}\\b_{1}&b_{0}&b_{-1}&\ddots &&\vdots \\b_{2}&b_{1}&\ddots &\ddots &\ddots &\vdots \\\vdots &\ddots &\ddots &\ddots &b_{-1}&b_{-2}\\\vdots &&\ddots &b_{1}&b_{0}&b_{-1}\\b_{n-1}&\cdots &\cdots &b_{2}&b_{1}&b_{0}\end{bmatrix}}}$$For example, Google T5 used a learned Relative Position Representation, where the diagonals in the positional bias matrix ${\displaystyle B}$ are grouped into bands to decrease the number of learnable parameters of ${\displaystyle B}$.

Relatedly, Relative Position Representations was an early attempt by some of the original authors of the Transformer to make a decoupled relative positional encoding scheme. It has not been used much in practice since 2018. In this scheme, learned positional encoding vectors are added to the key and value vectors in an attention mechanism block.

RoPE

RoPE (Rotary Positional Encoding) is another scheme for relative positional encoding. It works by rotating the key and value vectors input into a attention mechanism block.

Consider a feature vector with even dimensions: ${\displaystyle x=(x_{1},x_{2},\dots ,x_{2d-1},x_{2d})\in \mathbb {R} ^{2d}}$. Like in the original sinuisoidal positional encoding scheme, it can be written as a complex vector ${\displaystyle v=(x_{1}+ix_{2},\dots ,x_{2d-1}+ix_{2d})\in \mathbb {C} ^{d}}$. Then, to encode it as positioned at ${\displaystyle t}$, the ${\displaystyle t}$-th feature vector is represented by rotating its entries:$${\displaystyle \operatorname {RoPE} (((x_{1}+ix_{2}),\dots ,(x_{2d-1}+ix_{2d})),t):=(e^{i\omega _{1}t}(x_{1}+ix_{2}),\dots ,e^{i\omega _{d}t}(x_{2d-1}+ix_{2d}))}$$where the frequencies ${\displaystyle \omega _{1},\dots ,\omega _{d}\in \mathbb {R} }$ are usually designed by hand. A standard design is ${\displaystyle \omega _{k}=b^{-{\frac {k-1}{d}}}}$ where ${\displaystyle b=10000}$, the same base as the original Transformer, and common since the original RoPE paper and Llama.

In an attention mechanism, RoPE is implemented as$${\displaystyle {\begin{aligned}{\text{RoPEAttention}}(Q,K,V)={\text{softmax}}\left({\frac {\operatorname {RoPE} (Q)\operatorname {RoPE} (K)^{\mathrm {T} }}{\sqrt {d_{K}}}}+M\right)V\end{aligned}}}$$where$${\displaystyle \operatorname {RoPE} (Q)={\begin{bmatrix}\operatorname {RoPE} (q_{1},1)\\\operatorname {RoPE} (q_{2},2)\\\vdots \\\operatorname {RoPE} (q_{\ell _{\text{query}}},\ell _{\text{query}})\end{bmatrix}}}$$and similarly for the RoPE key matrix ${\displaystyle \operatorname {RoPE} (K)}$.

Like the original positional encoding, it is translation-invariant and behaves as a base-${\displaystyle b}$ positional number system. Specifically, translation symmetry means that$${\displaystyle \operatorname {RoPE} (x,t)\cdot \operatorname {RoPE} (x',t')=\operatorname {RoPE} (x,t+\Delta t)\cdot \operatorname {RoPE} (x',t'+\Delta t)}$$for any ${\displaystyle x,x'\in \mathbb {C} ^{n}}$ and any ${\displaystyle t,t',\Delta t\in \mathbb {R} }$.

NoPE

In NoPE (No Positional Encoding), there is no positional encoding. The idea is that a decoder's causal masking lets each token ${\displaystyle t}$ to see only tokens ${\displaystyle 1:t}$, which is an implicit kind of positional encoding.

NoPE is rarely used for all attention modules of a Transformer, since it degrades performance too much is used to save compute. However, NoPE may be used for some attention modules to trade off performance for computing cost. For example, Llama 4 alternates layers of NoPE and RoPE, with RoPE in 3 layers and NoPE in the 4th. They call it iRoPE ("interleaved RoPE").

Context extension

Since the per-token cost of inference scales with context length, training cost is decreased by using shorter contexts during training. However, this would make the resulting model bad at using longer contexts. Consequently, a common way to train a model is to "train short, test long", i.e. training a model on short contexts, and use it on long contexts.

Context extension was a concern since the original Transformer paper. In it, the authors reported trying both learned positional encoding and desigend positional encoding. They found both to result in similar performance, and decided to use the designed positional encoding, since it "may allow the model to extrapolate to sequence lengths longer than the ones encountered during training".

A slightly more sophisticated method is train according to a curriculum: Begin by training on a short context length, then train on a longer context length. This can be repeated. For example, the model can be pretrained on context lengths up to 8K tokens, then up to 64K, then up to 512K.

Context lengths can even be mixed during training. It was found that given a fixed training budget, training on a mixture of long contexts and short contexts resulted in higher performance than purely training on long contexts.

In general, context extension using RoPE consists of training a model on one context length ${\displaystyle L}$ with one set of RoPE angles ${\displaystyle \omega _{1},\dots ,\omega _{d}}$, then its RoPE angles are modified to ${\displaystyle \omega _{1}',\dots ,\omega _{d}'}$, and it is trained further on context length ${\displaystyle L'=sL}$ for some ${\displaystyle s>1}$.

Some architectures natively support context extension. For example, convolutional seq2seq, and sliding window attention, are both insensitive to context length.

References