Eigen Analysis of Self-Attention and its Reconstruction from Partial
  Computation
  State-of-the-art transformer models use pairwise dot-product based
self-attention, which comes at a computational cost quadratic in the input
sequence length. In this paper, we investigate the global structure of
attention scores computed using this dot product mechanism on a typical
distribution of inputs, and study the principal components of their variation.
Through eigen analysis of full attention score matrices, as well as of their
individual rows, we find that most of the variation among attention scores lie
in a low-dimensional eigenspace. Moreover, we find significant overlap between
these eigenspaces for different layers and even different transformer models.
Based on this, we propose to compute scores only for a partial subset of token
pairs, and use them to estimate scores for the remaining pairs. Beyond
investigating the accuracy of reconstructing attention scores themselves, we
investigate training transformer models that employ these approximations, and
analyze the effect on overall accuracy. Our analysis and the proposed method
provide insights into how to balance the benefits of exact pair-wise attention
and its significant computational expense.
