Research map / Learning theory and algorithms / Matrix and tensor methods
Improved Algorithms for Kernel Matrix-Vector Multiplication Under Sparsity Assumptions
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a sum-of-entries-linear-in-n assumption on Gaussian kernel matrices from attention and an LSH-based subquadratic (about n^1.89) algorithm for approximate kernel matrix-vector multiplication with arbitrary-sign vectors.
Problem
Approximate kernel (Gaussian) matrix-vector products Kx for attention-derived asymmetric kernel matrices in subquadratic time for unrestricted vectors x in high dimensions.
Approach
Assume the total entry sum of K is linear in n (tail sum at most a constant times head sum of top-n entries), then combine vector pre-processing, LSH-based heavy-key finding, and adaptive importance-style subsampling of light keys with per-row sample counts estimated via KDE, giving an additive l2 error guarantee ||Kx-y|| <= eps||x|| that works for any x.
Key results
- Empirically the head-to-tail ratio constant c is at most 4.6 for BERT across all layers and heads (5.15 for GPT-1 and 5.39 for RoBERTa).
- Theoretical runtime is O~(d n^1.89 / eps^2) for ApproxKMV, subquadratic and handling arbitrary-sign x, improving over prior non-negative-only algorithm.
- Median ratio of n-th and 2n-th largest entries is about 20 or less for most heads, so a uniform tail bound assumption is not supported.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use ApproxKMV under the head-to-tail sparsity assumption instead of the prior LSH-based algorithm | Gaussian kernel matrix-vector multiplication for unrestricted vectors · Gaussian kernel matrices satisfying Assumption (A) | runtime exponent in n: n^{1.173+o(1)} -> n^{1.89} | Helped |
| Evaluate the head-to-tail assumption on reduced Gaussian kernel matrices from BERT attention | Reduced Gaussian kernel matrices · BERT base (uncased) on SQuAD sentences | maximum head-to-tail ratio: less than 4.6 | No clear effect |
| Evaluate the head-to-tail assumption on reduced Gaussian kernel matrices | Reduced Gaussian kernel matrices · GPT-1 on SQuAD sentences | maximum head-to-tail ratio: less than 5.15 | No clear effect |
| Evaluate the head-to-tail assumption on reduced Gaussian kernel matrices | Reduced Gaussian kernel matrices · RoBERTa on SQuAD sentences | maximum head-to-tail ratio: less than 5.39 | No clear effect |
| Use adaptive sampling budgets based on per-query empirical variance in the approximate attention implementation | KDEFormer-based normalized attention approximation · GloVe embeddings, sequence lengths 4K–16K | exact-to-approximate runtime ratio | Helped |
Surprising findings
- The stronger assumption of a small uniform bound on tail entries does not hold; the n-th and (n+1)-th largest entries have median ratio near 1.
- The prior algorithm of Alman et al. can fail to be subquadratic even for non-negative x in some error regimes, e.g., when K has a single all-ones row.
Limitations
- Algorithm relies on a structural assumption on K that is validated only empirically on a few models and SQuAD sentences.
- Runtime is n^1.89 and the empirical runtime experiment is a basic implementation built on KDEFormer.
- Assumption is stated for the reduced Gaussian kernel, and the constant c may vary for other models or data.
Experimental setup
Datasets: SQuAD
Benchmarks: SQuAD (sentences for attention matrices) GloVe embeddings (runtime experiment)
Metrics: head-to-tail ratio c median ratio of nth and 2nth largest entries wall-clock runtime ratio exact vs approximate
Baselines: Exact O(n^2 d) multiplication KDEFormer Kernel noisy power method (Alman et al.)
Builds on: locality sensitive hashing Fast Gaussian KDE (Charikar et al.-style LSH KDE) KDEFormer Kernel noisy power method
Closest papers by meaning
- Faster Kernel Matrix Algebra via Density Estimation (ICML 2021 · similarity 0.90)
- The Structural Complexity of Matrix-Vector Multiplication (NeurIPS 2025 · similarity 0.87)
- Faster Algorithms for Structured Linear and Kernel Support Vector Machines (ICLR 2025 · similarity 0.87)
- How to Capture Higher-order Correlations? Generalizing Matrix Softmax Attention to Kronecker Computation (ICLR 2024 · similarity 0.86)
- Provable Acceleration of Nesterov's Accelerated Gradient for Asymmetric Matrix Factorization and Linear Neural Networks (NeurIPS 2024 · similarity 0.85)
- Metric Transforms and Low Rank Representations of Kernels for Fast Attention (NeurIPS 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.