# HeatViT: Hardware-Efficient Adaptive Token Pruning for Vision Transformers

Peiyan Dong1, Mengshu Sun1, Alec Lu2, Yanyue Xie1, Kenneth Liu2, Zhenglun
Kong1,
Xin Meng1, Zhengang Li1, Xue Lin1, Zhenman Fang2, Yanzhi Wang1,3
1Northeastern University, 2Simon Fraser University, 3CoCoPIE LLC
{dong.pe, sun.meng, xie.yany, kong.zhe, li.zhen, xue.lin,
<EMAIL_ADDRESS>
{alec_lu, ksl24<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

While vision transformers (ViTs) have continuously achieved new milestones in
the field of computer vision, their sophisticated network architectures with
high computation and memory costs have impeded their deployment on resource-
limited edge devices. In this paper, we propose a hardware-efficient image-
adaptive token pruning framework called HeatViT for efficient yet accurate ViT
acceleration on embedded FPGAs. By analyzing the inherent computational
patterns in ViTs, we first design an effective attention-based multi-head
token selector, which can be progressively inserted before transformer blocks
to dynamically identify and consolidate the non-informative tokens from input
images. Moreover, we implement the token selector on hardware by adding
miniature control logic to heavily reuse existing hardware components built
for the backbone ViT. To improve the hardware efficiency, we further employ
8-bit fixed-point quantization and propose polynomial approximations with
regularization effect on quantization error for the frequently used nonlinear
functions in ViTs. Finally, we propose a latency-aware multi-stage training
strategy to determine the transformer blocks for inserting token selectors and
optimize the desired (average) pruning rates for inserted token selectors, in
order to improve both the model accuracy and inference latency on hardware.
Compared to existing ViT pruning studies, under the similar computation cost,
HeatViT can achieve 0.7%$\sim$8.9% higher accuracy; while under the similar
model accuracy, HeatViT can achieve more than 28.4%$\sim$65.3% computation
reduction, for various widely used ViTs, including DeiT-T, DeiT-S, DeiT-B, LV-
ViT-S, and LV-ViT-M, on the ImageNet dataset. Compared to the baseline
hardware accelerator, our implementations of HeatViT on the Xilinx ZCU102 FPGA
achieve $3.46\times$$\sim$$4.89\times$ speedup with a trivial resource
utilization overhead of 8%$\sim$11% more DSPs and 5%$\sim$8% more LUTs.

_Keywords- Vision Transformer; FPGA Accelerator; Hardware and Software Co-
design; Data-level Sparsity._

##  I Introduction

Transformers [2, 37] have recently made an attractive resurgence in the form
of Vision Transformers (ViTs) [11], showing strong versatility in NLP [47, 25,
3], computer vision (e.g., image classification [11], object detection [5,
65], semantic segmentation [61], image processing [7], and video understanding
[63]), and complex scenarios with multi-modal data. Furthermore, ViTs can be
used as effective backbone networks [11, 49, 19, 4] with superior
transferability to downstream tasks through minor fine-tunings. Seemingly,
ViTs and transformers have great potential to unify diverse application
domains through common architectures and tackle the reliance on scarce domain
data, ultimately addressing the two fundamental problems in deep learning: (i)
strong reliance on domain data, and (ii) constant model improvements to serve
evolving needs. ViTs and transformers are largely considered as one of the
future dominant deep learning techniques.

However, to fully unleash advantages of transformer architectures, we need to
address the following _challenges_ before ViTs and transformers become an
indispensable staple in future AI computing. (i) Although the self-attention
mechanism is a key defining feature of transformer architectures, a well-known
concern is its quadratic time and memory complexity with respect to the number
of input tokens. This hinders scalability in many settings, let alone
deployment on resource-constrained edge devices. (ii) Majority of existing
works on efficient ViT and transformer techniques followed what has been done
for Convolutional Neural Networks (CNNs) by using conventional weight pruning
[64, 10, 56, 55], quantization [60, 38, 33], and compact architecture design
[18, 42, 48, 6, 8, 16, 9, 30, 50], with limited accuracy and speed
performance. (iii) In the efforts of exploring token removal to address the
quadratic complexity, the static approaches [41, 32, 13, 44, 10] remove tokens
with a fixed ratio in an input-agnostic manner, ignoring input sample
dependent redundancy; and existing image-adaptive approaches [36, 56, 53]
simply discard non-informative tokens and do not fully explore token-level
redundancies from different attention heads. Both approaches achieve a
relatively low pruning rate (to preserve accuracy) or an undermined accuracy
(at a high pruning rate). Moreover, none of these studies support efficient
hardware implementation on edge devices. (iv) Transformer architectures tend
to use more hardware-unfriendly computations, e.g., more nonlinear operations
than CNNs, to improve accuracy. Therefore, we need to address the low hardware
efficiency issue of such computations, while enjoying the additional
optimization dimension provided by multi-head self-attention.

In this paper, we propose HeatViT, a hardware-efficient image-adaptive token
pruning framework, together with 8-bit quantization, for efficient yet
accurate ViT inference acceleration on embedded FPGA platforms. To improve
pruning rate while preserving model accuracy, we make two observations by
analyzing the computation workflow in ViTs: (i) the information redundancy in
input tokens differs among attention heads in ViTs; and (ii) non-informative
tokens identified in earlier transformer blocks may still encode important
information when propagating to later blocks. Based on these, we design an
effective token selector module that can be inserted before transformer blocks
to reduce token number (i.e., number of tokens) with negligible computational
overhead. As shown in Fig. 1, we incorporate different token-level
redundancies from multiple attention heads to be more accurate in token
scoring. Furthermore, instead of completely discarding non-informative ones,
we package them together into one informative token to preserve information
for later transformer blocks.

Figure 1: The workflow of HeatViT on DeiT-S. The proposed token selector S
conserves informative tokens conditioned on features from the previous layer.
And non-informative tokens are averaged into one package token (blue).

For hardware implementation on edge FPGA devices, we design our token selector
with linear layers, i.e., fully-connected (FC) layers, instead of
convolutional (CONV) layers, to reuse the GEMM (General Matrix Multiply)
hardware component built for the backbone ViT (i.e., without token selectors)
execution. In addition, we always concatenate the identified (and sparse)
informative tokens and the packaged informative token together to form a dense
input of tokens to avoid sparse computations on hardware. To improve the
hardware efficiency, we further apply 8-bit quantization for weights and
activations, and propose polynomial approximations for the frequently used
nonlinear functions in ViTs, including GELU [20], Softmax [17], and Sigmoid
[35]. Besides, we introduce the regularization effect on quantization error
into the design of polynomial approximations to support more ambitious
quantization. We design a proof-of-concept FPGA accelerator for ViTs based on
our proposed HeatViT. We implement the GEMM engine inspired by [14, 31] to
execute the most computation-intensive multi-head self-attention module and
feed-forward network in the backbone ViT, and the classification network in
our token selector. It is worth noting that only lightweight control logic is
added to support our adaptive token pruning by reusing the same hardware
components built for the backbone ViT execution.

To reduce inference latency on hardware while preserving model accuracy
(typically within 0.5% or 1% accuracy loss), we propose a latency-aware multi-
stage training strategy to (i) determine the transformer blocks for inserting
token selectors and (ii) optimize the desired (average) pruning rates for
these token selectors. Specifically, we insert a token selector for each
transformer block, from the last block backward to the first one, since early
blocks are more sensitive to accuracy. For each insertion, we train the
current token selector while fine-tuning other network components, to decrease
latency through increasing pruning rate of the current block until accuracy
loss exceeds a threshold. Then we further consolidate token selectors in
consecutive transformer blocks with similar pruning rates into one token
selector for a whole stage of transformer blocks. Our training strategy is
conducted as fine-tuning on pre-trained ViTs. And because we use small epoch
numbers for inserting token selectors, our training effort is roughly 90% of
that for training-from-scratch of backbone ViTs (without token selectors).

TABLE I: Comparison between representative ViT pruning methods.

Method |  Design Scheme | Method |  Design Scheme
---|---|---|---
DyViT [41] | ① | ATS [13] | ①
IA [36] | ② | PS-ViT [44] | ①
VTP [64] | ③ | Evo-ViT [53] | ②
S2ViTE [10] | ①③④ | UP-DeiT [55] | ③④

① – Static Token Pruning; ② – Adaptive Token Pruning; ③ – Head Pruning;
④ – Token Channel Pruning.

As summarized in Fig. 2, we evaluate HeatViT for multiple widely used ViT
models on the ImageNet dataset, including DeiT-tiny (DeiT-T, HeatViT-T), DeiT-
small (DeiT-S, HeatViT-S), DeiT-base (DeiT-B, HeatViT-B) [45], LV-ViT-small
(LV-ViT-S, HeatViT-LV-S), and LV-ViT-medium (LV-ViT-M, HeatViT-LV-M) [24].
These models are already well condensed and thus more challenging to prune
compared to larger ViT models. Compared to state-of-the-art ViT pruning
studies in Table I (pruning types are explained in detail in Sec II-B),
HeatViT achieves better accuracy-computation trade-offs: Under a similar
computation cost, HeatViT can achieve 0.7%$\sim$8.9% higher accuracy; while
under a similar accuracy, HeatViT can reduce the computation cost by more than
28.4%$\sim$ 65.3%. Compared to the baseline hardware accelerator (16-bit and
no token pruning), our implementations of HeatViT on the Xilinx ZCU102 FPGA
achieves $3.46\times$$\sim$$4.89\times$speedup with a trivial resource
utilization overhead of 8%$\sim$11% more DSPs and 5%$\sim$8% more LUTs.
Compared to the optimized ARM CPU and NVIDIA GPU versions on the NVIDIA Jetson
TX2 board with our token pruning, our FPGA implementations achieve
685$\times$$\sim$1695$\times$ and 2.68$\times$$\sim$3.79$\times$ more
speedups, 242.6$\times$$\sim$719.0$\times$ and 3.0$\times$$\sim$4.7$\times$
higher energy efficiency.

Our contributions are summarized as follows:

  * •

Algorithm and hardware co-design for an effective and hardware-efficient token
selector to enable efficient image-adaptive token pruning in ViTs.

  * •

A latency-aware multi-stage training strategy to learn the effective insertion
of token selectors in ViTs.

  * •

A polynomial approximation of nonlinear functions inside ViTs for more
ambitious quantization and efficient FPGA-based implementations.

  * •

An end-to-end acceleration framework, with both image-adaptive pruning and
8-bit quantization, for ViT inference on embedded FPGAs.

  * •

Experiments to demonstrate superior pruning rates and inference accuracy of
HeatViT over state-of-the-art ViT pruning studies, as well as trivial hardware
resource overhead.

Figure 2: Comparison of HeatViT with prior pruning methods: Under a similar
computation cost, HeatViT achieves 0.7%$\sim$8.9% higher accuracy; while under
a similar accuracy, HeatViT reduces the computation cost by more than
28.4%$\sim$ 65.3%. Final HeatViT models are quantized into 8-bit fixed-point
format. Figure 3: Overview of ViT

##  II Background and Related Work

###  II-A Vision Transformer

Transformers are initially proposed to handle the learning of long sequences
in NLP tasks. Dosovitskiy et al. [11] and Carion et al. [5] adapt the
transformer architecture to image classification and detection, respectively,
and achieve competitive performance against CNN counterparts with stronger
training techniques and larger-scale datasets. DeiT [45] further improves the
training pipeline with the aid of distillation, eliminating the need for
large-scale pretraining [57]. Inspired by the competitive performance and
global receptive field of transformer models, follow-up works design ViTs for
different computer vision tasks including object detection, semantic
segmentation, 3D object animation, and image retrieval.

Fig. 3 illustrates three components in ViTs: _patch embedding_ , _transformer
encoders_ , and _classification output head_. For patch embedding, an image
$\mathbf{X}\in\mathbb{R}^{H\times W\times C}$ is reshaped into a sequence of
2D patches $\mathbf{X}_{p}\in\mathbb{R}^{N\times(P^{2}\cdot C)}$, where
$(H,W)$ is original image resolution, $C$ is channel number, $(P,P)$ is the
resolution of patches, and $N=HW/P^{2}$ is the number of patches and also the
effective input sequence length (i.e., number of tokens) to transformer
encoders. Patch embeddings are obtained by mapping $\mathbf{X}_{p}$ into $D$
dimensions via a trainable linear projection
$\mathbf{E}\in\mathbb{R}^{(P^{2}\cdot C)\times D}$: $\mathbf{X}_{0}=$
$[\mathbf{X}_{class};\mathbf{X}^{1}_{p}\mathbf{E};\mathbf{X}^{2}_{p}\mathbf{E};...;\mathbf{X}^{N}_{p}\mathbf{E}]+\mathbf{E}_{pos}$,
where $D$ is the constant latent vector size throughout transformer encoders,
and $\mathbf{E}_{pos}\in\mathbb{R}^{(N+1)\times D}$ is learnable position
embeddings. A learnable embedding $\mathbf{X}_{0}^{0}=\mathbf{X}_{class}$ is
prepended in patch embeddings $\mathbf{X}_{0}$. Then $\mathbf{X}$ goes through
a stack of $L$ transformer encoders for processing. The output
$\mathbf{X}_{L}^{0}$ (class token) of the final ($L$-th) transformer encoder
is fed to a classification output head implemented by an MLP to obtain the
final result. The MLP module uses two linear layers with a Gaussian Error
Linear Unit (GELU) activation layer in between.

The $l$-th transformer encoder receives the patch embeddings
$\mathbf{X}_{l-1}$ as input. Fig. 3 illustrates a ViT encoder block,
consisting of a multi-head self-attention (MSA) module and an MLP (FFN)
module, both with LN (layer normalization) applied before input. The encoder
block operations are then:

$\displaystyle\mathbf{X^{\prime}}_{l-1}$
$\displaystyle=\text{MSA}(\text{LN}(\mathbf{X}_{l-1}))+\mathbf{X}_{l-1},$ (1)
$\displaystyle\mathbf{X}_{l}$
$\displaystyle=\text{FFN}(\text{LN}(\mathbf{X^{\prime}}_{l-1}))+\mathbf{X^{\prime}}_{l-1}.$

For $h$ heads in MSA, $\text{LN}(\mathbf{X}_{l-1})$ is split into $h$ parts.
For each head, the corresponding part in $\text{LN}(\mathbf{X}_{l-1})$ is
transferred into query $\mathbf{Q}$, key $\mathbf{K}$, and value $\mathbf{V}$
through three linear projections $W_{Q}$, $W_{K}$, and $W_{V}$, respectively.
Then self-attention function [47] in each head is performed as:

$\text{Attention}(\mathbf{Q},\mathbf{K},\mathbf{V})=\text{Softmax}(\mathbf{Q}\mathbf{K}^{T}/\sqrt{D})\mathbf{V}.$
(2)

Attention outputs from all the heads are concatenated and linearly
transformed.

###  II-B Model Pruning on ViT

State-of-the-art ViT pruning studies exploring the redundancy from three
dimensions in ViTs are summarized below.

Redundancy of the attention head. Attention head pruning [64, 10, 56, 55]
reduces weight redundancy on the transformation matrices ($W_{Q}$, $W_{K}$,
$W_{V}$) before MSA operation. Due to the parallel computing nature of the
transformer heads, these works directly prune some heads entirely and lead to
significant accuracy drop, for example, 27% GMACs reduction, but with 2.2%
accuracy drop on DeiT-T in [10]. It is an inefficient way of computation
reduction because the attention head usually contributes less than 43% of the
total computation in several ViT architectures [27].

Redundancy of the token channel. Token channel [10, 56, 55] pruning executes
feature-level pruning on the embedding of the token feature to diminish the
redundancy of the feature representation. Since this pruning type is
equivalent to structured pruning on the token embedding, i.e., removing the
same embedding dimension for different tokens, it is difficult to guarantee an
ideal pruning rate without significant accuracy deterioration.

Redundancy of the token number. Token pruning [41, 32, 36, 13, 44, 10, 53, 56]
aims at removing the non-informative input data. According to [54], the
accuracy of neural networks is more related to the object information, but not
the background information, implying the input-level redundancy. There is
often much higher redundancy along the token number dimension.

###  II-C Computational Complexity Analysis

Given an input sequence $N{\times}D$, where $N$ is the input sequence length
or the token number, and $D$ is the embedding dimension [45] of each token,
some works [36, 64] address the computational complexity of ViT as
$(12ND^{2}+2N^{2}D)$. However, $D$ represents three physical dimensions: (i)
$D_{ch}$ – channel size of a token, (ii) $h$ – number of heads, and (iii)
$D_{attn_{s}}$ – sub-channel size for one head. The channel size of the Query
($\mathbf{Q}$), Key ($\mathbf{K}$), and Value ($\mathbf{V}$) matrices is
$HD_{attn_{s}}$. As shown in Table II, the computational complexity of the ViT
can be written as
$[4ND_{ch}(hD_{attn_{s}})+2N^{2}(hD_{attn_{s}})+8ND_{ch}D_{fc}]$. Compared
with other prunable dimensions, directly pruning tokens, $N$, will contribute
to the reduction of all operations linearly or even quadratically ($N^{2}$ in
layers ② and ③), more compression benefits than other pruning types. Please
note that since token pruning is equivalent to removing information redundancy
within the image data, it can be more freely integrated into the compression
process on other model dimensions (e.g., model quantization in our case).

TABLE II: Computational complexity of one ViT block.

Layer | Module | Input Size | Computation | Output Size | #MACs
---|---|---|---|---|---
① | MSA | $N\times D_{ch}$ |  Linear Transformation | $N\times hD_{attn_{s}}$ | $ND_{ch}hD_{attn_{s}}$
② | $N\times hD_{attn_{s}}$ | $\mathbf{Q}\times\mathbf{K}^{\mathrm{T}}$ | $N\times N$ | $N^{2}hD_{attn_{s}}$
③ | $N\times N$ | $\mathbf{QK}^{\mathrm{T}}\times\mathbf{V}$ | $N\times hD_{attn_{s}}$ | $N^{2}hD_{attn_{s}}$
④ | $N\times hD_{attn_{s}}$ | Projection | $N\times D_{ch}$ | $NhD_{attn_{s}}D_{ch}$
⑤ | FFN | $N\times D_{ch}$ | FC Layer | $N\times 4D_{fc}$ | $4ND_{ch}D_{fc}$
⑥ | $N\times 4D_{fc}$ | FC Layer | $N\times D_{ch}$ | $4ND_{fc}D_{ch}$
Total MACs: $4ND_{ch}hD_{attn_{s}}+2N^{2}hD_{attn_{s}}+8ND_{ch}D_{fc}$

###  II-D Static vs. Image-Adaptive Token Pruning

There are two sub-branches in the token pruning of the ViT: static token
pruning and image-adaptive token pruning. Static token pruning [41, 32, 13,
10, 44] reduces the number of input tokens by a fixed ratio for different
images, which neglects the fact that the information of each image varies both
in the region size and location, and thus restricts the image pruning rate. In
contrast, image-adaptive token pruning [36, 56, 53] deletes redundant tokens
based on the inherent image characteristics to achieve a per-image adaptive
pruning rate. Generally, smaller pruning rates are applied for complex and
information-rich images while larger pruning rates for simple and information-
less ones. Ideally, it can achieve a larger overall pruning rate than the
static one as Fig 4. However, existing adaptive token pruning studies do not
consider the visual characteristics inside the ViT (token redundancy in ViT,
Sec III) –visual receptive field of different heads, and delete the less
informative tokens completely without the opportunity to correct evaluation
errors. Moreover, there are no more details on how to determine the location,
number, and pruning rate of the pruning evaluation module specifically. Hence,
they often lead to a limited overall pruning rate (e.g., 35% GMACs reduction
on DeiT-S [36]). Finally, none of these studies have considered the efficient
hardware implementation on edge devices to support adaptive token pruning. For
example, [36] introduces a new operation, Argsort, which is currently not
compatible with many frameworks [39].

Figure 4: Comparison between static token pruning and HeatViT image-adaptive
token pruning.

###  II-E Transformer Accelerators on FPGAs

Previous state-of-the-art FPGA accelerators on Transformer-based models [29],
[40] and [59] also leverage sparsity. However, they have three main
limitations. (i)[29] depends on block-circulant matrix-based weight
representation in order to replace the matrix-vector multiplication in FC
layers with FFT/IFFT-based processing elements. However, [29] accelerates only
the MSA part of the model and omits the FFN part (about $65\%$ computation of
the whole model). (ii) [40] utilizes the block-wise weight pruning and [59]
implements the structure pruning (row-wise or column-wise) to compress weights
to similar sizes (lower memory footprint). However, the pruning granularity of
both is coarse, resulting in severe accuracy degradation at limited
compression rates. For example, [40] shows 2% accuracy drops under the 36%
sparsity. (iii) These FPGA-based accelerators are mainly for transformers in
the Natural Language Processing (NLP) tasks, not for computer vision ones. In
addition, they all compress the model weights, which means that new
substructures or additional overhead is needed to support the specific sparse
matrix multiplication. According to our Section III analysis, the difference
in input data type will introduce a unique redundancy that motivates an
effective compression space. Experiments show that adaptive token pruning at
the data level can speed up the model inference with negligible accuracy
losses and little overhead for hardware implementations.

##  III Analysis of Token Redundancy in ViT and Overview of HeatViT

###  III-A Token Redundancy in ViT

Token redundancy viewed by different attention heads. Assuming that the final
class (CLS) token is strongly correlated with classification [62], we
visualize the information regions detected by the CLS token in different
attention heads of DeiT-T, as shown in Fig. 5. It can be seen that each head
extracts the features of the image (multi-head visual receptive area of the
image) independently and differently [36, 21, 34], indicating that the heads
contain distinct token-level redundancy. This inspires our token selector
design with multiple heads, which is elaborated in Section IV-A.

Figure 5: The information region detected by each head in DeiT-T.

Token redundancy viewed by different transformer blocks. Fig. 6 gives the
centered kernel alignment (CKA) [28] that represents the similarity between
the tokens in each transformer block and the final CLS token, showing a
tendency from weak to strong. It tells us that it is inaccurate for each
transformer block to encode or evaluate the image tokens, especially in the
front blocks. Thus, pruning rates for these front blocks should be lower to
avoid ruling the informative tokens out. This also inspires our token packager
technique to provide chances to make up for pruning mistakes (Section IV-B).

Figure 6: CKA between the final CLS token and other tokens measured after each
transformer block (2 to 11).

###  III-B Overview of HeatViT

To develop a hardware-efficient image-adaptive token pruning framework, we
first design an effective adaptive token pruning module (also known as token
selector) according to the vision redundancy in ViTs (Section IV). This module
includes an attention-based multi-head token classifier and a token packager,
as shown in Fig. 7. To improve the pruning rate and accuracy, the token
classifier incorporates different token-level redundancies in multiple heads
to more accurately classify tokens and the token packager consolidates
(instead of discarding) non-informative tokens to one informative token to
reserve information for later transformer blocks. To improve the hardware
efficiency, we choose linear layers for the token selector to reuse the GEMM
hardware component for the backbone ViT, and always concatenate the classified
sparse tokens into dense ones. Please note that it is challenging for CNN-
based architecture to implement the data-level pruning, because the kernel
size of the convolution operation is fixed so that the irregular input
features cannot be directly concatenated into dense ones to speedup the model
inference. Moreover, we deploy 8-bit fixed-point quantization to further
compress the model, and propose a polynomial approximation of nonlinear
functions inside ViTs for FPGA-based efficient implementations and regularize
the quantization errors. A proof-of-concept hardware accelerator design is
presented in Section V. To meet the target ViT inference speed on hardware
while reserving the accuracy (typically within 1% accuracy loss), one also
needs to carefully decide the number of token selectors to insert in the
backbone ViT, as well as the location and pruning rate of each token selector.
To address this challenge, in Section VI, we propose a latency-aware multi-
stage training strategy to learn all these parameters.

##  IV Adaptive Token Pruning Module

Figure 7: HeatViT overview. Left: Transformer blocks split into multiple
stages with token selectors inserted between them (One token selector includes
one token classifier and one token packager). Right: Multi-head token
classifier to identify informative tokens.

As shown in Fig. 7, the proposed adaptive token selector is based on
observations in Section III, including the attention-based multi-head token
classifier and the token packager.

###  IV-A Attention-Based Multi-Head Token Classifier

Multi-Head Token Classifier. Based on the multi-head visual receptive area of
the ViT, we propose a fine-grained structure to evaluate token scores. As
shown in Fig. 7, each head focuses on extracting different features and
respective fields of an image, demonstrating that the importance of each token
towards each head is different. Hence, our multi-head classifier generates a
score-map vector for each input token, marking the information amount of each
token in each head separately.

Let one head dimension be $d{=}D/h$. We split the input
$X{\in}\mathbb{R}^{N\times D}$ into $h$ subvectors
$\\{x_{i}\\}^{h}_{i=1}{\in}\mathbb{R}^{N\times d}$, and feed the subvectors
into an MLP network to obtain the representation of local receptive field
$E_{i}^{\mathrm{local}}$ and the representation of global receptive field
$E_{i}^{\mathrm{global}}$.

$E_{i}^{\mathrm{local}}={\rm MLP}(x_{i})\in\mathbb{R}^{N\times d/2}$ (3)
$E_{i}^{\mathrm{global}}={\rm Average}({\rm MLP}(x_{i}))\in\mathbb{R}^{1\times
d/2}$ (4)

Pushing the feature $E_{i}{=}concate(E_{i}^{local},E_{i}^{global}\times
N){\in}\mathbb{R}^{N\times d}$ into another MLP network and one Softmax
function, token score maps $\\{s_{i}\\}^{h}_{i=1}{\in}\mathbb{R}^{N\times 2}$
are produced. $s_{i}$ is the token score for attention head $i$ and
${\times}2$ represents the keep and prune probabilities respectively:

$\begin{gathered}s_{i}={\rm Softmax}({\rm MLP}(E_{i}))\in\mathbb{R}^{N\times
2}\\\ \end{gathered}$ (5)

Attention-Based Branch. Base on the attention mechanism [23], we add an
attention-based branch along the classifier backbone to synthesis the
importance of each head:

$\bar{X}=\mathrm{Concat}(\bigg{\\{}\frac{1}{d}\sum_{j=1}^{d}x_{ij}\bigg{\\}}^{h}_{i=1})\in\mathbb{R}^{N\times
h}$ (6) $A={\rm Sigmoid}({\rm MLP}(\bar{X})))\in\mathbb{R}^{N\times
h}\vspace{-0.05in}$ (7)

where $\bar{X}$ is a head-wise statistic through its channel dimension $D$. In
Eq. (7), we feed $\bar{X}$ into an MLP network with the sigmoid to obtain the
score vector $A$, evaluating the importance of each head. Then the overall
token score is calculated by the weighted average $S$ with $A$:

$\tilde{S}=\frac{\sum_{i=1}^{h}s_{i}*a_{i}}{\sum_{i=1}^{h}a_{i}}\in\mathbb{R}^{N\times
2}$ (8)

where $\tilde{S}$ is the token probability score. Then we apply the Gumbel-
Softmax for the token keep/prune decision mask:

$M={\rm GumbelSoftmax}(\tilde{S})\in\\{0,1\\}^{N}$ (9)

Since deleted image tokens cannot appear in subsequent blocks, $M$ passes on
to the following blocks and will be updated by applying $M$ $\leftarrow$
$M\odot M^{\prime}$. $M^{\prime}$ is the new mask generated in the next stage.

###  IV-B Token Packager

To solve the problem in the Sec III, we apply a token packaging step that
summarizes non-informative tokens (predicted by the classifier) into a package
token instead of completely discarding them. Assume there are $T$ (evaluated
by the classifier) non-informative tokens
$\\{\hat{x}_{t}\\}^{T}_{t=1}{\in}\mathbb{R}^{T\times D}$ along with their
token scores $\\{\tilde{s}_{t}\\}^{T}_{t=1}{\in}\mathbb{R}^{T\times 2}$, these
tokens are compressed into one token through weighted averaging:

$P=\frac{\sum_{t=1}^{T}\hat{x}_{t}*\tilde{s}_{t}[0]}{\sum_{t=1}^{T}\tilde{s}_{t}[0]}\in\mathbb{R}^{1\times
D}$ (10)

where $P$ is the package token; $\tilde{s}_{t}[0]$ is the keep score of
$\hat{x}_{t}$; $*$ is an element-wise multiplication. $P$ will continue the
subsequent calculations along with the informative ones, enabling the model to
correct scoring mistakes.

After image-adaptive removing a certain part of tokens and the token packaging
step, the sparse input matrix (all the informative tokens and package token)
will be concatenated into a new smaller-size dense matrix to complete the
computation in the following blocks, which speedup the model inference
directly. And most of the component operations (FC layer, Softmax, GELU) have
already been there in the backbone ViT blocks. Therefore, we can utilize our
unified operation-level optimization scheme of the ViT deployment on FPGA.

##  V ViT Hardware Accelerator Design with Adaptive Token Pruning

The hardware architecture of ViT accelerators in HeatViT is illustrated in
Fig. 8, including the accelerator design for pruned ViTs with token selector
and the computation flow in the General Matrix Multiply (GEMM) engine. Besides
the LayerNorm layer (less time consuming but more complex to implement on the
FPGA) that is left on the ARM CPU, all other components in HeatVit are
implemented on the FPGA.

###  V-A Challenges

To implement ViT FPGA accelerator with our dynamic token pruning, we address
the following challenges. (i) The token selector module should be implemented
with minimal hardware overhead by adding miniature control logic and reusing
existing hardware for the backbone ViT. (ii) The GEMM loop tiling should
accommodate an additional tiling dimension due to multi-head parallelism.
(iii) ViTs use more nonlinear operations than CNNs, and we need to refine
these operations for more aggressive quantization and efficient hardware
implementations without losing accuracy.

###  V-B ViT Accelerator with Dynamic Token Selection

As displayed in Fig. 8(a), the input (tokens) and weight of each ViT layer are
loaded from the off-chip DDR memory to the on-chip buffers, and processed by
the GEMM engine which we will implement motivated by [15, 31]. Outputs are
further processed with the activation function (Softmax or GELU), and then
stored from the on-chip output buffer back to the off-chip memory. Double
buffering will be applied to overlap data transfer time with computation. The
token selector for pruning consists of FC layers and GELU activations, which
also exist in the original ViTs, and thus can be managed by the same
computation engine with negligible hardware overhead (Section V-C). Note
LayerNorm is executed on the CPU.

####  V-B1 Loop Tiling in GEMM

We generalize loop tiling [58] for GEMM engine to deal with relatively large
ViT layers. The concurrency of MAC operations in matrix multiplications
requires pipelining and loop unrolling, as well as array partitioning of
buffers. Fig. 8(b) shows detailed computation flow in GEMM loop tiling for
ViTs accommodating an additional tiling dimension from multi-head mechanism.
Given a ViT layer $j$ from ①$\sim$⑥ in Table II that performs one or $h$
matrix multiplications with its $N_{j}$ tokens after pruning, we represent
input size as $N_{j}\times D_{i}$, weight matrix size as $D_{i}\times D_{o}$,
and output size as $N_{j}\times D_{o}$, where $D_{i}$ denotes $D_{ch}$,
$D_{attn}$, or $N$ in the MHSA module, and $D_{ch}$ or $4D_{fc}$ in the MLP
module. Tiling is applied to $D_{i}$ and $D_{o}$ dimensions, with tiling sizes
$T_{i}$ and $T_{o}$, respectively. For attention computations
($\mathbf{Q}\times\mathbf{K}^{\mathrm{T}}$ in ② and
$\mathbf{QK}^{\mathrm{T}}\times\mathbf{V}$ in ③), both input and output are
split into $h$ groups. A control signal is used to indicate whether current
computations are attention-related. Results from ② and ③ are kept in $h$
groups, while results from other layers are accumulated. To improve
throughput, we optimize parallelism factors including $T_{i}$, $T_{o}$, and
$T_{h}$ (an additional tiling dimension for $h$ heads). Therefore, we will
conduct comprehensive FPGA resource modeling for available computing and on-
chip memory resources.

(a) ViT hardware accelerator architecture supporting dynamic token selection.

(b) GEMM loop tiling with an additional tiling from multi-head mechanism.

Figure 8: Hardware architecture of ViT accelerator in HeatViT.

####  V-B2 Throughput and Resource Utilization Analysis

The inference throughput (FPS) of ViT inference is determined by the
parallelism factors $T_{i}$, $T_{o}$ and $T_{h}$, which are bounded by the
number of available computation (mainly DSPs) and on-chip memory (BRAMs)
resources. The inference is executed layer-by-layer, and the FPS can be
inferred through dividing the total number of clock cycles required to process
all the ViT layers with the working frequency on FPGAs. The throughput and
resource utilization analysis of ViT accelerators is similar to that of CNN
accelerators [43], except that the head dimension in ViTs needs to be
additionally considered for parallelism. Since the layers in token selectors
can be managed by the same GEMM engine as for the existing ViT layers, this
analysis also applies to token selectors.

###  V-C Token Selection Flow

Token selection contains token classification to determine informative and
non-informative tokens using GumbelSoftmax with a threshold value (usually
0.5), and token packaging to average the non-informative tokens to one that is
then consolidated into the informative tokens. The pruned token (input)
sequences with sparsity will be reorganized as dense ones, eliminating
hardware overhead for indexing. Fig. 9 describes the three steps to implement
token selection in our ViT hardware accelerator: (1) calculating the exponent
for each token $x_{i}$ and the summation $Sum$ of all these exponents; (2)
dividing each exponent by the sum and classifying the corresponding token as
informative or not according to a threshold; and (3) if the token is
informative, concatenating it to the informative token sequence, otherwise
adding it to a temporary token $Tmp$. Finally, $Tmp$ is averaged and
concatenated to the informative token sequence.

Figure 9: Token selection flow.

###  V-D Polynomial Approximation of Nonlinear Functions

ViT models contain nonlinear functions including GELU, Softmax, and Sigmoid.
(i) Some nonlinear operations inside those functions, e.g., exponential
function $\mathrm{exp}(x)$ and error function $\mathrm{erf}(x)$ consume large
amounts of computing resources when implemented with the built-in Xilinx Vitis
HLS math library [51], and thus incurring difficulty for hardware acceleration
(Table III). (ii) To apply more aggressive quantization than CNN/RNN models,
we need to add the regularization effect on quantization error to these
approximate operations. Inspired by [26], we propose to explore algorithm-
level polynomial approximation to implement GELU and Softmax functions,
through which we introduce $\delta_{1}$ and $\delta_{2}$ (both $<$1) to
control the regularization effect. Since the Sigmoid function is only present
inside token selectors (a small number), we do not introduce a regularization
effect for it.

The $\mathrm{erf}(x)$ function is approximated using a second-order polynomial
as,

$L_{\mathrm{erf}}(x)=\mathrm{sign}(x)\cdot\delta_{1}\cdot[a(\mathrm{clip}(|x|,\max=-b)+b)^{2}+1],$
(11)

with the constants $a=-0.2888$, $b=-1.769$ and $\delta_{1}<1$.

The GELU function is then expressed as

$\mathrm{GELU_{aprx}}(x)=\frac{x}{2}\left[1+L_{\mathrm{erf}}\left(\frac{x}{\sqrt{2}}\right)\right],$
(12)

The Softmax function is approximated as

$\mathrm{Softmax_{aprx}}(\mathbf{x}_{i})=\frac{\delta_{2}\exp(\tilde{x}_{i})}{\sum_{j=1}^{N}\exp(\tilde{x}_{j})},$
(13)

with $\tilde{x}_{i}=x_{i}-x_{\max}$, $x_{\max}=\max_{i}(x_{i})$ and
$\delta_{2}<1$. This subtraction ensures the numerical stability during the
approximation calculation, and all inputs can be decomposed as
$\tilde{x}=(-\ln 2)z+p$, where $z$ is a non-negative integer and $p$ is a real
number in $(-\ln 2,0]$. $\exp(\tilde{x})$ can then be calculated as
$\exp(p)>>z$, where $z=\left\lfloor-\tilde{x}/\ln 2\right\rfloor$,
$p=\tilde{x}+z\ln 2$, and $\exp(p)$ is approximated as

$\exp(p)=0.3585(p+1.353)^{2}+0.344.$ (14)

Both $\delta_{1}$ and $\delta_{2}$ are regularization value ($<1$) on
quantization error, which can be constant ($\delta_{1}$=0.5, $\delta_{2}$=0.5
in our case).

For the Sigmoid function, we adopt the piece-wise linear approximation (PLAN)
from [46].

TABLE III: Resource utilization for nonlinear functions between original (Orig.) and approximation (Aprx.) implementations. | GELU | Sigmoid | Softmax
---|---|---|---
Aprx. | Orig. | Aprx. | Orig. | Aprx. | Orig.
FF | 334 | 191116 | 1015 | 2334 | 1939 | 2464
LUT | 438 | 160909 | 1512 | 2333 | 2364 | 2476
DSP | 4 | 139 | 0 | 3 | 2 | 3

Table III compares the resource utilization for these nonlinear functions
between the original implementations using the built-in Xilinx Vitis HLS math
library and our proposed implementations. Our methods are more resource
efficient than those using the HLS math library, with
1.5$\times$$\sim$572$\times$ resource improvement. Furthermore, for each
model, we try multiple sets of token pruning ratios and there is no accuracy
drops between the approximate model and the original one.

Figure 10: Regularization effect on quantization error of approximated GELU.

###  V-E Regularization Effect on Quantization Error

GELU and Softmax functions are abundant in transformer blocks, which inspires
us to introduce the regularization effect of quantization error into the
approximated functions for more aggressive quantization (e.g., 8-bit fixed-
point quantization in our case). Here we proof that our regularization works.

GELU for activation data is: $A$$=$$\mathrm{GELU}(x)$. Quantization on $x$ can
be considered as adding a small error $\Delta e$ to $x$. We examine the
influence of $\Delta e$ on output $A$ by computing the GELU derivative
$\frac{\partial A}{\partial x}$. Assuming that $A$ changes by $\Delta e$$>$0,
we can obtain the absolute error of output $A$:

$\mathrm{Error_{gelu}}(x)=\frac{\partial A}{\partial x}\cdot\Delta e.$ (15)

Since $\frac{\partial A_{aprx}}{\partial x}$ is always $<1$ (Fig. 10) for
GELU, the total quantization error is reduced after approximation.

Softmax for activation data is:
$A_{i}$$=$$\frac{\delta_{2}\exp(\tilde{x}_{i})}{\sum_{j=1}^{N}\exp(\tilde{x}_{j})}$.
As a similar process as GELU, we compute the $Softmax_{aprx}$ derivative
$\frac{\partial A}{\partial x}$:

$\frac{\partial A}{\partial
x}\\!=\\!\left\\{\begin{matrix}\frac{\partial\frac{\delta_{2}\exp(\tilde{x}_{i})}{\sum_{j=1}^{N}\exp(\tilde{x}_{j})}}{\partial\tilde{x}_{j}}=\delta_{2}\cdot
A_{i}\cdot(1-A_{i}),&i=j\\\
\frac{\partial\frac{\delta_{2}\exp(\tilde{x}_{i})}{\sum_{j=1}^{N}\exp(\tilde{x}_{j})}}{\partial\tilde{x}_{i}}=-\delta_{2}\cdot
A_{i}\cdot A_{j},&i\neq j\end{matrix}\right..$ (16)

Assuming $A_{0}$ changes by $\Delta e_{0}$, the absolute error of all outputs
with Equation (16) is:

$\displaystyle Error_{\mathrm{softmax}}$ $\displaystyle=|\delta_{2}\Delta
e_{0}A_{0}(1-A_{0})|+\sum_{i=1}^{N-1}|-\delta_{2}\Delta e_{0}A_{0}A_{i}|$ (17)
$\displaystyle=2\delta_{2}|\Delta e_{0}|\ A_{0}(1-A_{0})<\Delta e_{0},$

since $0\leq A_{0}\leq 1$, $2A_{0}(1-A_{0})$ is always smaller than 1 and
$2\delta_{2}A_{0}(1-A_{0})$ is further reduced ($\delta_{2}<1$). So, the total
quantization error after Softmax approximation is $<\Delta e_{0}$.

##  VI Latency-Aware Multi-Stage Training Strategy

Our strategy is as follows: (1) We propose latency-sparsity loss to take into
account the latency characteristics of the hardware side during the training
process. (2) We design a block-to-stage training pipeline to learn the number
of token selectors to insert in the backbone ViT, their location and pruning
rates. Please note that (i) the block-to-stage pipeline is based on token
pruning, and 8-bit quantization on weight and activation will lead to
2$\times$$\sim$2.4$\times$ speedup without accuracy drops; and (ii) our
training strategy uses finetuning for each selector, and the training effort
of our pipeline is equivalent to the effort of training-from-scratch of the
backbone ViT.

Relationship between Latency and Keep Ratio. In order to bridge the inference
of ViT model to the actual latency bound of hardware deployment, we build the
latency-sparsity table for the target FPGA as Table IV. In this paper, we
measure the actual numbers from our FPGA implementation. Each time we only
enter the $KeepRatio$ tokens into one ViT block with a selector and test the
corresponding latency.

TABLE IV: Tested latency of one DeiT block with different token keeping ratios on ZCU102 FPGA. Keep Ratio | 1.0 | 0.9 | 0.8 | 0.7 | 0.6 | 0.5
---|---|---|---|---|---|---
Latency | DeiT-T | 1.034 | 0.945 | 0.881 | 0.764 | 0.702 | 0.636
(ms) | DeiT-S | 3.161 | 2.837 | 2.565 | 2.255 | 1.973 | 1.682

Latency-Sparsity Loss. $\xi_{ratio}$ is built as follows:

${\mathrm{Block}(\rho_{i})}=latency\\_sparsity\\_table(\rho_{i})$ (18)
$\sum_{i=1}^{L}{\mathrm{B}lock}_{i}(\rho_{i})\leq LatencyLimit$ (19)
$\xi_{ratio}=\sum_{i=1}^{L}(1-\rho_{i}-\frac{1}{B}\sum_{b=1}^{B}\sum_{j=1}^{N}D_{j}^{i,b})^{2}$
(20)

where Eq. (18) shows the look-up-table mapping to find the latency of one
$\mathrm{Block}$ under the corresponding ratio $\rho_{i}$ in Table IV. Eq.
(19) guarantees that the inference speed of the whole model satisfies the
given hardware latency requirement, with $i$ being the block index, $\rho_{i}$
being the corresponding pruning rate. Through Eq. (18) and (19), we obtain
appropriate $\rho_{i}$ and feed it to the latency-sparsity loss (20), where
$B$ is the training batch size, and $M$ (Eq. (9)) is the token keep decision.
In order to achieve per-image adaptive pruning, we set the average pruning
rate of all images in one batch as the convergence target of the Eq. (20).

Training Objective. It includes the standard cross-entropy loss $\xi_{cls}$,
distillation loss $\xi_{distill}$, and latency-sparsity loss $\xi_{ratio}$.
The former two are the same as the loss strategy used in DeiT.

$\xi=\xi_{cls}+\lambda_{distill}\xi_{distill}+\lambda_{ratio}\xi_{ratio}$ (21)

where we set $\lambda_{distill}{=}0.5$, $\lambda_{ratio}{=}2$ in all our
experiments.

1

Input : ViT blocks $\\{\mathrm{Block}_{i}\\}^{L}_{i=1}$;

Accuracy drop constraint $a_{\mathrm{drop}}$;

Initial pruning rate $\rho_{\mathrm{init}}$;

Target latency $LatencyLimit$.

2

Output : Token selectors with pruning rates $\rho_{s_{1}},...,\rho_{s_{k}}$.

3

// Step1: Insert a token selector between each two adjacent blocks and adjust
the pruning rate $\rho_{i}$.

4 foreach  _$i\in[L,L-1,\dots,4]$_ do

5 $\rho_{i}=\rho_{\mathrm{init}}$;

6 $a,t\leftarrow$ Evaluate$(\\{\mathrm{Block}_{j}(\rho_{j})\\}^{L}_{j=1})$;

7 // $a$ and $t$ represent accuracy drop and latency of the whole model.

8 while  _$a <a_{\mathrm{drop}}$_ do

9 if  _$t <LatencyLimit$_ then

10 Return the finalized token pruned ViT;

11 else

12 Decrease $t_{i}$;

13 $\rho_{i}$ = latency_sparsity_table($t_{i}$);

14 $a,t\leftarrow$ Evaluate$(\\{\mathrm{Block}_{j}(\rho_{j})\\}^{L}_{j=1})$;

15

16

17

// Step2: Combine sequential selectors with similar pruning rates as one
stage, keep the first selector and retrain ViT.

18

19$\rho_{s_{1}},...,\rho_{s_{k}}\leftarrow$ Combine $\rho_{1},...,\rho_{L}$;

20Retrain
ViT$[\mathrm{Block}_{1}(\rho_{1}),..,\mathrm{Block}_{i}(\rho_{s_{1}}),..,\mathrm{Block}_{L}(\rho_{s_{k}})]$;

21 if  _$t <LatencyLimit$_ then

22 Return the finalized token pruned ViT;

23else

24 Increase $a_{drop}$ or $LatencyLimit$;

25 Initialize the model and selectors from the end of the last Step1;

26 Go to the Step1 and repeat the training process.

27

Algorithm 1 Latency-Aware Multi-Stage Training with Image-Adaptive Token
Pruning Figure 11: Accuracy and token sparsity distribution after block-to-
stage training. The insertion before the 2nd and 3rd blocks shows the pruning
difficulty.

Block-to-Stage Training. Algorithm 1 presents our training strategy to find
the optimal accuracy-pruning rate trade-offs and proper locations for token
selectors, based on the token redundancy (Fig. 6). In ViTs, tokens can be more
effectively encoded in later blocks. Hence, we adopt progressive training on
inserting the token selector from later blocks to front ones. Each time we
insert a token selector, we train the current selector and fine tune the other
parts by decreasing the latency of the current block until accuracy drops
noticeably ($>0.5\%$). Since token pruning in the front 3 blocks leads to more
severe accuracy drops, we stop the selector insertion when reaching the fourth
block. If the pruned model has satisfied the target latency, we end the
training and finalize the pruned model; otherwise, continue the training and
repeat the insertion. After all the insertions, if the adjacent selectors have
a similar pruning rate (difference$<8.5\%$), we combine them as one pruning
stage and solely keep the first selector of that stage, shown in Fig. 11.
Finally, if the final latency of the whole model is lower than the target
latency, we return the pruned model; otherwise, we will relax the accuracy or
latency constraints and repeat the training.

##  VII Experimental Results

###  VII-A Experimental Setup

Our experiments include adaptive token pruning and hardware implementation for
ViTs with different pruning settings. Note that after token pruning we will
apply 8-bit quantization on weight and activation, and all the quantization
processes do not lose accuracy, except for 1.2% on DeiT-T.

####  VII-A1 Training Setup for ViT Pruning

The baseline models with 32-bit floating-point precision are from the
TorchVision library [12]. Our experiments are conducted on the ImageNet-1K
dataset with various transformers backbones, including DeiT-T, DeiT-S, DeiT-B,
LV-ViT-S, and LV-ViT-M, as shown in Table V. We follow the training settings
in DeiT. Training on one selector insertion costs 30 epochs on 8 NVIDIA
A100-SXM4-40GB GPUs. The training effort on block-to-stage training is listed
in Table V which illustrates that the training effort of the entire block-to-
stage pipeline is equivalent to the train-from-scratch of the backbone ViT.
Through our training pipeline, we observe that 3$\sim$4 token selectors are
suitable for most of the models.

TABLE V: Training effort for ViTs with different backbones. Model | #Heads |  Embed. Dim. | Depth | #Epochs for Training
---|---|---|---|---
Baseline | Ours
DeiT-T | 3 | 192 | 12 | 300 | 270
DeiT-S | 6 | 384 | 12 | 300 | 270
DeiT-B | 12 | 768 | 12 | 300 | 270
LV-ViT-S | 6 | 384 | 16 | 400 | 390
LV-ViT-M | 8 | 512 | 20 | 400 | 390

####  VII-A2 Hardware Platform

Our hardware accelerator designs are evaluated on the Xilinx ZCU102 platform
[52] with Zynq UltraScale+ MPSoC, containing 2520 DSPs, 912 BRAM blocks, and
274.1k LUTs. We use Vitis HLS to generate the FPGA accelerators. The synthesis
and implementation of the designs are performed with the Xilinx Vitis 2020.1
tool [51]. The working frequency is set to 150 MHz. The data in all models are
represented in an 8-bit fixed-point format. The hardware design for HeatViT is
built based on state-of-the-art FPGA design for ViT [31] with the GEMM engine
described in Section V-B1. Additionally, the HeatViT hardware design
incorporates a token selector and polynomial approximation of nonlinear
functions explained in Section V-C and V-D.

###  VII-B Accuracy and GMACs Results

Fig. 2 demonstrates that our models achieve better accuracy-computation trade-
offs compared to other pruned or scaled models. Our HeatViT reduces the
computation cost by $16.1\%{\sim}42.6\%$ for various backbones with negligible
$\leq 0.75\%$ accuracy degradation, which surpasses existing methods on both
accuracy and efficiency. To explore model scaling on ViT, we train more DeiT
models with the embedding dimension of 160/256/288/320 as our baselines. The
accuracy improvement of HeatViT is 4% (72.1% vs. 68.1% with 0.9 GMACs) over
DeiT-T-160, 4.67% (76.87% vs. 72.20% with 1.3 GMACs) over DeiT-T, and 0.81%
(79.34% vs. 78.53% with 2.64 GMACs) over DeiT-S-288. Additionally, our method
can prune up to 23.1% on DeiT-T and 16.1% on DeiT-S without any accuracy
degradation.

Figure 12: Comparison of different token selector structures. We use DeiT-T (72.2%, 1.3 GMACs) as the baseline. TABLE VI: Hardware results under different pruning settings for various ViTs on ImageNet dataset. Design | Model | Keep Ratio | #GMACs | Bitwidth | Resource Utilization | Power | FPS | Energy Effi.
---|---|---|---|---|---|---|---|---
(Stage 1/2/3) | (Pruning Rate) | kLUT | kFF | BRAM36 | DSP | (W) | (Accl. Rate) | (FPS/W)
Baseline | DeiT-T | 1/1/1 | 1.30 (1$\times$) | 16 |  115.6 (42%) |  101.5 (19%) |  288.5 (32%) |  1739 (69%) | 8.012 | 78.3 (1$\times$) | 9.77
DeiT-S | 1/1/1 | 4.60 (1$\times$) | 16 |  130.3 (48%) |  102.8 (19%) |  492.5 (54%) |  1754 (70%) | 10.095 | 25.9 (1$\times$) | 2.57
LV-ViT-S | 1/1/1 | 6.55 (1$\times$) | 16 | 19.4 (1$\times$) | 1.92
DeiT-B | 1/1/1 | 17.60 (1$\times$) | 16 |  144.5 (53%) |  103.9 (19%) |  664.3 (73%) |  1786 (71%) | 11.041 | 11.2 (1$\times$) | 1.01
HeatViT with Token Selector | DeiT-T | 0.85/0.79/0.51 | 1.00 (1.30$\times$) | 8 |  137.6 (50%) |  126 (23%) |  355.5 (39%) |  1968 (78%) |  9.453 | 183.4 (2.34$\times$) | 19.4
0.76/0.70/0.41 | 0.90 (1.44$\times$) | 8 | 198.8 (2.54$\times$) | 21.0
0.70/0.39/0.21 | 0.75 (1.74$\times$) | 8 | 271.2 (3.46$\times$) | 28.7
DeiT-S | 0.90/0.84/0.61 | 3.86 (1.19$\times$) | 8 |  145 (53%) |  100.4 (18%) |  338.5 (37%) |  1955 (78%) | 10.697 | 57.0 (2.20$\times$) | 5.33
0.70/0.39/0.21 | 2.64 (1.74$\times$) | 8 | 97.1 (3.75$\times$) | 9.08
0.42/0.21/0.13 | 2.02 (2.27$\times$) | 8 | 109.2 (4.22$\times$) | 10.2
LV-ViT-S | 0.90/0.84/0.61 | 5.49 (1.19$\times$) | 8 | 62.8 (3.24$\times$) | 5.87
0.70/0.39/0.21 | 3.77 (1.74$\times$) | 8 | 72.8 (3.75$\times$) | 6.81
0.42/0.21/0.13 | 2.88 (2.27$\times$) | 8 | 89.1 (4.59$\times$) | 8.33
DeiT-B | 0.90/0.84/0.61 | 14.79 (1.19$\times$) | 8 |  161.4 (59%) |  101.8 (19%) |  528.6 (58%) |  2066 (82%) | 11.352 | 36.1 (3.22$\times$) | 3.18
0.70/0.39/0.21 | 10.11 (1.74$\times$) | 8 | 43.3 (3.87$\times$) | 3.81
0.42/0.21/0.13 | 7.75 (2.27$\times$) | 8 | 54.8 (4.89$\times$) | 4.83

####  VII-B1 Operations in Token Selector

We compare different selector structures with the same computation cost of 0.9
GMACs in Fig. 12. MLP-based token selectors outperform convolution-based ones
under different combinations. In addition, MLP-based selectors bring more
benefits than convolution-based ones, since we reuse the GEMM on the FC
operation of original ViTs without opening additional resources for the new
computation design.

For the activation functions, GELU outperforms ReLU [1] and Hardswish [22]
continuously. Even though ReLU and Hardswish can be directly deployed on
FPGAs, the resource utilization of GELU can be improved to
$35\times$$\sim$$572\times$ by the polynomial approximation (Section V-D).

###  VII-C Hardware Results

Multiple hardware accelerators are designed according to the number of heads
in a specific ViT. As shown in Table VI, with the same total degree of
computation parallelism, the resource utilization and power of DeiT-S and LV-
ViT-S designs are higher than those of DeiT-T ones, since DeiT-T has 3 heads
while DeiT-S and LV-ViT-S all have 6 heads, requiring more BRAM space to
accommodate data of all the attention heads. This trend is similar for DeiT-B
(12 heads).

Compared with the baseline hardware designs (16-bit and no token pruning), the
accelerators with token selector in HeatViT framework utilize 9% more DSPs and
8% more LUTs for DeiT-T, 8% more DSPs and 5% more LUTs for DeiT-S and LV-
ViT-S, 11% more DSPs and 6% more LUTs for DeiT-B. This demonstrates that the
control flow to support adaptive token pruning introduces negligible resource
utilization overhead. After the token pruning, the frame rate increases from
78.3 FPS to 142.7 FPS (1.82$\times$) for DeiT-T, from 25.9 FPS to 57.6 FPS
(2.22$\times$) for DeiT-S, from 19.4 FPS to 46.9 FPS (2.42$\times$) for LV-
ViT-S, and from 11.2 FPS to 28.9 FPS (2.58$\times$) for DeiT-B. Furthermore,
we deploy the 8-bit fixed-point quantization on models to achieve another
1.90$\times$ speedup, ending up the final speedup with 3.46$\times$ (271.2
FPS) for DeiT-T, 4.22$\times$ (109.2 FPS) for DeiT-S, 4.59$\times$ (89.1 FPS)
for LV-ViT-S, and 4.89$\times$ (54.8 FPS) for the DeiT-B.

####  VII-C1 Comparisons with CPUs and GPUs

Figure 13: Comparison of energy efficiency between HeatViT and TX2 CPU/GPU
with the improvement breakdown of different techniques.

We also test DeiT-T, DeiT-S, LV-ViT-S, and DeiT-B on Jetson TX2 with 4-core
ARM CPU and NVIDIA Pascal GPU, and compared them with our FPGA (ZCU102)
implementation. Since MSA and FFN computations are reduced by token pruning,
CPUs and GPUs can also be accelerated. And TX2 CPU/GPU does not support low-
bit computation, so we only present the full precision model for them with
adaptive token pruning as shown in Fig. 13. All the results are normalized
against the original model on TX2 CPU without token pruning. First, our final
FPGA implementation achieves the highest $1827\times\sim 3013\times$ speedup
with 9.453W, 10.697W, and 11.352W power for different designs. While the
baseline FPGA design [31] (16-bit and no token pruning) achieves
373$\times$$\sim$870$\times$ speedup, token pruning can bring
1.82$\times$$\sim$2.58$\times$ speedup and ambitious 8-bit quantization can
contribute another 1.90$\times$ speedup. Second, with token pruning, TX2 GPU
achieves 647$\times$$\sim$814$\times$ speedup with 12W power and TX2 CPU
achieves 1.78$\times$$\sim$2.67$\times$ speedup with 4W power. For the energy
efficiency, our FPGA implementation achieves 4.8 FPS/W$\sim$28.7 FPS/W, which
is 242.6$\times$$\sim$719.0$\times$ higher than TX2 CPU and
3.0$\times$$\sim$4.7$\times$ higher than TX2 GPU (with token pruning).

##  VIII Conclusion

In this paper, we have proposed a hardware-efficient image-adaptive token
pruning framework called HeatViT for ViT inference acceleration on resource-
constraint edge devices. To improve the pruning rate and accuracy, we analyzed
the inherent computational patterns in ViTs and designed an effective token
selector that can more accurately classify tokens and consolidates non-
informative tokens. We also implemented a proof-of-concept ViT hardware
accelerator on FPGAs by heavily reusing the hardware components built for the
backbone ViT to support the adaptive token pruning module. Besides, we propose
a polynomial approximation of nonlinear functions for ambitious (8-bit)
quantization and efficient hardware implementation. Finally, to meet both the
target inference latency and model accuracy, we proposed a latency-aware
multi-stage training strategy to learn the number of token selectors to insert
into the backbone ViT, and the location and pruning rate of each token
selector. Experimental results demonstrate that HeatViT achieves superior
pruning rate and accuracy compared to state-of-the-art pruning studies, while
incurring trivial amount of hardware resource overhead.

## Acknowledgements

This work is partly supported by NSF CCF-1901378; NSERC Discovery Grant
RGPIN-2019-04613, DGECR-2019-00120, Alliance Grant ALLRP-552042-2020; CFI John
R. Evans Leaders Fund.

## References

  * [1] A. F. Agarap, “Deep learning using rectified linear units (relu),” _arXiv preprint arXiv:1803.08375_ , 2018.
  * [2] D. Bahdanau, K. H. Cho, and Y. Bengio, “Neural machine translation by jointly learning to align and translate,” in _International Conference on Learning Representations (ICLR)_ , 2015.
  * [3] T. B. Brown, B. Mann, N. Ryder, M. Subbiah, J. Kaplan, P. Dhariwal, A. Neelakantan, P. Shyam, G. Sastry, A. Askell, S. Agarwal, A. Herbert-Voss, G. Krueger, T. Henighan, R. Child, A. Ramesh, D. M. Ziegler, J. Wu, C. Winter, C. Hesse, M. Chen, E. Sigler, M. Litwin, S. Gray, B. Chess, J. Clark, C. Berner, S. McCandlish, A. Radford, I. Sutskever, and D. Amodei, “Language models are few-shot learners,” in _Advances in Neural Information Processing Systems (NeurIPS)_ , vol. 33, 2020, pp. 1877–1901.
  * [4] H. Cao, Y. Wang, J. Chen, D. Jiang, X. Zhang, Q. Tian, and M. Wang, “Swin-unet: Unet-like pure transformer for medical image segmentation,” _arXiv preprint arXiv:2105.05537_ , 2021.
  * [5] N. Carion, F. Massa, G. Synnaeve, N. Usunier, A. Kirillov, and S. Zagoruyko, “End-to-end object detection with transformers,” in _European Conference on Computer Vision (ECCV)_. Springer, 2020, pp. 213–229.
  * [6] B. Chen, P. Li, C. Li, B. Li, L. Bai, C. Lin, M. Sun, J. Yan, and W. Ouyang, “Glit: Neural architecture search for global and local image transformer,” in _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , 2021, pp. 12–21.
  * [7] H. Chen, Y. Wang, T. Guo, C. Xu, Y. Deng, Z. Liu, S. Ma, C. Xu, C. Xu, and W. Gao, “Pre-trained image processing transformer,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2021, pp. 12 299–12 310.
  * [8] M. Chen, H. Peng, J. Fu, and H. Ling, “Autoformer: Searching transformers for visual recognition,” in _Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV)_ , 2021, pp. 12 270–12 280.
  * [9] M. Chen, K. Wu, B. Ni, H. Peng, B. Liu, J. Fu, H. Chao, and H. Ling, “Searching the search space of vision transformer,” in _Advances in Neural Information Processing Systems (NeurIPS)_ , vol. 34, 2021, pp. 8714–8726.
  * [10] T. Chen, Y. Cheng, Z. Gan, L. Yuan, L. Zhang, and Z. Wang, “Chasing sparsity in vision transformers: An end-to-end exploration,” in _Advances in Neural Information Processing Systems_ , 2021.
  * [11] A. Dosovitskiy, L. Beyer, A. Kolesnikov, D. Weissenborn, X. Zhai, T. Unterthiner, M. Dehghani, M. Minderer, G. Heigold, S. Gelly, J. Uszkoreit, and N. Houlsby, “An image is worth 16x16 words: Transformers for image recognition at scale,” in _International Conference on Learning Representations (ICLR)_ , 2021.
  * [12] Facebook, “Torchvision,” 2021, last accessed Sept 12, 2021. [Online]. Available: https://pytorch.org/vision/stable/models.html
  * [13] M. Fayyaz, S. A. Kouhpayegani, F. R. Jafari, E. Sommerlade, H. R. V. Joze, H. Pirsiavash, and J. Gall, “Ats: Adaptive token sampling for efficient vision transformers,” _arXiv preprint arXiv:2111.15667_ , 2021.
  * [14] S. Fox, J. Faraone, D. Boland, K. Vissers, and P. H. Leong, “Training deep neural networks in low-precision with high accuracy using fpgas,” in _2019 International Conference on Field-Programmable Technology (ICFPT)_ , 2019, pp. 1–9.
  * [15] S. Fox, J. Faraone, D. Boland, K. Vissers, and P. H. Leong, “Training deep neural networks in low-precision with high accuracy using fpgas,” in _2019 International Conference on Field-Programmable Technology (ICFPT)_. IEEE, 2019, pp. 1–9.
  * [16] C. Gong, D. Wang, M. Li, X. Chen, Z. Yan, Y. Tian, and V. Chandra, “Nasvit: Neural architecture search for efficient vision transformers with gradient conflict aware supernet training,” in _International Conference on Learning Representations (ICLR)_ , 2021.
  * [17] I. Goodfellow, Y. Bengio, and A. Courville, _Deep Learning_. MIT Press, 2016, http://www.deeplearningbook.org.
  * [18] Y. Guo, Y. Zheng, M. Tan, Q. Chen, J. Chen, P. Zhao, and J. Huang, “Nat: Neural architecture transformer for accurate and compact architectures,” in _Advances in Neural Information Processing Systems (NeurIPS)_ , vol. 32, 2019\.
  * [19] K. Han, A. Xiao, E. Wu, J. Guo, C. Xu, and Y. Wang, “Transformer in transformer,” in _Advances in Neural Information Processing Systems_ , 2021\.
  * [20] D. Hendrycks and K. Gimpel, “Gaussian error linear units (gelus),” _arXiv preprint arXiv:1606.08415_ , 2016.
  * [21] B. Heo, S. Yun, D. Han, S. Chun, J. Choe, and S. J. Oh, “Rethinking spatial dimensions of vision transformers,” in _Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV)_ , 2021.
  * [22] A. Howard, M. Sandler, G. Chu, L.-C. Chen, B. Chen, M. Tan, W. Wang, Y. Zhu, R. Pang, V. Vasudevan _et al._ , “Searching for mobilenetv3,” in _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , 2019, pp. 1314–1324.
  * [23] J. Hu, L. Shen, and G. Sun, “Squeeze-and-excitation networks,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2018, pp. 7132–7141.
  * [24] Z. Jiang, Q. Hou, L. Yuan, D. Zhou, Y. Shi, X. Jin, A. Wang, and J. Feng, “All tokens matter: Token labeling for training better vision transformers,” _arXiv preprint arXiv:2104.10858_ , 2021.
  * [25] J. D. M.-W. C. Kenton and L. K. Toutanova, “Bert: Pre-training of deep bidirectional transformers for language understanding,” in _Proceedings of NAACL-HLT_ , 2019, pp. 4171–4186.
  * [26] S. Kim, A. Gholami, Z. Yao, M. W. Mahoney, and K. Keutzer, “I-bert: Integer-only bert quantization,” _arXiv preprint arXiv:2101.01321_ , 2021\.
  * [27] Z. Kong, P. Dong, X. Ma, X. Meng, W. Niu, M. Sun, B. Ren, M. Qin, H. Tang, and Y. Wang, “Spvit: Enabling faster vision transformers via soft token pruning,” _arXiv preprint arXiv:2112.13890_ , 2021.
  * [28] S. Kornblith, M. Norouzi, H. Lee, and G. Hinton, “Similarity of neural network representations revisited,” in _International Conference on Machine Learning (ICML)_. PMLR, 2019, pp. 3519–3529.
  * [29] B. Li, S. Pandey, H. Fang, Y. Lyv, J. Li, J. Chen, M. Xie, L. Wan, H. Liu, and C. Ding, “Ftrans: energy-efficient acceleration of transformers using fpga,” in _Proceedings of the ACM/IEEE International Symposium on Low Power Electronics and Design_ , 2020, pp. 175–180.
  * [30] C. Li, T. Tang, G. Wang, J. Peng, B. Wang, X. Liang, and X. Chang, “Bossnas: Exploring hybrid cnn-transformers with block-wisely self-supervised neural architecture search,” in _Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV)_ , 2021, pp. 12 281–12 291.
  * [31] Z. Li, M. Sun, A. Lu, H. Ma, G. Yuan, Y. Xie, H. Tang, Y. Li, M. Leeser, Z. Wang, X. Lin, and Z. Fang, “Auto-vit-acc: An fpga-aware automatic acceleration framework for vision transformer with mixed-scheme quantization,” in _International Conference on Field Programmable Logic and Applications_. Springer, 2022, pp. 289–300.
  * [32] Y. Liang, C. GE, Z. Tong, Y. Song, J. Wang, and P. Xie, “EVit: Expediting vision transformers via token reorganizations,” in _International Conference on Learning Representations_ , 2022. [Online]. Available: https://openreview.net/forum?id=BjyvwnXXVn_
  * [33] Z. Liu, Y. Wang, K. Han, W. Zhang, S. Ma, and W. Gao, “Post-training quantization for vision transformer,” in _Advances in Neural Information Processing Systems (NeurIPS)_ , vol. 34, 2021, pp. 28 092–28 103.
  * [34] M. Mao, R. Zhang, H. Zheng, P. Gao, T. Ma, Y. Peng, E. Ding, and S. Han, “Dual-stream network for visual recognition,” in _Advances in Neural Information Processing Systems_ , 2021.
  * [35] T. M. Mitchell, “Machine learning and data mining,” _Communications of the ACM_ , vol. 42, no. 11, pp. 30–36, 1999.
  * [36] B. Pan, Y. Jiang, R. Panda, Z. Wang, R. Feris, and A. Oliva, “Ia-red2: Interpretability-aware redundancy reduction for vision transformers,” in _Advances in Neural Information Processing Systems_ , 2021.
  * [37] A. Parikh, O. Täckström, D. Das, and J. Uszkoreit, “A decomposable attention model for natural language inference,” in _Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing_ , 2016, pp. 2249–2255.
  * [38] G. Prato, E. Charlaix, and M. Rezagholizadeh, “Fully quantized transformer for machine translation,” in _Findings of the Association for Computational Linguistics: EMNLP 2020_ , 2020, pp. 1–14.
  * [39] S. Prillo and J. Eisenschlos, “Softsort: A continuous relaxation for the argsort operator,” in _International Conference on Machine Learning (ICML)_. PMLR, 2020, pp. 7793–7802.
  * [40] P. Qi, Y. Song, H. Peng, S. Huang, Q. Zhuge, and E. H.-M. Sha, “Accommodating transformer onto fpga: Coupling the balanced model compression and fpga-implementation optimization,” in _Proceedings of the 2021 on Great Lakes Symposium on VLSI_ , 2021, pp. 163–168.
  * [41] Y. Rao, W. Zhao, B. Liu, J. Lu, J. Zhou, and C.-J. Hsieh, “Dynamicvit: Efficient vision transformers with dynamic token sparsification,” in _Advances in Neural Information Processing Systems_ , 2021.
  * [42] D. So, Q. Le, and C. Liang, “The evolved transformer,” in _International Conference on Machine Learning (ICML)_. PMLR, 2019, pp. 5877–5886.
  * [43] M. Sun, Z. Li, A. Lu, Y. Li, S.-E. Chang, X. Ma, X. Lin, and Z. Fang, “Film-qnn: Efficient fpga acceleration of deep neural networks with intra-layer, mixed-precision quantization,” in _Proceedings of the 2022 ACM/SIGDA International Symposium on Field-Programmable Gate Arrays (FPGA)_ , 2022, p. 134–145.
  * [44] Y. Tang, K. Han, Y. Wang, C. Xu, J. Guo, C. Xu, and D. Tao, “Patch slimming for efficient vision transformers,” 2021.
  * [45] H. Touvron, M. Cord, M. Douze, F. Massa, A. Sablayrolles, and H. Jégou, “Training data-efficient image transformers & distillation through attention,” in _International Conference on Machine Learning_ , 2021, pp. 10 347–10 357.
  * [46] I. Tsmots, O. Skorokhoda, and V. Rabyk, “Hardware implementation of sigmoid activation functions using fpga,” in _2019 IEEE 15th International Conference on the Experience of Designing and Application of CAD Systems (CADSM)_ , 2019, pp. 34–38.
  * [47] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, Ł. Kaiser, and I. Polosukhin, “Attention is all you need,” in _Advances in Neural Information Processing Systems_ , 2017, pp. 5998–6008.
  * [48] H. Wang, Z. Wu, Z. Liu, H. Cai, L. Zhu, C. Gan, and S. Han, “Hat: Hardware-aware transformers for efficient natural language processing,” in _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics (ACL)_ , 2020, pp. 7675–7688.
  * [49] W. Wang, E. Xie, X. Li, D.-P. Fan, K. Song, D. Liang, T. Lu, P. Luo, and L. Shao, “Pyramid vision transformer: A versatile backbone for dense prediction without convolutions,” in _Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV)_ , 2021.
  * [50] H. Wu, B. Xiao, N. Codella, M. Liu, X. Dai, L. Yuan, and L. Zhang, “Cvt: Introducing convolutions to vision transformers,” _arXiv preprint arXiv:2103.15808_ , 2021.
  * [51] Xilinx, “Vitis unified software platform,” 2022, last accessed April 21, 2022\. [Online]. Available: https://www.xilinx.com/products/design-tools/vitis/vitis-platform.html#development
  * [52] Xilinx, “Zcu102 evaluation board - user guide,” 2022, last accessed April 21, 2022\. [Online]. Available: https://www.xilinx.com/content/dam/xilinx/support/documents/boards_and_kits/zcu102/ug1182-zcu102-eval-bd.pdf
  * [53] Y. Xu, Z. Zhang, M. Zhang, K. Sheng, K. Li, W. Dong, L. Zhang, C. Xu, and X. Sun, “Evo-vit: Slow-fast token evolution for dynamic vision transformer,” _arXiv preprint arXiv:2108.01390_ , 2021.
  * [54] C. Yang, Z. Wu, B. Zhou, and S. Lin, “Instance localization for self-supervised detection pretraining,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2021, pp. 3987–3996.
  * [55] H. Yu and J. Wu, “A unified pruning framework for vision transformers,” _arXiv preprint arXiv:2111.15127_ , 2021.
  * [56] S. Yu, T. Chen, J. Shen, H. Yuan, J. Tan, S. Yang, J. Liu, and Z. Wang, “Unified visual transformer compression,” in _International Conference on Learning Representations_ , 2022.
  * [57] L. Yuan, Y. Chen, T. Wang, W. Yu, Y. Shi, Z.-H. Jiang, F. E. Tay, J. Feng, and S. Yan, “Tokens-to-token vit: Training vision transformers from scratch on imagenet,” in _Proceedings of the IEEE/CVF International Conference on Computer Vision_ , 2021, pp. 558–567.
  * [58] C. Zhang, G. Sun, Z. Fang, P. Zhou, P. Pan, and J. Cong, “Caffeine: Toward uniformed representation and acceleration for deep convolutional neural networks,” _IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems_ , vol. 38, no. 11, pp. 2072–2085, 2018.
  * [59] X. Zhang, Y. Wu, P. Zhou, X. Tang, and J. Hu, “Algorithm-hardware co-design of attention mechanism on fpga devices,” _ACM Transactions on Embedded Computing Systems (TECS)_ , vol. 20, no. 5s, pp. 1–24, 2021.
  * [60] Z. Zhao, Y. Liu, L. Chen, Q. Liu, R. Ma, and K. Yu, “An investigation on different underlying quantization schemes for pre-trained language models,” in _CCF International Conference on Natural Language Processing and Chinese Computing_. Springer, 2020, pp. 359–371.
  * [61] S. Zheng, J. Lu, H. Zhao, X. Zhu, Z. Luo, Y. Wang, Y. Fu, J. Feng, T. Xiang, P. H. Torr _et al._ , “Rethinking semantic segmentation from a sequence-to-sequence perspective with transformers,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2021, pp. 6881–6890.
  * [62] D. Zhou, Y. Shi, B. Kang, W. Yu, Z. Jiang, Y. Li, X. Jin, Q. Hou, and J. Feng, “Refiner: Refining self-attention for vision transformers,” 2021.
  * [63] L. Zhou, Y. Zhou, J. J. Corso, R. Socher, and C. Xiong, “End-to-end dense video captioning with masked transformer,” in _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2018, pp. 8739–8748.
  * [64] M. Zhu, K. Han, Y. Tang, and Y. Wang, “Visual transformer pruning,” in _KDD 2021 Workshop on Model Mining_ , 2021.
  * [65] X. Zhu, W. Su, L. Lu, B. Li, X. Wang, and J. Dai, “Deformable detr: Deformable transformers for end-to-end object detection,” in _International Conference on Learning Representations (ICLR)_ , 2020.