Nyströmformer: A Nyström-Based Algorithm for Approximating Self-Attention

2021/02/07 by Yunyang Xiong, Xiong, Yunyang, Zhanpeng Zeng +12 · 1 voice · 43 citations
Computer Science · Engineering · #Ferroelectric and Negative Capacitance Devices #Natural Language Processing Techniques #Topic Modeling #cs.CL #cs.LG

paper · pdf · doi:10.48550/arxiv.2102.03902

openalex publication_date 2021/02/07 · openalex created_date 2021/02/15 · openalex updated_date 2026/07/28

Abstract

Transformers have emerged as a powerful tool for a broad range of natural language processing tasks. A key component that drives the impressive performance of Transformers is the self-attention mechanism that encodes the influence or dependence of other tokens on each specific token. While beneficial, the quadratic complexity of self-attention on the input sequence length has limited its application to longer sequences -- a topic being actively studied in the community. To address this limitation, we propose Nyströmformer -- a model that exhibits favorable scalability as a function of sequence length. Our idea is based on adapting the Nyström method to approximate standard self-attention with O(n) complexity. The scalability of Nyströmformer enables application to longer sequences with thousands of tokens. We perform evaluations on multiple downstream tasks on the GLUE benchmark and IMDB reviews with standard sequence length, and find that our Nyströmformer performs comparably, or in a few cases, even slightly better, than standard self-attention. On longer sequence tasks in the Long Range Arena (LRA) benchmark, Nyströmformer performs favorably relative to other efficient self-attention methods. Our code is available at https://github.com/mlpen/Nystromformer.

Citations

• Training Deep Nets with Sublinear Memory Cost
• Large Memory Layers with Product Keys
• LLM-Supported Manufacturing Mapping Generation
• Reformer: The Efficient Transformer
• ELECTRA: Pre-training Text Encoders as Discriminators Rather Than Generators
• ALBERT: A Lite BERT for Self-supervised Learning of Language Representations
• Longformer: The Long-Document Transformer
• Language Models are Few-Shot Learners
• Conv-Linformer: Boosting Linformer's Performance with Convolution in Small-Scale Settings
• Rethinking Attention with Performers
• Long Range Arena: A Benchmark for Efficient Transformers
• Learning Multiple Layers of Features from Tiny Images
• LambdaNetworks: Modeling Long-Range Interactions Without Attention

Cited by

• ELSAA: Efficient Low-Rank and Sparse Attention Approximation for Training Transformers
• Norm or Direction? Decoding Vision Mambas for High-Resolution Vision
• Spectral-LSH: Sub-Quadratic Prompt Compression via Krylov-Projected Locality-Sensitive Hashing
• Attention to Mamba: A Recipe for Cross-Architecture Distillation
• Extending the Context of Pretrained LLMs by Dropping Their Positional Embeddings
• Log-Linear Attention
• Leaner Transformers: More Heads, Less Depth
• MobileWan: Closing the Quality Gap for Mobile Video Diffusion
• A Coulomb Particle Model for Learning Kernel Attention in Transformers
• WSD-MIL: Window Scale Decay Multiple Instance Learning for Whole Slide Image Classification
• Dynamic Rank Reinforcement Learning for Adaptive Low-Rank Multi-Head Self Attention in Large Language Models
• LLM-driven Knowledge Enhancement for Multimodal Cancer Survival Prediction
• LUNA: Linear Universal Neural Attention with Generalization Guarantees
• A Mathematical Theory of Top-k Sparse Attention via Total Variation Distance
• Block Sparse Flash Attention
• ViT³: Unlocking Test-Time Training in Vision
• Structural Prognostic Event Modeling for Multimodal Cancer Survival Analysis
• DeepCoT: Deep Continual Transformers for Real-Time Inference on Data Streams
• UniFormer: Unified and Efficient Transformer for Reasoning Across General and Custom Computing
• Diagnose Like A REAL Pathologist: An Uncertainty-Focused Approach for Trustworthy Multi-Resolution Multiple Instance Learning
• DiScoFormer: Plug-In Density and Score Estimation with Transformers
• Linear Differential Vision Transformer: Learning Visual Contrasts via Pairwise Differentials
• Transformers from Compressed Representations
• On Structured State-Space Duality
• KVLinC : KV Cache Quantization with Hadamard Rotation and Linear Correction
• Exact Causal Attention with 10% Fewer Operations
• RACE Attention: A Strictly Linear-Time Attention Layer for Training on Outrageously Large Contexts
• Understanding Transformers for Time Series: Rank Structure, Flow-of-ranks, and Compressibility
• LOTFormer: Doubly-Stochastic Linear Attention via Low-Rank Optimal Transport
• PDE-Transformer: A Continuous Dynamical Systems Approach to Sequence Modeling
• Decoupled-Value Attention for Prior-Data Fitted Networks: GP Inference for Physical Equations
• Pixelated Butterfly: Simple and Efficient Sparse training for Neural Network Models
• Towards Interpretable and Efficient Attention: Compressing All by Contracting a Few
• Multipole Semantic Attention: A Fast Approximation of Softmax Attention for Pretraining
• SAC-MIL: Spatial-Aware Correlated Multiple Instance Learning for Histopathology Whole Slide Image Classification
• FLARE: Fast Low-rank Attention Routing Engine
• STAMP: Multi-pattern Attention-aware Multiple Instance Learning for STAS Diagnosis in Multi-center Histopathology Images
• PRELUDE: A Benchmark Designed to Require Global Comprehension and Reasoning over Long Contexts
• GFocal: A Global-Focal Neural Operator for Solving PDEs on Arbitrary Geometries
• Welcome New Doctor: Continual Learning with Expert Consultation and Autoregressive Inference for Whole Slide Image Analysis
• Long-Range Transformers for Dynamic Spatiotemporal Forecasting
• Improved Algorithms for Kernel Matrix-Vector Multiplication Under Sparsity Assumptions
• EcoTransformer: Attention without Multiplication

Discussions

• Nyströmformer: A Nyström-Based Algorithm for Approximating Self-Attention [hn, 85 points, 2 comments]

Related

• Conv-Linformer: Boosting Linformer's Performance with Convolution in Small-Scale Settings
• Revisiting Linformer with a modified self-attention with linear complexity
• PolySketchFormer: Fast Transformers via Sketching Polynomial Kernels
• Dense Local Dependencies Induce Attention-Logit Explosion and Training Instability During Long-Sequence Transformer Training
• Sparser is Faster and Less is More: Efficient Sparse Attention for Long-Range Transformers