LeaPformer: Enabling Linear Transformers for Autoregressive and Simultaneous Tasks via Learned Proportions

Victor Agostinelli Iii, Sanghyun Hong, Lizhong Chen

Introduction

Standard Transformer architectures have revolutionized natural language processing but are constrained by their quadratic computational complexity. As input sequences grow, the cost of computing self-attention increases exponentially, making long-context processing and real-time applications computationally expensive. While "Linear Transformers" have been proposed to approximate the attention mechanism in linear time, they often suffer from a significant performance gap compared to their quadratic counterparts.

To bridge this gap, researchers previously introduced position-based re-weighting functions (such as those in cosFormer) to emphasize local context. However, these functions typically rely on the total sequence length ($N$) to calculate relative positions (e.g., $i/N$). This dependency creates a fundamental bottleneck: the model cannot function in environments where the total length is unknown, such as autoregressive generation or simultaneous streaming tasks. LeaPformer addresses this limitation by introducing Learned Proportions (LeaP), a mechanism that allows linear transformers to dynamically determine token importance without prior knowledge of the sequence length.

The Limitation of Static Re-weighting

In many linear attention variants, re-weighting is used to restore the "locality bias" inherent in standard Softmax attention. By weighting nearby tokens more heavily, models can better capture local dependencies. However, current methods are often "static" and "global." They require the total sequence length to normalize positions, which makes them unsuitable for:

  1. Autoregressive Tasks: In text generation, the model produces tokens one by one and does not know the final length of the sequence.
  2. Simultaneous Tasks: In live speech translation, the model must process and translate segments of audio before the speaker has finished their sentence.

Furthermore, static re-weighting is often hard-coded to favor local tokens, which can be detrimental for languages with long-range dependencies, such as Subject-Object-Verb (SOV) languages where critical information (like a verb) may appear at the very end of a long string.

The LeaPformer Architecture

LeaPformer replaces fixed, length-dependent position indices with a dynamic LeaP module. This module is a lightweight, two-layer feed-forward network that predicts a token's "proportion"—a value between 0 and 1—based solely on the token's own vector representation.

Key Innovations

  • Content-Aware Positioning: Instead of assuming a token's importance based on its index, LeaPformer learns to map a token's meaning to its relative position. This allows the model to "leap" across sequences to find relevant information, regardless of whether it is local or distant.
  • Sequence Length Independence: Because the proportion is derived from the token's content rather than a fixed ratio of $i/N$, the model can operate in streaming and generative modes where the total $N$ is unknown.
  • Efficiency and Scalability: The LeaP module is designed to be extremely efficient, adding only 0.2% to 1.5% to the total parameter count. The researchers also found that sharing a single LeaP module across all attention heads maintains performance while significantly reducing memory overhead.

Experimental Evaluation

The authors evaluated LeaPformer across three distinct benchmarks to test its versatility and efficiency:

  1. Long-Range Arena (LRA): This benchmark tests the model's ability to handle long sequences across tasks like text classification, image processing, and pathfinding. LeaPformer achieved the highest "Relative Composite Performance," providing the best balance between accuracy and throughput among efficient variants like Performer, Linformer, and Skyformer.
  2. Language Modeling (Wikitext-103): In autoregressive generation, LeaPformer achieved a perplexity of 24.04, the lowest among all tested efficient attention mechanisms, surpassing the previous state-of-the-art, cosFormer.
  3. Simultaneous Speech-to-Text Translation: Testing on MuST-C (English-German) and CoVoST 2 (French-English), LeaPformer became the first position-based re-weighting linear model to succeed in a streaming environment. It performed within 0.23–0.26 BLEU points of the standard Softmax attention while maintaining linear complexity.

Discussion and Insights

A significant finding of the study is LeaPformer's ability to handle complex linguistic structures. By visualizing attention heatmaps, the authors demonstrated that LeaPformer can learn non-diagonal attention patterns. This is particularly useful for SOV languages, where the model must maintain a memory of the subject and object while waiting for the verb at the end of the sequence. Static models that force a local bias often fail in these scenarios, whereas LeaPformer's learned proportions allow it to adapt its focus dynamically.

Conclusion and Future Work

LeaPformer represents a significant step forward for efficient transformers, proving that linear-time models can excel in generative and streaming tasks without sacrificing the benefits of position-based re-weighting. While the model shows slight weaknesses in extremely sparse spatial tasks like the LRA "Pathfinder," its overall performance across language and speech tasks is robust.

Future research may focus on scaling LeaPformer to massive Large Language Models (LLMs) with billions of parameters and exploring even more compressed architectures for the LeaP module to further reduce the minimal parameter overhead.

Summary updated

Abstract

A promising approach to preserving model performance in linearized transformers is to employ position-based re-weighting functions. However, state-of-the-art re-weighting functions rely heavily on target sequence lengths, making it difficult or impossible to apply them to autoregressive and simultaneous tasks, where the target and sometimes even the input sequence length are unknown. To address this issue, we propose Learned Proportions (LeaP) and LeaPformers. Our contribution is built on two major components. First, we generalize the dependence on explicit positional representations and sequence lengths into dependence on sequence proportions for re-weighting. Second, we replace static positional representations with dynamic proportions derived via a compact module, enabling more flexible attention concentration patterns. We evaluate LeaPformer against eight representative efficient transformers on the Long-Range Arena benchmark, where we show that LeaPformer achieves the best quality-throughput trade-off, as well as apply LeaPformer to Wikitext-103b autoregressive language modeling and simultaneous speech-to-text translation for two language pairs, achieving competitive results in both tasks.
BibTeX
@inproceedings{iii2024leapformer,
  author = {Victor Agostinelli III and Sanghyun Hong and Lizhong Chen},
  title = {{LeaPformer: Enabling Linear Transformers for Autoregressive and Simultaneous Tasks via Learned Proportions}},
  booktitle = {International Conference on Machine Learning},
  year = {2024},
  url = {https://openreview.net/forum?id=XhH1OKLANY},
}
Figure