Relative Positional Encodings in Transformers: How Shaw's Attention, Transformer-XL, and T5 Relative Biases Preserve Translation Invariance

Standard self-attention operations in transformer architectures possess no inherent awareness of sequence order. Because scaled dot-product attention computes interactions across sets of tokens without regard to index ordering, early models relied on absolute positional encodings to inject sequential structure. While absolute encodings assign rigid coordinate embeddings to each index in a sequence, natural language semantics depend on relative displacement: the syntactic relationship between a verb and its direct object remains identical whether the pair appears at indices (4, 5) or (104, 105).

To resolve this limitation, researchers developed relative positional encoding mechanisms. Beginning with the relation-aware self-attention of Shaw et al. (2018), expanding into the four-term query-key matrix decomposition of Transformer-XL (2019), and refining into the logarithmic scalar bucketing of T5 (2020) and the disentangled attention of DeBERTa (2021), relative positional representations established translation invariance across transformer layers. Understanding their mathematical structure clarifies why relative representations improve generalizability and why modern LLM serving frameworks eventually migrated toward rotational formulations like RoPE to overcome KV cache and kernel fusion bottlenecks.

The Translation Invariance Failure in Absolute Positional Encodings

The vanilla transformer architecture introduced by Vaswani et al. (2017) addressed sequence order by adding fixed sinusoidal vectors to input token embeddings:

$$PE_{(pos, 2i)} = \sin\left(\frac{pos}{10000^{2i/d_{\text{model}}}}\right), \quad PE_{(pos, 2i+1)} = \cos\left(\frac{pos}{10000^{2i/d_{\text{model}}}}\right)$$

Subsequent models such as BERT (Devlin et al., 2018) and GPT-2 (Radford et al., 2019) replaced fixed sinusoids with learned absolute position embeddings $W_p \in \mathbb{R}^{L_{\max} \times d_{\text{model}}}$, where each absolute sequence index $i$ is assigned a dedicated parameter vector $p_i$.

Absolute position injection suffers from three structural deficiencies:

1. Lack of Translation Invariance: In an absolute encoding framework, the attention logit between token $x_i$ at position $i$ and token $x_j$ at position $j$ depends on the absolute coordinates $i$ and $j$. If an identical phrase is shifted by an offset $\Delta$, the inner products $(x_i + p_i) W_Q W_K^T (x_j + p_j)^T$ change completely because $p_{i+\Delta} \neq p_i$ and $p_{j+\Delta} \neq p_j$.
2. Context Length Hard Ceilings: Learned absolute position tables cannot process sequences longer than $L_{\max}$ without resizing and fine-tuning the embedding table. Any token index beyond the pre-allocated table has no representation.
3. Weak Long-Range Generalization: Because higher position indices receive fewer gradient updates during training (due to variable sequence lengths in batches), parameters corresponding to tail positions remain poorly calibrated.

Shaw's Formulation: Relation-Aware Attention on Graph Distances

Shaw et al. (2018) introduced the first formal relative positional encoding mechanism by framing sequence inputs as directed, labeled graphs where edge labels correspond to the signed relative distance $j - i$ between tokens.

Instead of adding position vectors to input word embeddings before the first layer, Shaw et al. integrated relative position representations directly into the attention mechanism at every self-attention layer.

In standard self-attention, the unnormalized attention score $e_{ij}$ and output vector $z_i$ are computed as:

$$e_{ij} = \frac{(x_i W^Q)(x_j W^K)^T}{\sqrt{d_z}}$$

$$z_i = \sum_{j=1}^n \alpha_{ij} (x_j W^V), \quad \text{where } \alpha_{ij} = \frac{\exp(e_{ij})}{\sum_{k=1}^n \exp(e_{ik})}$$

Shaw et al. augmented the keys and values with learned relative position embedding tensors $a_{ij}^K, a_{ij}^V \in \mathbb{R}^{d_z}$:

$$e_{ij} = \frac{x_i W^Q (x_j W^K + a_{ij}^K)^T}{\sqrt{d_z}} = \frac{x_i W^Q (x_j W^K)^T + x_i W^Q (a_{ij}^K)^T}{\sqrt{d_z}}$$

