"...
we show that sketches for Polynomial Kernel from the randomized numerical linear algebra literature can be used to approximate the polynomial attention which leads to a significantly faster attention mechanism without assuming any sparse structure for the attention matrix that has been done in many previous works.
...
we propose an efficient block-based algorithm that lets us apply the causal mask to the attention matrix without explicitly realizing the n×n attention matrix and compute the output of the polynomial attention mechanism in time linear in the context length.
...
"