  Vision Transformer (ViT) has emerged as a competitive alternative to
convolutional neural networks for various computer vision applications.
Specifically, ViT multi-head attention layers make it possible to embed
information globally across the overall image. Nevertheless, computing and
storing such attention matrices incurs a quadratic cost dependency on the
number of patches, limiting its achievable efficiency and scalability and
prohibiting more extensive real-world ViT applications on resource-constrained
devices. Sparse attention has been shown to be a promising direction for
improving hardware acceleration efficiency for NLP models. However, a
systematic counterpart approach is still missing for accelerating ViT models.
To close the above gap, we propose a first-of-its-kind algorithm-hardware
codesigned framework, dubbed ViTALiTy, for boosting the inference efficiency of
ViTs. Unlike sparsity-based Transformer accelerators for NLP, ViTALiTy unifies
both low-rank and sparse components of the attention in ViTs. At the algorithm
level, we approximate the dot-product softmax operation via first-order Taylor
attention with row-mean centering as the low-rank component to linearize the
cost of attention blocks and further boost the accuracy by incorporating a
sparsity-based regularization. At the hardware level, we develop a dedicated
accelerator to better leverage the resulting workload and pipeline from
ViTALiTy's linear Taylor attention which requires the execution of only the
low-rank component, to further boost the hardware efficiency. Extensive
experiments and ablation studies validate that ViTALiTy offers boosted
end-to-end efficiency (e.g., $3\times$ faster and $3\times$ energy-efficient)
under comparable accuracy, with respect to the state-of-the-art solution.