$$z_i = \sum_{j=1}^n \alpha_{ij} (x_j W^V + a_{ij}^V)$$

Distance Clipping and Parameter Sharing

To prevent the number of unique relative parameters from scaling quadratically with maximum sequence length, Shaw et al. introduced a clipping threshold $k$:

$$\text{clip}(j - i, k) = \max(-k, \min(k, j - i))$$

The relative representations are defined by indexing into learned tables $w^K, w^V \in \mathbb{R}^{(2k+1) \times d_z}$:

$$a_{ij}^K = w_{\text{clip}(j-i, k)}^K, \quad a_{ij}^V = w_{\text{clip}(j-i, k)}^V$$

This clipping formulation asserts that beyond a distance of $k$ tokens, precise relative offset information provides diminishing syntactic value.

In their empirical ablations on WMT 2014 English-to-German and English-to-French translation, Shaw et al. established two critical findings:

• Incorporating relative representations solely into keys ($a_{ij}^K$) achieved a 1.3 BLEU gain over absolute encodings, whereas adding relative representations to values ($a_{ij}^V$) yielded marginal additional benefit while substantially increasing memory traffic.
• Combining relative encodings with absolute encodings provided no performance advantage over pure relative encodings, proving that absolute coordinates are redundant when pairwise relative offsets are explicitly modeled.

Transformer-XL: The Four-Term Decomposition and Segment Recurrence

While Shaw's approach proved effective for machine translation, autoregressive language modeling required processing long continuous documents without resetting positional context across chunk boundaries.

Dai et al. (2019) introduced Transformer-XL, which paired segment-level recurrence with a mathematical decomposition of self-attention logits.

Expanding the standard attention logit between absolute embeddings $(E_{x_i} + U_i)$ and $(E_{x_j} + U_j)$, where $E$ represents word embeddings and $U$ represents absolute position vectors, yields four terms:

$$\mathbf{A}_{i,j}^{\text{abs}} = \underbrace{E_{x_i} W_Q W_K^T E_{x_j}^T}_{\text{(a) Content-Content}} + \underbrace{E_{x_i} W_Q W_K^T U_j^T}_{\text{(b) Content-Position}} + \underbrace{U_i W_Q W_K^T E_{x_j}^T}_{\text{(c) Position-Content}} + \underbrace{U_i W_Q W_K^T U_j^T}_{\text{(d) Position-Position}}$$

Transformer-XL re-engineers this expansion into a relative formulation:

$$\mathbf{A}_{i,j}^{\text{rel}} = \underbrace{E_{x_i} W_q W_{k,E}^T E_{x_j}^T}_{\text{(a) Content-Content}} + \underbrace{E_{x_i} W_q W_{k,R}^T R_{i-j}^T}_{\text{(b) Content-Dependent Position Bias}} + \underbrace{u W_{k,E}^T E_{x_j}^T}_{\text{(c) Global Content Bias}} + \underbrace{v W_{k,R}^T R_{i-j}^T}_{\text{(d) Global Position Bias}}$$

Key mathematical modifications include:

1. Sinusoidal Relative Matrix: The absolute key position vector $U_j$ in terms (b) and (d) is replaced by $R_{i-j}$, a fixed sinusoidal embedding representing the relative distance $i - j$.
2. Dedicated Projection Weights: Transformer-XL splits key projection weights into $W_{k,E}$ for content vectors and $W_{k,R}$ for relative positional vectors.
3. Learned Global Bias Vectors: The query positional vector $U_i$ in terms (c) and (d) is replaced by learnable global parameter vectors $u, v \in \mathbb{R}^{d}$. Because the query position does not need to specify an absolute index, $u$ and $v$ represent inductive biases: $u$ captures the general baseline affinity between query content and key content, while $v$ captures the baseline affinity for relative distance $i - j$ regardless of specific word identity.

This formulation allowed Transformer-XL to cache hidden states from preceding context segments without disrupting positional integrity, expanding effective temporal dependency by 450% over standard fixed-window transformers.

