Improved Algorithms for Kernel Matrix-Vector Multiplication Under Sparsity Assumptions

2025/07/31 by Piotr Indyk, Indyk, Piotr, Michael Kapralov +5 · 1 citation
Engineering · Computer Science · Neuroscience · #Sparse and Compressive Sensing Techniques #Medical Image Segmentation Techniques #Brain Tumor Detection and Classification

paper · pdf · doi:10.48550/arxiv.2507.23539

Abstract

Motivated by the problem of fast processing of attention matrices, we study fast algorithms for computing matrix-vector products for asymmetric Gaussian Kernel matrices K∈ ℝ^{n× n}. K's columns are indexed by a set of n keys k₁,k₂…, k_n∈ ℝ^d, rows by a set of n queries q₁,q₂,…,q_n∈ ℝ^d , and its i,j entry is K_ij = e^{-‖q_i-k_j‖₂2/2σ2} for some bandwidth parameter σ>0. Given a vector x∈ ℝⁿ and error parameter ε>0, our task is to output a y∈ ℝⁿ such that ‖Kx-y‖₂≤ ε‖x‖₂ in time subquadratic in n and linear in d. Our algorithms rely on the following modelling assumption about the matrices K: the sum of the entries of K scales linearly in n, as opposed to worst case quadratic growth. We validate this assumption experimentally, for Gaussian kernel matrices encountered in various settings such as fast attention computation in LLMs. We obtain the first subquadratic-time algorithm that works under this assumption, for unrestricted vectors.

Citations

• HyperAttention: Long-context Attention in Near-Linear Time
• Fast Attention Requires Bounded Entries
• KDEformer: Accelerating Transformers via Kernel Density Estimation
• On The Computational Complexity of Self-Attention
• Scatterbrain: Unifying Sparse and Low-rank Attention Approximation
• DEANN: Speeding up Kernel-Density Estimation using Approximate Nearest Neighbor Search
• Faster Kernel Matrix Algebra via Density Estimation
• Nyströmformer: A Nyström-Based Algorithm for Approximating Self-Attention
• Kernel Density Estimation through Density Constrained Near Neighbor Search
• Rethinking Attention with Performers
• Big Bird: Transformers for Longer Sequences
• Conv-Linformer: Boosting Linformer's Performance with Convolution in Small-Scale Settings
• Longformer: The Long-Document Transformer
• Reformer: The Efficient Transformer
• HuggingFace's Transformers: State-of-the-art Natural Language Processing
• RoBERTa: A Robustly Optimized BERT Pretraining Approach
• Hashing-Based-Estimators for Kernel Density in High Dimensions
• Attention Is All You Need
• On the Fine-Grained Complexity of Empirical Risk Minimization: Kernel\n Methods and Neural Networks
• SQuAD: 100,000+ Questions for Machine Comprehension of Text
• BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding

Cited by

• Even Faster Kernel Matrix Linear Algebra via Density Estimation

Related

• Is Input Sparsity Time Possible for Kernel Low-Rank Approximation?
• Fast Matrix Square Roots with Applications to Gaussian Processes and Bayesian Optimization
• Leverage Score Sampling for Tensor Product Matrices in Input Sparsity Time
• Giga-scale Kernel Matrix Vector Multiplication on GPU
• Low-Bandwidth Matrix Multiplication: Faster Algorithms and More General Forms of Sparsity