Fourier Position Embedding: Enhancing Attention’s Periodic Extension for Length Generalization

Ermo Hua, Che Jiang, Xingtai Lv, Kaiyan Zhang, Ning Ding, Youbang Sun, Biqing Qi, Yuchen Fan, Xuekai Zhu, Bowen Zhou · 2024

Read Fourier Position Embedding: Enhancing Attention’s Periodic Extension for Length Generalization by Ermo Hua, Che Jiang, Xingtai Lv, Kaiyan Zhang, Ning Ding, Youbang Sun, Biqing Qi, Yuchen Fan, Xuekai Zhu, Bowen Zhou (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-17739.txt.

Introduction

Ermo Hua and nine co-authors rethink how language models mark word position in this two thousand twenty-four paper. Models need position signals to read order. The standard trick, rotary position embedding, helps models stretch to longer texts, but only so far. The authors trace the failure with signal processing theory. They show the method works by a hidden Fourier transform, and that other model parts damage the needed spectrum.

Linear layers and activations smear the frequencies, and short training starves some of them. Their fix, Fourier position embedding, repairs the spectrum on purpose. Models using it extend to longer contexts more cleanly. The paper serves researchers who push models toward book-length inputs. It reframes a practical trick as a signal design problem.

Catalog record

CREATORErmo Hua, Che Jiang, Xingtai Lv, Kaiyan Zhang, Ning Ding, Youbang Sun, Biqing Qi, Yuchen Fan, Xuekai Zhu, Bowen Zhou
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE46 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-17739

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Fourier Position Embedding: Enhancing Attention’s Periodic Extension for Length Generalization Ermo Hua, Che Jiang, Xingtai Lv, Kaiyan Zhang, Ning Ding, Youbang Sun, Biqing Qi, Yuchen Fan, Xuekai Zhu, Bowen Zhou Abstract Extending the context length of Language Models (LMs) by improving Rotary Position Embedding (RoPE) has become a trend. While existing works mainly address RoPE’s limitations within attention mechanism, this paper provides an analysis across nearly all parts of LMs, uncovering their adverse effects on length generalization for RoPE-based attention. Using Discrete Signal Processing theory, we show that RoPE enables periodic attention by implicitly achieving Non-Uniform Discrete Fourier Transform . However, this periodicity is undermined by the spectral damage caused by: 1) linear layers and activation functions outside of attention; 2) insufficiently trained frequency components brought by time-domain truncation. Building on our observations, we propose Fourier Position Embedding (FoPE) , which enhances attention’s frequency-domain properties to improve both its periodic extension and length generalization. FoPE constructs Fourier Series and zero-outs the destructive frequency components, increasing model robustness against the spectrum damage. Experiments across various model scales and benchmarks show that, within varying context windows, FoPE maintains a more stable performance compared to RoPE and ALiBi. Several analyses and ablations bring further support to our method and theoretical modeling. https://github.com/TsinghuaC3I/Fourier-Position-Embedding 1 Introduction (a) Accuracy on Passkey Retrieval (higher is better) (b) Perplexity on C4 (lower is better) Figure 1: Training with max_seq_length = 512, FoPE extends the model’s information retrieval ability in a needle-in-haystack task to 16x training length, while performance with RoPE and ALiBi drops dramatically at just 2x training length. When comparing perplexity, FoPE shows significantly more stable performance than RoPE and performs only slightly worse than ALiBi. Figure 2: The reasons why RoPE’s periodic extension deteriorates and how FoPE addresses these issues to improve length generalization. (a) As signals pass through linear and nonlinear transformations, this causes spectral leakage and distortion, mixing multiple frequencies into a single dimension. Under RoPE, each dimension is treated as a single-frequency component. By contrast, FoPE models each dimension as a Fourier series of different frequency components, thereby separating information more effectively and mitigating spectral damage. (b) FoPE eliminates inadequately trained frequency components, which are harmful for periodic extension. By preserving only the zero-frequency component, FoPE safeguards periodic extension and delivers more robust length generalization. Generation based on the information from long contexts is crucial for Language Models (LMs). However, LMs are typically trained on a fixed context window ( Vaswani 2017 ; Touvron et al. 2023 ; Groeneveld et al. 2024 ) and tends to overfit to the specific context length. Many studies consider the absolute position embedding ( Vaswani 2017 ) to be the source of overfitting in length generalization. As mitigation, several relative position embedding methods have been proposed ( Press et al. 2021 ; Su et al. 2024 ; Peng et al. 2023 ; Jin et al. 2024 ) to improve LMs’ long-distance dependency. Among these, ALiBi ( Press et al. 2021 ) introduced a position-biased attention mask, which linearly declines the attention weights based on distance. ALiBi delivers stable perplexity in pre-training, but it loses the information from long-distance tokens, resulting in poor performance on long-context downstream tasks. Another method, RoPE ( Su et al. 2024 ) , uses the phase of complex numbers to store the position information. Combined with continual pre-training and other interpolation-based methods ( Peng et al. 2023 ; Xiong et al. 2024 ; Chen et al. 2024a ; Jin et al. 2024 ) , RoPE provides better access to long-distance information, making it one of the most widely used position embedding. However, RoPE-based LMs still struggle with length generalization without supplementary methods like YARN ( Peng et al. 2023 ) . In this paper, we take a closer look at RoPE in the frequency-domain with tools from Discrete Signal Processing (DSP) theory. Our modeling reveals that RoPE implicitly performs Non-Uniform Discrete Fourier Transform (NUDFT) on the hidden states, enabling periodic attention based on the frequency-domain encoding. However, we find that the periodicity is hindered by the spectral damage caused by: 1) linear layers and activation functions outside attention; 2) inadequately-trained frequency components within attention (See Fig 2 ). This explains why RoPE fails to achieve length generalization without assistance from other methods. Building on our observations above, we propose Fourier Position Embedding (FoPE) to further improve the attention’s periodic extension for better length generalization. Compared to RoPE, FoPE introduces two main improvements: 1) While RoPE treats each dimension as a single-frequency function, FoPE models each dimension as a Fourier Series , consisting of a dominate frequency component and several harmonic components. This approach better mirrors the actual spectrum in LMs and helps attention separate information across different wavelengths, mitigating the negative effects of Spectral Damage. 2) FoPE clips inadequately trained frequency components that is harmful to length generalization. To keep the passing of long wavelength information, we substitute these components with zero, as the zero-frequency component corresponds to the longest wavelength. We summarize our contribution as follows: 1. Based on DSP, we provide frequency-domain analysis to reveal the negative influence from nearly all parts from LMs. We find that the length generalization is hindered by the Spectrum Damage arised from: 1) linear layers and activation functions; 2) undertrained frequency components. 2. We propose FoPE to improve attention’s robustness on the Spectrum Damage. FoPE construct Fourier Series to extract multi-frequency information in each dimension, and clip the frequency of destructive components to zero. Thus, FoPE delivers better periodic extension of attention, thus bringing better length generalizaion. 3. We conduct experiments across several model scales and datasets. The perplexity in pre-training and the accuracy in needle-in-haystack demonstrate FoPE’s superiority over RoPE and ALiBi on length generalization. Evaluation on more complex tasks (i.e. summarization and few-shot question-answering) bring further support to our method and theoretical modeling. 2 Preliminaries 2.1 Non-Uniform Discrete Fourier Transform Given a finite sequence of \{x_{n}\}:=x_{0},x_{1},...,x_{N-1} equally-sampled from a continuous function x , Discrete Fourier Transform (DFT) converts them into equally-spaced components \{X_{m}\}:=X_{0},X_{1},...,X_{M-1} in frequency-domain, the original samples can be recovered by Inverse DFT (IDFT): X_{m}=\sum\limits_{n=0}^{N-1}x_{n}e^{-i2\pi\frac{n}{N}m},\ \ x_{n}=\frac{1}{M}\sum\limits_{m=0}^{M-1}X_{m}e^{i2\pi\frac{m}{M}n} (1) As e^{i\omega n}=\cos\omega n+i\sin\omega n is periodic in the original domain, DFT implicitly transforms the original function into a linear combination of periodic waves with frequency \omega_{m}=2\pi\frac{m}{M} . Thus, DFT is an estimation of the original function, which is lossless only if the original function exactly composes of these specific periodic components. To achieve a more precise approximation, the sampled frequencies can follow any arbitrary distribution \{\omega_{m}\}:=\omega_{0},\omega_{1},...,\omega_{M-1} , where the only constraint is \omega_{m}\in[0,2\pi) . The generalization of DFT is called Non-Uniform DFT (NUDFT) . 2.2 RoPE implicitly achieves Periodic Attention based on NUDFT Given a M -dimension query Q and key K for tokens a and b , RoPE rotates different dimensions m to different phases: \widetilde{q_{m}}(n_{a})=Q_{m}e^{i\omega_{m}n_{a}},\widetilde{k_{m}}(n_{b})=K_{m}e^{i\omega_{m}n_{b}} (2) where \omega_{m}=1/{\theta^{{}^{(2m/M)}}} and \theta is the pre-defined parameters in RoPE. Then, the attention weight h_{m}(n) in each dimension will be calculated as: \widetilde{h_{m}}(n)=\widetilde{q_{m}}(n_{a})\widetilde{k_{m}}^{*}(n_{b})=H_{m}e^{i\omega_{m}n} (3) where n=n_{a}-n_{b} and H_{m}=Q_{m}K_{m} . Finally, the overall attention weight between different tokens becomes: h(n)=\sum\limits_{m=0}^{M-1}\widetilde{h_{m}}(n)=\sum\limits_{m=0}^{M-1}H_{m}e^{i\omega_{m}n} (4) Comparing it with Eq ( 1 ), it can be observed that RoPE implicitly achieves a token-level Inverse NUDFT with frequency components \{\omega_{m}\} . Based

Read the complete text