PaperlayerView exact revision on arXiv

Source-linked AI summary

KERPLE: Kernelized Relative Positional Embedding for Length Extrapolation

Ta-Chung Chi, Ting-Han Fan, Peter J. Ramadge, Alexander I. Rudnicky

arXiv:2205.09921v2cs.CLcs.LG

TL;DR

Transformers may need to process sequences longer than their fixed training lengths, while increasing training length is often costly. KERPLE models relative positional differences with CPD kernels and uses constant shifts to connect them to PD kernels in attention. Its logarithmic variant performs well at longer extrapolation lengths across evaluated tasks, though its comparison with T5 varies at shorter lengths.

  • Problem

    Transformers often need to handle sequences longer than their fixed training length, while substantially increasing training length is often infeasible because training cost is O(L^2).

    Source: §1 · p. 1

  • Method

    KERPLE models relative positional differences with shift-invariant CPD kernels, shifts them to PD kernels, and evaluates power and logarithmic variants.

    Source: §3.1 · p. 3, §4 · pp. 4–5

  • Results

    Across evaluated tasks, the logarithmic variant consistently outperforms prior work at all extrapolation lengths; versus T5, it is close to or slightly worse below 2048 and excels at longer lengths.

    Source: §5.2 · p. 7

  • Takeaways & Limitations

    The logarithmic variant's extrapolation tendency holds across all datasets evaluated in this work.

    Source: §5.2 · p. 7

    The study considers simple CPD kernels and defers more complicated forms to future work.

    Source: §3.2 · p. 4

Abstract

from arXiv · show

Relative positional embeddings (RPE) have received considerable attention since RPEs effectively model the relative distance among tokens and enable length extrapolation. We propose KERPLE, a framework that generalizes relative position embedding for extrapolation by kernelizing positional differences. We achieve this goal using conditionally positive definite (CPD) kernels, a class of functions known for generalizing distance metrics. To maintain the inner product interpretation of self-attention, we show that a CPD kernel can be transformed into a PD kernel by adding a constant offset. This offset is implicitly absorbed in the Softmax normalization during self-attention. The diversity of CPD kernels allows us to derive various RPEs that enable length extrapolation in a principled way. Experiments demonstrate that the logarithmic variant achieves excellent extrapolation performance on three large language modeling datasets. Our implementation and pretrained checkpoints are released at https://github.com/chijames/KERPLE.git.

1 Introduction

Length extrapolation matters because transformers may need to handle sequences longer than their fixed training length, while substantially increasing training length is often infeasible. The introduction motivates relative positional embeddings as a promising approach to length changes.

1 Introduction

  • Transformers often need to handle sequences longer than the fixed training length, but substantially increasing that length is often infeasible because training cost is O(L^2).The paper frames continued performance on longer inference sequences as length extrapolation.Source: §1 · p. 1
  • Relative positional embeddings model positional differences and are considered more robust to input-length changes than absolute positional embeddings.The paper motivates studying how relative positional embeddings work.Source: §1 · p. 1
  • Figure 1 illustrates training the 3-Para-Log variant on length-3 sequences and activating a final row at inference to extrapolate to length 4.Its a, b, and p parameters are shared across layers within each attention head.Source: Figure 1 · p. 2

2 Background and Related Work

The background introduces transformer attention and positional information, surveys absolute and relative positional embeddings, and describes kernel applications in transformers.

2.1 Preliminary

  • A transformer maps token embeddings to query, key, and value vectors, while its operation is described as position-agnostic.The paper notes that positional information is believed to help model token interactions.Source: §2.1 · p. 2

2.2 Positional Embedding

  • Absolute positional embeddings add a position-specific vector to each token embedding; relative positional embeddings instead model the difference between positions.T5 uses bucketed relative distances and log-binning, while rotary embeddings encode position through rotations.Source: §2.2 · pp. 2–3

2.3 Kernel and its Application in Transformer

  • Kernel methods generalize inner products to high-dimensional spaces, and transformer research applies kernels to positional embeddings or uses feature maps to linearize attention.The latter line of work aims to reduce self-attention's computational cost.Source: §2.3 · p. 3

