RoPE Attention Can Be Trained in Almost Linear Time

Understand

The Rotary Position Embedding (RoPE) mechanism has become a powerful enhancement to the Transformer architecture, which enables models to capture token relationships when encoding positional information.

• However, the RoPE mechanisms make the computations of attention mechanisms more complicated, which makes efficient algorithms challenging.
• Earlier research introduced almost linear time algorithms for the forward computation under specific parameter settings of bounded entries (i.e., in time $n^{1+o(1)}$ where $n$ is the number of input tokens), but has not addressed backward computation.
• In this work, we develop the first almost linear time algorithm for backward computations in the RoPE-based attention under bounded entries.