ClusterAttention Speeds Up Bidirectional Attention Without Training

This paper introduces ClusterAttention, a novel method designed to accelerate bidirectional attention layers without requiring any additional training. Unlike existing sparse attention techniques that often rely on input structure or slow, amortized clustering processes, ClusterAttention employs a rapid recursive clustering algorithm. This algorithm dynamically adapts to the geometric properties of keys and queries within each attention head, generating effective clusters. A key innovation is setting all clusters to a fixed size that is a power of two, which enables block-sparse attention to operate with the same latency per query-key interaction as dense attention on GPUs. The research also provides a theoretical explanation for output error in sparse attention, showing how compensating for excluded clusters through their centroids can reduce error. In practical evaluations, ClusterAttention achieved a 2 to 6 times speedup on large-scale tabular data (TabPFN-3) while retaining over 99% of dense accuracy. For video generation (Wan 2.1-14B T2V), it delivered a 1.8x speedup, outperforming specialized methods, and produced outputs closer to dense attention.