  We introduce Transformer-VQ, a decoder-only transformer computing
softmax-based dense self-attention in linear time. Transformer-VQ's efficient
attention is enabled by vector-quantized keys and a novel caching mechanism. In
our large-scale experiments, Transformer-VQ is shown highly competitive in
quality, obtaining 0.99 bpb on Enwik8, 26.6 ppl on PG-19, and 3.16 bpb on
ImageNet64. In addition, the optimized implementation of Transformer-VQ is over
3x faster than a comparable quadratic-time transformer at sequence length 8k,
is over 12x faster at 32k, and can scale to 131k with similar throughput. Code
available: \url{https://github.com/transformer-vq/transformer_vq}
