Proxyformer: Nyström-Based Linear Transformer with Trainable Proxy Tokens

Sangho Lee, Hayun Lee, Dongkun ShinAAAI 2024 · DOI

Abstract

Standard Transformers suffer from quadratic computational complexity, limiting their application to long sequences. While Nyström-based methods offer linear complexity by sampling landmarks, they often introduce redundancy and computational overhead from matrix inversion. We present Proxyformer, which replaces sampled landmarks with trainable "proxy tokens." By enforcing orthogonality through contrastive learning and ensuring context-awareness via an injection module, Proxyformer achieves state-of-the-art performance on the Long Range Arena benchmark with significantly reduced memory and time costs.

Introduction: The Quadratic Bottleneck

The self-attention mechanism is the core of the Transformer's success but also its primary limitation. As input sequence length ($n$) increases, the $O(n^2)$ cost makes tasks like processing high-resolution images or long documents computationally prohibitive. Efficient Transformers, such as the Nyströmformer, attempt to approximate the attention matrix using a subset of "landmarks." However, these models face two major hurdles: the redundancy of sampled landmarks and the latency introduced by calculating pseudo-inverse matrices.

The Proxyformer Architecture

Proxyformer addresses these issues by moving from sampling to learning. Instead of selecting landmarks from the input at runtime, it utilizes a set of $m$ trainable parameters known as proxy tokens.

Trainable Proxy Tokens and Contrastive Learning

These proxy tokens act as a global "neural memory," learning optimal representations across the entire dataset. To prevent redundancy, a contrastive loss is applied to ensure the tokens remain nearly orthogonal in vector space. This mathematical property allows the model to treat the landmark matrix as an identity matrix, effectively bypassing the expensive pseudo-inverse calculation required by traditional Nyström-based models.

The ProxyAttention module architecture. It illustrates how input tokens (X) and proxy tokens (P) interact through decomposed attention matrices (K1 and K2) to produce context-aware outputs.

Input Injection and Decomposed Dropout

To ensure the static proxy tokens remain sensitive to specific input contexts, an Input Injection Module is employed in the initial layer. This module uses cross-attention to "inject" information from the input sequence into the proxy tokens. Furthermore, the authors introduced Decomposed Dropout, a specialized regularization technique designed for the smaller, decomposed matrices used in linear attention.

Experimental Results

The model was rigorously tested on the Long Range Arena (LRA) benchmark, which includes tasks like ListOps, character-level text classification, and image pathfinding with sequences up to 4,000 tokens.

Performance comparison on the LRA benchmark. Proxyformer (red) occupies the top-right corner, indicating superior accuracy and throughput compared to models like BigBird, Performer, and the standard Transformer.

Key Findings

  • Superior Accuracy: Proxyformer achieved an average LRA score of 59.43, surpassing both the standard Transformer (58.77) and the Nyströmformer (58.63).
  • Efficiency Gains: The model reduced memory usage by up to 92% for 4K sequences and achieved a 3.8x throughput increase over the standard Transformer at high sequence lengths.
  • Ablation Studies: Removing the contrastive loss led to redundant tokens, while omitting the injection module significantly degraded performance on context-sensitive tasks, validating the core design choices.

Conclusion

Proxyformer demonstrates that learning landmarks is more effective than sampling them. By combining trainable proxy tokens with contrastive orthogonality, the model achieves a rare balance of high accuracy and linear efficiency. Future work will focus on scaling Proxyformer to larger architectures like BERT and Vision Transformers to test its limits in massive-scale pre-training.

Summary updated

BibTeX
@inproceedings{lee2024proxyformer,
  author = {Sangho Lee and Hayun Lee and Dongkun Shin},
  title = {{Proxyformer: Nyström-Based Linear Transformer with Trainable Proxy Tokens}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  doi = {10.1609/aaai.v38i12.29244},
}
Figure