Research map / Architectures and efficiency / Attention and transformers
Sparse Attention as Compact Kernel Regression
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.
Shows that sparse attention (normalized ReLU, sparsemax, alpha-entmax, top-k, and a new r-ReLUmax) is Nadaraya-Watson kernel regression with compact-support kernels, and tests these kernels in Memory Mosaics on language modeling, in-context learning, and length generalization.
Problem
Softmax attention corresponds to Gaussian kernel regression and suffers from dense weights and attention dispersion, but a kernel-theoretic account of sparse attention mechanisms was missing.
Approach
Sparse attention transformations are equivalent to Nadaraya-Watson estimators with compact-support kernels: alpha-entmax with alpha=1+1/r corresponds to rectified polynomial kernels of order r (Epanechnikov, biweight, triweight), with auto-normalization giving adaptive bandwidth; r-ReLUmax anchors support at the max-scoring key to avoid the 0/0 degeneracy of normalized ReLU.
Key results
- On RegBench at 1k training examples, Epanechnikov (sparsemax) reaches 94.2% accuracy versus 93.9% for Gaussian, with lower TVD (32.5 vs 34.1).
- On MQMTAR length generalization, Epanechnikov (sparsemax) keeps 0.31 exact match at 64x length versus 0.00 for the Transformer and 0.00 for Gaussian attention.
- Adaptive-normalization mechanisms (sparsemax, alpha-entmax) consistently outperform normalized ReLU on BabiStories validation loss across 1, 8, and 12 layer models.
Surprising findings
- Normalized ReLU (fixed bandwidth Epanechnikov) performs worst among the sparse variants on RegBench and length generalization despite being the direct Epanechnikov kernel.
- Uniform top-k kNN attention fails to extrapolate on most synthetic tasks.
Limitations
- Experiments are limited to small models (<1B parameters), so scaling benefits are untested.
- Context lengths are short (512 tokens for language modeling), so efficiency gains are not demonstrated in practice.
- Results are on Memory Mosaics and small synthetic/diagnostic benchmarks rather than standard large-scale transformer settings.
Experimental setup
Datasets: BabiStories RegBench MQMTAR Reverse Sort Simple English Wikipedia
Benchmarks: BabiStories RegBench MQMTAR Reverse Sort Simple English Wikipedia
Metrics: validation loss accuracy total variation distance exact match accuracy
Baselines: Gaussian softmax attention top-k softmax uniform kNN normalized ReLU Mamba Transformer RetNet H3 Gla S4
Builds on: Memory Mosaics alpha-entmax sparsemax AdaSplash Nadaraya-Watson estimator
Closest papers by meaning
- The Kernel Reality Check: Benchmarking and Distilling Efficient Attention at Scale (NeurIPS 2026 · similarity 0.91)
- Transformers Learn Faster with Semantic Focus (NeurIPS 2025 · similarity 0.90)
- SEA: Sparse Linear Attention with Estimated Attention Mask (ICLR 2024 · similarity 0.89)
- Attention layers provably solve single-location regression (ICLR 2025 · similarity 0.89)
- AdaSplash: Adaptive Sparse Flash Attention (ICML 2025 · similarity 0.88)
- SAS: Simple Attention Sparsification via End-to-End Optimization of Context Ranking (NeurIPS 2026 · similarity 0.88)
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.