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

2021/02/07 by Yunyang Xiong, Xiong, Yunyang, Zhanpeng Zeng +12 · 1 voice · 72 citations
Computer Science · Engineering · Mathematics · #Algorithm #Benchmark (surveying) #Code (set theory) #Computer science #Ferroelectric and Negative Capacitance Devices #Mathematics #Natural Language Processing Techniques #Quadratic equation #Range (aeronautics) #Scalability #Security token #Sequence (biology) #Topic Modeling #cs.CL #cs.LG

paper · pdf · doi:10.48550/arxiv.2102.03902

published in arXiv (Cornell University) (Cornell University) · AAAI 2021; Code and supplement available at https://github.com/mlpen/Nystromformer

openalex publication_date 2021/02/07 · openalex created_date 2021/02/15 · arxiv created 2021/03/31 · arxiv updated 2021/04/02 · 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
• Linformer: Self-Attention with Linear Complexity
• 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
• Where to Add PDE Diffusion in Transformers
• 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
• Artifacts and Attention Sinks: Structured Approximations for Efficient Vision Transformers
• Long-Range Transformers for Dynamic Spatiotemporal Forecasting
• Improved Algorithms for Kernel Matrix-Vector Multiplication Under Sparsity Assumptions
• EcoTransformer: Attention without Multiplication
• Block-based Symmetric Pruning and Fusion for Efficient Vision Transformers
• Geometric Transformers for Protein Interface Contact Prediction
• Plug-and-play linear attention with provable guarantees for training-free image restoration
• Scaling Attention to Very Long Sequences in Linear Time with Wavelet-Enhanced Random Spectral Attention (WERSA)
• Single Domain Generalization for Multimodal Cross-Cancer Prognosis via Dirac Rebalancer and Distribution Entanglement
• Estimating Interventional Distributions with Uncertain Causal Graphs through Meta-Learning
• TransGAN: Two Pure Transformers Can Make One Strong GAN, and That Can Scale Up
• Continual Multiple Instance Learning with Enhanced Localization for Histopathological Whole Slide Image Analysis
• NLP4Neuro: Sequence-to-sequence learning for neural population decoding
• A unified framework for establishing the universal approximation of transformer-type architectures
• FMMformer: Efficient and Flexible Transformer via Decomposed Near-field and Far-field Attention
• Focus Your Attention: Towards Data-Intuitive Lightweight Vision Transformers
• GeistBERT: Breathing Life into German NLP
• Revisiting Transformers with Insights from Image Filtering and Boosting
• UFO-ViT: High Performance Linear Vision Transformer without Softmax
• What exactly did the Transformer learn from our physics data?
• TuneComp: Joint Fine-tuning and Compression for Large Foundation Models
• MonarchAttention: Zero-Shot Conversion to Fast, Hardware-Aware Structured Attention
• Kernel PCA for Out-of-Distribution Detection: Non-Linear Kernel Selections and Approximations
• Enhancing Transformers Through Conditioned Embedded Tokens
• SchoenbAt: Rethinking Attention with Polynomial basis
• Advancing Multiple Instance Learning with Continual Learning for Whole Slide Imaging
• Learning Advanced Self-Attention for Linear Transformers in the Singular Value Domain
• OLinear: A Linear Model for Time Series Forecasting in Orthogonally Transformed Domain
• Graph Laplacian Wavelet Transformer via Learnable Spectral Decomposition
• Trading Complexity for Expressivity Through Structured Generalized Linear Token Mixing
• HMPE:HeatMap Embedding for Efficient Transformer-Based Small Object Detection
• A Review of YOLOv12: Attention-Based Enhancements vs. Previous Versions

Discussions

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

Related

• Linformer: Self-Attention with Linear Complexity
• 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