
After reordering products and reusing \(\sum _{j=1}^C\phi (k_j)v_j\)  and \(\sum _{j^{\prime }=1}^C\phi (k_{j^{\prime }})\)  for each \(i\) , the time and memory complexity can be reduced to \(O(C)\)  [1]}, [2]}. Based on the kernel view, the Transformer's softmax function of \(Q^TK\)  can be approximated by kernel functions of randomized feature maps [1]}, [2]}. In particular, the kernel function in Eq.(REF ) unbiasedly approximates the exponential of the dot product in softmax attention by drawing feature vectors from a zero-mean Gaussian distribution \(\omega \sim \mathcal {N}(0, I_D)\)
\(\begin{split}\exp (q_i^Tk_j) &=\mathbb {E}_{\omega \sim \mathcal {N}(0, I_D)}[\phi (q_i)^T\phi (k_j)], \\\text{s.t.}~\phi (z) &= \exp (\omega ^Tz -\frac{\Vert z\Vert ^2}{2}),~z=q_i~\text{or}~k_j.\end{split}\) 
