  Self-attention, as the key block of transformers, is a powerful mechanism for
extracting features from the inputs. In essence, what self-attention does is to
infer the pairwise relations between the elements of the inputs, and modify the
inputs by propagating information between input pairs. As a result, it maps
inputs to N outputs and casts a quadratic $O(N^2)$ memory and time complexity.
We propose centroid attention, a generalization of self-attention that maps N
inputs to M outputs $(M\leq N)$, such that the key information in the inputs
are summarized in the smaller number of outputs (called centroids). We design
centroid attention by amortizing the gradient descent update rule of a
clustering objective function on the inputs, which reveals an underlying
connection between attention and clustering. By compressing the inputs to the
centroids, we extract the key information useful for prediction and also reduce
the computation of the attention module and the subsequent layers. We apply our
method to various applications, including abstractive text summarization, 3D
vision, and image processing. Empirical results demonstrate the effectiveness
of our method over the standard transformers.