3 Theoretical Foundations of CPD Kernels

The theoretical foundation uses shift-invariant conditionally positive definite kernels to model relative position differences and relates them to positive definite kernels. It derives CPD kernel families and shows how constant shifts make them usable as PD kernels in self-attention.

3.1 PD and CPD Kernels

  • CPD kernels generalize positional distances, but PD kernels are needed to represent the inner products used by self-attention.The paper models relative position with a shift-invariant function of the difference between positions.Source: §3.1 · p. 3

3.2 Constructing PD Kernels From CPD Kernels via Constant Shifts

  • Scaling, summation, fractional powers, and logarithms of suitable CPD kernels yield families including negative distance powers and negative log-distance forms.The listed forms include -a||x - x'||^p and -b log(1 + a||x - x'||^p), with 0 < p <= 2.Source: §3.2 · p. 4
  • The paper limits its study to simple CPD kernels and defers more complicated compositions to future work.Examples of deferred forms combine distance powers with logarithmic transformations.Source: §3.2 · p. 4
  • Adding a sufficiently large constant to a CPD kernel makes it positive definite, and Softmax's shift invariance means the exact offset need not be specified in the positional design.The offset can be found by geometric sequence search if needed.Source: §3.2 · p. 4

4 Kernelized Relative Positional Embedding

KERPLE models relative positional differences with shift-invariant conditionally positive definite kernels, then incorporates them into self-attention through a composite kernel. The section develops power and logarithmic variants and relates them to ALiBi and T5 positional bias.

4 Kernelized Relative Positional Embedding

  • A sufficiently large constant makes the conditionally positive definite positional kernel positive definite, and Softmax normalization absorbs that offset.The constant can be enlarged by geometric search until it is large enough.Source: §4 · pp. 4–5
  • The composite kernel augments the query–key attention product with positional information from a bias kernel.The formulation retains the original query–key product while adding positional information.Source: §4 · p. 5
  • With ℓ=2, the practical choices are power and logarithmic variants; more complicated variants train more slowly for only marginal perplexity improvement.The authors report that the two simpler choices offer advantages in both performance and speed based on their study.Source: §4 · p. 5
  • With a triangle bias kernel, KERPLE reduces to ALiBi, which the authors identify as their state-of-the-art extrapolation comparison.The paper focuses its experiments on comparison with ALiBi.Source: §4 · p. 5
  • The logarithmic variant is connected to T5's log-binning bias, uses fewer parameters, but cannot learn non-monotonic relations.The paper contrasts 2×12 parameters for its variant with 32×12 for T5 bias.Source: §4 · p. 5

5 Experiments

Experiments compare KERPLE variants with established positional methods across three language-modeling datasets and multiple extrapolation lengths. The logarithmic variant generally combines strong long-context perplexity with competitive training speed, while more complex kernels and position-wise analyses clarify its behavior.

5.1 Dataset and Implementation Description

  • Experiments use OpenWebText2, GitHub, and ArXiv, with models adapted from GPT-NeoX and trained at sequence length 512.The implementation uses a 162M configuration, bfloat16, and one 40 GB NVIDIA A100 GPU; evaluations test lengths from 512 to 16384.Source: §5.1 · p. 6, §5.2 · p. 6, Table 2 · p. 6

5.2 Experimental Results (Also c.f. Appendix A.4 to A.7)

  • Across datasets and extrapolation lengths, KERPLE-log has lower perplexity than KERPLE-power, beats T5 at longer lengths, and outperforms ALiBi, Rotary, and Sinusoidal.It is 4.4% faster than KERPLE-power and 9.7% faster than T5; versus ALiBi, Rotary, and Sinusoidal it is respectively 1.6% slower, 7.5% faster, and 3.0% slower.Source: §5.2 · pp. 6–7, Table 3 · p. 7