T5 Relative Position Biases: Scalar Offsets and Logarithmic Bucketing

Raffel et al. (2019) in the Text-to-Text Transfer Transformer (T5) introduced a simplified, parameter-efficient relative position mechanism.

Rather than projecting high-dimensional relative position vectors through weight matrices, T5 defines relative positional encoding as a learned scalar bias $b_{i,j}$ added directly to the pre-softmax attention logit:

$$e_{ij} = \frac{q_i k_j^T}{\sqrt{d_k}} + b_{i,j}$$

For an attention layer with $H$ heads, $b_{i,j}$ is a vector of $H$ learned scalars.

Relative Distance (j - i) Mapping in T5:

Exact Buckets (0 to 7):
Distance:  0   1   2   3   4   5   6   7
Bucket:   [0] [1] [2] [3] [4] [5] [6] [7]

Logarithmic Buckets (8 to max_distance):
Distance:  8-11   12-16   17-23   24-33   ...   128+
Bucket:    [8]     [9]     [10]    [11]   ...   [31]

Logarithmic Distance Bucketing

To span long sequences without maintaining a separate parameter for every integer offset, T5 partitions relative distances into 32 discrete buckets:

1. Exact Local Allocation: For small relative offsets $|j - i| < 8$, the bucket index equals the exact integer distance.
2. Logarithmic Long-Range Allocation: For relative offsets between 8 and a maximum threshold (typically 128 tokens), bucket indices are assigned using a logarithmic scale:

$$\text{bucket}(d) = 8 + \left\lfloor \frac{\log(d / 8)}{\log(\text{max\_distance} / 8)} \cdot (\text{num\_buckets} - 8) \right\rfloor$$

1. Saturation: Distances exceeding $\text{max\_distance}$ map to the final bucket index ($\text{num\_buckets} - 1$).
2. Directional Splitting: In bidirectional encoder layers, positive and negative relative distances are mapped to separate bucket sets (e.g., 16 buckets for backward offsets, 16 for forward offsets). In causal decoder layers, only backward offsets ($j \le i$) are parameterized.

This logarithmic bucketing scheme reflects an intuitive linguistic principle: distinguishing between offset 1 and offset 2 (adjacent words) is essential for local phrase parsing, whereas distinguishing between offset 80 and offset 85 is unnecessary for capturing distant semantic relationships.

DeBERTa: Disentangled Attention

He et al. (2020) advanced relative position modeling in DeBERTa (Decoding-enhanced BERT with Disentangled Attention).

DeBERTa represents each input token using two separate vectors: a content vector $H_i$ and a relative position vector $P_{i|j}$ describing relative distance. The cross-attention logit is computed by disentangling content and position interactions into three additive matrices:

$$A_{i,j} = \underbrace{H_i W_q W_k^T H_j^T}_{\text{Content-to-Content}} + \underbrace{H_i W_q W_{k,r}^T P_{i|j}^T}_{\text{Content-to-Position}} + \underbrace{P_{j|i} W_{q,r} W_k^T H_j^T}_{\text{Position-to-Content}}$$

DeBERTa intentionally excluded the fourth term (Position-to-Position, $P_{j|i} W_{q,r} W_{k,r}^T P_{i|j}^T$), demonstrating empirically that pure relative distance between two indices without content conditioning contains zero semantic information and adds unnecessary gradient noise.

Computational Complexity and KV Cache Bottlenecks

Despite their empirical strengths in language understanding benchmarks (GLUE, SuperGLUE), early relative positional mechanisms created severe computational and memory bottlenecks in large-scale autoregressive serving.

Attention Kernel Incompatibility

In modern LLM inference runtimes, scaled dot-product attention relies on fused GPU kernels such as FlashAttention and FlashAttention-3, which load blocks of $Q$, $K$, and $V$ matrices into SRAM and compute attention on chip without materializing the full $N \times N$ attention matrix in HBM.

