Treeformer: Dense Gradient Trees for Efficient Attention Computation. (arXiv:2208.09015v1 [cs.CL])

Standard inference and training with transformer based architectures scale
quadratically with input sequence length. This is prohibitively large for a
variety of applications especially in web-page translation, query-answering
etc. Consequently, several approaches have been developed recently to speedup
attention computation by enforcing different attention structures such as
sparsity, low-rank, approximating attention using kernels. In this work, we
view attention computation as that of nearest neighbor retrieval, and use
decision tree based hierarchical navigation to reduce the retrieval cost per
query …

arxiv attention computation gradient trees