5.3 Experiments on Complicated Kernels

  • More complex composite kernels show no clear extrapolation advantage over the practical variants, although 3-para-log is slightly better in perplexity than the two-parameter logarithmic variant.The authors conclude that increasing kernel complexity does not necessarily improve relative positional embeddings.Source: §5.3 · p. 8, Table 5 · p. 8

5.4 Plots of Kernel Functions

  • On GitHub, learned log kernels include flat functions, whereas ALiBi and the generalized power variant quickly reach very negative values.The authors interpret the flat log kernels as effectively extending window attention and corroborating use of more distant token information.Source: §5.4 · p. 8, Figure 2 · p. 8, Figure 3 · p. 9

5.5 Position-wise Perplexity Evaluation

  • At evaluation length 4096, KERPLE-log’s perplexity continues to decrease through position 4096 and is lower than windowed-at-512 KERPLE across positions.It uses 24 additional learnable parameters and has almost the same training speed as window attention; its PPL@512 is lowest among the model variants.Source: §5.5 · p. 9

6 Conclusion and Future Work

KERPLE kernelizes relative positional embeddings for length extrapolation using conditionally positive definite kernels, which can be shifted to preserve self-attention’s inner-product interpretation. The paper reports strong extrapolation for its logarithmic variant and identifies several future directions.

6 Conclusion and Future Work

  • KERPLE generalizes relative positional embeddings for length extrapolation by applying conditionally positive definite kernels to positional differences.The framework derives practical variants from these kernels.Source: §6 · p. 9
  • A constant offset can convert the CPD kernels into positive definite kernels while preserving self-attention’s inner-product interpretation.The offset is implicitly absorbed by Softmax normalization during self-attention.Source: §6 · pp. 9–10
  • The logarithmic KERPLE variant achieves exceptional extrapolation performance on three large language modeling datasets.The conclusion also points to general kernel families, non-monotonic positional effects, higher-dimensional inputs, and memory efficiency as future directions.Source: §6 · pp. 9–10

7 Broader Impact

The paper describes its work as developing kernel-based understanding of relative positional embeddings for transformers. It notes potential applications across domains as well as possible societal harms.

7 Broader Impact

  • The authors identify natural language, programming language, and DNA or protein sequence modeling as domains where positional information may be useful.They describe the work as developing understanding of relative positional embeddings using expressive kernel classes.Source: §7 · p. 10
  • Transformer research may have positive economic effects by enabling tasks that humans cannot do or improving accuracy and efficiency.Source: §7 · p. 10
  • The authors also note potential harms from automation-related job loss, improper text generation, and privacy issues in data collection.They state these implications apply broadly to NLP research rather than to this work specifically.Source: §7 · p. 10

A.1 Proof of CPD Shift Lemma

The CPD Shift Lemma states that any conditionally positive definite kernel can be made positive definite by adding a sufficiently large nonnegative constant. The proof reduces the quadratic-form condition to vectors near the zero-sum subspace and uses continuity.

A.1 Proof of CPD Shift Lemma

  • For a CPD kernel k, some c ≥ 0 makes c + k(x, y) positive definite.The proof seeks a sufficiently large c so the associated quadratic form is nonnegative for every unit vector.Source: §A.1 · p. 14
  • The proof reduces the claim to the case where the kernel matrix has no zero eigenvalues and the minimum unit-vector quadratic form is negative.If that minimum is nonnegative, the matrix is already positive semidefinite; zero-eigenvalue directions do not obstruct the shift.Source: §A.1 · p. 14
  • For vectors orthogonal to the all-ones vector, strict CPD gives a strictly positive quadratic form.With zero eigenvalues excluded, equality cannot occur on that subspace.Source: §A.1 · p. 15
  • Continuity keeps the quadratic form positive for nearby unit vectors, and vectors with a small sum can be approximated by vectors orthogonal to the all-ones vector.This establishes positivity near the zero-sum subspace, leaving the constant shift to handle the remaining directions.Source: §A.1 · p. 15

A.2 Shift-invariant Kernels with Bounded and Unbounded Ranges