• Shaw & DeBERTa: Require tensor contractions involving 3D or 4D intermediate tensors ($O(B \times H \times N \times N \times d)$), forcing high-bandwidth memory reads and preventing fused SRAM execution.
• T5: Requires adding an $N \times N$ matrix $B$ to $Q K^T$. While easier to fuse than Shaw's method, dynamically indexing into bucket tables introduces warp divergence and non-contiguous memory lookups during kernel execution.

Autoregressive KV Caching Invalidation

During autoregressive token generation, standard decoders maintain a key-value cache (KV cache) storing projected representations of past tokens:

$$K_{\text{cache}} = [k_1, k_2, \dots, k_{t-1}], \quad V_{\text{cache}} = [v_1, v_2, \dots, v_{t-1}]$$

Under Shaw's formulation, key representations depend on the query position:

$$k_j^{(i)} = x_j W^K + a_{i - j}^K$$

Because the relative offset $i - j$ changes at every decoding step $i$, previously cached key vectors become obsolete, requiring full re-computation ($O(t^2)$ per step) unless complex relative indexing transformations are applied.

Positional Encoding Paradigms:

Absolute Learned (BERT, GPT):
Input = Token_Embedding + Position_Embedding[i]

Relative Key/Value Bias (Shaw):
Attention_Logit = (q_i * (k_j + a_{j-i})^T) / sqrt(d)

Relative Scalar Bias (T5):
Attention_Logit = (q_i * k_j^T) / sqrt(d) + Bucket_Bias[j - i]

Rotational Multiplicative (RoPE):
Attention_Logit = (R_i * q_i) * (R_j * k_j)^T / sqrt(d) = q_i * R_{j-i} * k_j^T / sqrt(d)

The Modern Transition to Rotational and Slope Encodings

The tension between translation invariance and hardware efficiency drove the design of next-generation position representations in modern frontier LLMs:

1. Rotary Position Embeddings (RoPE): Su et al. (2021) introduced RoPE, which encodes relative position purely through multiplicative complex rotations applied to query and key vectors:

$$\langle \mathbf{R}_{\Theta, m}^d \mathbf{q}, \mathbf{R}_{\Theta, n}^d \mathbf{k} \rangle = \mathbf{q}^T \mathbf{R}_{\Theta, n - m}^d \mathbf{k}$$

RoPE embeds relative distance $n - m$ directly into the standard inner product without adding parameters, preserving standard static KV caching and full compatibility with FlashAttention.

1. Attention with Linear Biases (ALiBi): Press et al. (2021) replaced learned bucket tables with static, head-specific linear penalty slopes $m \cdot (j - i)$. ALiBi requires zero learned parameters and facilitates out-of-distribution sequence length extrapolation.

Relative positional encodings proved that sequence modeling in transformers is fundamentally relational. While early formulations incurred memory and cache overheads, their theoretical principles directly shaped the rotary and slope mechanisms that power modern foundation models today.

Sources

• Shaw, P., Uszkoreit, J., & Vaswani, A. (2018). Self-Attention with Relative Position Representations. NAACL-HLT 2018. https://arxiv.org/abs/1803.02155
• Dai, Z., Yang, Z., Yang, Y., Carbonell, J., Le, Q. V., & Salakhutdinov, R. (2019). Transformer-XL: Attentive Language Models Beyond a Fixed-Length Context. ACL 2019. https://arxiv.org/abs/1901.02860
• Raffel, C., Shazeer, N., 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. Journal of Machine Learning Research (JMLR). https://arxiv.org/abs/1910.10683
• He, P., Liu, X., Gao, J., & Chen, W. (2021). DeBERTa: Decoding-enhanced BERT with Disentangled Attention. ICLR 2021. https://arxiv.org/abs/2006.03654
• Su, J., Lu, Y., Pan, S., Ahmed, B., Liu, B., & Zheng, Y. (2024). RoFormer: Enhanced Transformer with Rotary Position Embedding. Neurocomputing. https://arxiv.org/abs/2104.09864
• Press, O., Smith, N. A., & Lewis, M. (2022). Train Short, Test Long: Attention with Linear Biases Enables Input Length Extrapolation. ICLR 2022. https://arxiv.org/abs/2108.12409