This admits the decomposition of dot-then-exponential, which enables the reordering of products and reduces the time and memory complexities to linear. When constructing random feature samples \(\omega \)  to be exact orthogonal, the softmax attention can be accurately approximated by having exponentially small and sharper bounds on regions where the attention values after softmax are small [1]}.