The section develops bounded shift-invariant kernels from positive definite functions and unbounded kernels from a representation theorem. Distance powers yield an unbounded positive definite kernel after an appropriate constant shift when 0 < p ≤ 2.

A.2 Shift-invariant Kernels with Bounded and Unbounded Ranges

  • The bounded family k(m, n) = exp(−a|m − n|^p), with a > 0 and 0 < p ≤ 2, follows from positive definiteness of exp(−|x|^p) [1938].The resulting kernel values lie in (0, 1].Source: §A.2 · p. 16
  • The bounded exponential family does not cover kernels with unbounded range, so the section uses a representation theorem for positive functions whose positive powers are positive definite [1938].The theorem represents such functions using a positive definite ψ and a real constant c.Source: §A.2 · p. 16
  • For 0 < p ≤ 2, a sufficiently large constant c makes k(m, n) = c − |m − n|^p a shift-invariant positive definite kernel.For p > 2, no such c exists.Source: §A.2 · pp. 16–17
  • The shifted distance-power kernel is interpreted as turning the positional dissimilarity |m − n|^p into a similarity, with c supplying the shift needed for positive definiteness [2000].Source: §A.2 · p. 17

A.3 Experiments on Gaussian-like Kernels

Gaussian-like kernels were tested as positional biases and weights, but their extrapolation performance remained limited compared with the logarithmic variant. The weight formulation performed better than the bias formulation.

A.3 Experiments on Gaussian-like Kernels

  • Gaussian-like kernels had large perplexities at every extrapolation length and limited advantages compared with the logarithmic variant.The authors conclude that a better class of shift-invariant kernels is needed for length extrapolation.Source: §A.3 · p. 17
  • The composite variants include bias and weight forms, with generalized variants learning an exponential power constrained to (0, 2] for positive definiteness.The kernels were evaluated on OpenWebText2, GitHub, and ArXiv.Source: §A.3 · p. 17
  • Gaussian-like kernels performed better as weights than as biases across the evaluated datasets.The authors relate this to bounded positive kernels being able to model a weight.Source: §A.3 · p. 17

A.4 Experiments on Large Model, Longer Training Length, and Wikitext-103

Supplementary experiments compare KERPLE-log with positional-embedding baselines across model sizes, training lengths, and datasets. Additional analyses relate its effective-length patterns to dataset and kernel differences, while position-wise perplexity comparisons show its behavior at length 16384.

A.4 Experiments on Large Model, Longer Training Length, and Wikitext-103

  • On the 1.3B model, KERPLE-log remained stronger than ALiBi on GitHub and ArXiv, while at training length 1024 it remained better than ALiBi and T5 bias, especially at longer evaluation lengths.On Wikitext-103, KERPLE-log was superior to ALiBi under ALiBi’s implementation and configurations.Source: §A.4 · p. 18, Table 9 · p. 19, Table 10 · p. 19

A.5 Additional Analyses

  • Effective length marks where positional-bias attenuation becomes strong; OpenWebText2 kernels focus more on distant relations, while ArXiv and GitHub show the opposite trend.The logarithmic variant tends to focus farther than the power variant, consistent with its slower decay; ALiBi’s fixed parameter yields the same curve across datasets, unlike learnable parameters that may adapt to dataset characteristics.Source: §A.5 · p. 20

A.6 Position-wise Perplexity for Length=16384

  • At evaluation length 16384, KERPLE-log was below its windowed-at-512 version most of the time, while T5 perplexity exploded and ALiBi remained worse than window attention.The curves compare position-wise perplexity on GitHub against window attention at 512.Source: §A.6 · pp. 20–21, Figure 7 · p. 21

A.7 The Choice of codebase and Hyperparameters

  • The experiments adopted GPT-NeoX baseline implementations and hyperparameters, except for batch size, and KERPLE hyperparameters were not fine-tuned.The datasets were those released with the GPT-NeoX codebase.Source: §A.7 · p. 21

Related papers

Loading 2205.09921v2…