How to Capture Higher-order Correlations? Generalizing Matrix Softmax
  Attention to Kronecker Computation
Josh Alman Zhao Song
In the classical transformer attention scheme, we are given three $n \times
d$ size matrices $Q, K, V$ (the query, key, and value tokens), and the goal is
to compute a new $n \times d$ size matrix $D^{-1} \exp(QK^\top) V$ where $D =
\mathrm{diag}( \exp(QK^\top) {\bf 1}_n )$. In this work, we study a
generalization of attention which captures triple-wise correlations. This
generalization is able to solve problems about detecting triple-wise
connections that were shown to be impossible for transformers. The potential
downside of this generalization is that it appears as though computations are
even more difficult, since the straightforward algorithm requires cubic time in
$n$. However, we show that in the bounded-entry setting (which arises in
practice, and which is well-studied in both theory and practice), there is
actually a near-linear time algorithm. More precisely, we show that bounded
entries are both necessary and sufficient for quickly performing generalized
computations:
  $\bullet$ On the positive side, if all entries of the input matrices are
bounded above by $o(\sqrt[3]{\log n})$ then we show how to approximate the
``tensor-type'' attention matrix in $n^{1+o(1)}$ time.
  $\bullet$ On the negative side, we show that if the entries of the input
matrices may be as large as $\Omega(\sqrt[3]{\log n})$, then there is no
algorithm that runs faster than $n^{3-o(1)}$ (assuming the Strong Exponential
Time Hypothesis from fine-grained complexity theory).
  We also show that our construction, algorithms, and lower bounds naturally
generalize to higher-order tensors and correlations. Interestingly, the higher
the order of the tensors, the lower the bound on the entries needs to be for an
efficient algorithm. Our results thus yield a natural tradeoff between the
boundedness of the entries, and order of the tensor one may use for more
expressive, efficient attention computation.