"... we show that sketches for Polynomial Kernel from the randomized numerical linear algebra literature can be used to approximate the polynomial attention whi

"... 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. ... "