Search papers, labs, and topics across Lattice.
This paper introduces ClusterAttention, a novel training-free method that accelerates bidirectional attention layers by employing a fast recursive clustering technique tailored to the geometry of keys and queries. Unlike traditional sparse attention methods that depend on input structure or require multiple forward passes, ClusterAttention achieves significant speedups鈥攔anging from two to six times on large-scale tabular data鈥攚hile maintaining over 99% accuracy compared to dense attention. Additionally, the authors derive a new error expression for sparse attention, revealing that tighter clusters can paradoxically lead to larger errors, which they mitigate through centroid compensation.
ClusterAttention achieves up to 6x speedup in bidirectional attention without sacrificing accuracy, challenging the conventional trade-off between speed and performance.
This paper introduces ClusterAttention, a general training-free speedup of bidirectional attention layers. Existing sparse attention methods either rely on structure in the input, such as order in language or spatial proximity in images, or use slow clustering processes amortized over several forward passes. ClusterAttention instead uses a fast recursive clustering method that adapts to the geometry of the keys and queries in each attention head to produce useful clusters. This method allows setting the size of the clusters arbitrarily. We utilize this by setting all clusters to be a fixed size that is a power of two, allowing the block-sparse attention to run at the same latency per query-key interaction as dense attention on GPUs. We also derive an expression for the output error in sparse attention, that explains the counterintuitive experimental finding that tight clusters can lead to larger errors than random clusters. We then derive the error when excluded clusters are compensated through their centroids, and show that this error shrinks with tighter clusters. We integrate this compensation into the method. On large-scale tabular data ClusterAttention speeds up TabPFN-3 arXiv:2605.13986 by two to six times, while retaining at least 99% of the dense accuracy. To our knowledge, it is the first training-free method that can be successfully applied in the setting of unstructured input and a single forward pass. For video generation with Wan 2.1-14B T2V arXiv:2503.20314 , ClusterAttention achieves output closer to dense attention and a larger speedup (1.8x versus 1.4x) compared to SVOO arXiv:2603.18636 , a leading method developed specifically for this domain, both run without offline calibration.
