ClusterAttention: A training-free speedup of bidirectional attention
cs.LG, cs.CV
Submitted: 2026-08-27
Updated: 2026-09-29
Comments: 13 pages, 2 figures, plus appendix. September update: Faster compensation kernel, fixed TabPFN-3 preprocessing and autocast scope (giving better accuracy and larger speedup), corrections in the error analysis and complexities, expanded comparison with similar work, revised the writing
Code: https://github.com/SpoketKasper/ClusterAttention
License: http://creativecommons.org/licenses/by/4.0/
The gist: We introduce ClusterAttention, a general training-free speedup of bidirectional attention at large token counts.
Terminology
Abstract
We introduce ClusterAttention, a general training-free speedup of bidirectional attention at large token counts. We point out two common assumptions in contemporary training-free methods; attention sparsity, and context that can be leveraged, such as structure in the input or multiple similar forward passes, and show when they fail. Our proposed method utilizes a fast attention-aware recursive clustering method, and compensation of excluded clusters through their mean. The clustering method gives power-of-two cluster sizes, allowing block-sparse attention to match dense attention in GPU throughput. On TabPFN-3 arXiv:2605.13986, a model where none of the assumptions hold, ClusterAttention is to our knowledge the first method to provide a substantial speedup over the default attention, while consistently keeping over 99% of its accuracy. On the largest dataset from the TALENT benchmark suite, it makes processing of the training dataset close to 8x faster at nearly 11x attention speedup. ClusterAttention is also competitive with domain-specific methods, while avoiding any of the domain-specific engineering. On video-generation with Wan 2.1-T2V-14B arXiv:2503.20314 it produces output closer to dense attention at a larger speedup (1.8x vs 1.4x) than SVOO arXiv:2603.18636, a leading method in this domain, with both evaluated without offline calibration.
Sources
- TabPFN-3: Technical Report
- Wan: Open and Advanced Large-Scale Video Generative Models
- Attention Sparsity is Input-Stable: Training-Free Sparse Attention for Video Generation via Offline Sparsity Profiling and Online QK Co-Clustering
- UltraGen: High-Resolution Video Generation with Hierarchical Attention
- HyenaDNA: Long-Range Genomic Sequence Modeling at Single Nucleotide Resolution
- DINOv2: Learning Robust Visual Features without Supervision
- SpargeAttention: Accurate and Training-free Sparse Attention Accelerating Any Model Inference
- Fast Transformers with Clustered Attention
- AdaCluster: Adaptive Query-Key Clustering for Sparse Attention in Video Generation
- Quest: Query-Aware Sparsity for Efficient Long-Context LLM Inference
- A Novel Benchmark for Few-Shot Semantic Segmentation in the Era of Foundation Models
- SageAttention2: Efficient Attention with Thorough Outlier Smoothing and Per-thread INT4 Quantization
- TALENT: A Tabular Analytics and Learning Toolbox
- The Unreasonable Effectiveness of Deep Features as a Perceptual Metric
- DeepSeek-V3.2: Pushing the Frontier of Open Large Language Models
- Multipole Semantic Attention: A Fast Approximation of Softmax Attention for Pretraining
- On the Properties of the Softmax Function with Application in Game Theory and Reinforcement Learning
Related papers
- Polynomial-Augmented Neural Networks (PANNs) with Weak Orthogonality Constraints for Enhanced Function and PDE Approximation
- AIRL-S: Unifying Reinforcement Learning and Search-Based Test-Time Scaling via Adversarial Inverse Reinforcement Learning
- Transformers as Bayesian In-Context Experimenters: Smoothness-Adaptive Efficient ATE Estimation
- Convergence issues in Relational Concept Analysis based on AOC-posets
- Beliefs Beyond Posteriors: The Predictive Cost of ELBO Binding
- Understanding Diffusion Models via Ratio-Based Function Approximation with SignReLU Networks