BiFormer: Vision Transformer with Bi-Level Routing Attention

Lei Zhu1 Xinjiang Wang2 Zhanghan Ke1 Wayne Zhang2 Rynson Lau1†
1 2
City University of Hong Kong SenseTime Research
{lzhu68-c,zhanghake2-c}@[Link], {wangxinjiang,[Link]}@[Link]
[Link]@[Link]
arXiv:2303.08810v1 [[Link]] 15 Mar 2023

it is almost inductive-bias-free and thus makes the model

Abstract more flexible to fit tons of data [15]. Last but not least, it
enjoys high parallelism, which benefits training and infer-
As the core building block of vision transformers, atten- ence of large models [13, 33, 36, 42]. Hence, transformer
tion is a powerful tool to capture long-range dependency. has not only revolutionized natural language processing but
However, such power comes at a cost: it incurs a huge also shown very promising progress in computer vision.
computation burden and heavy memory footprint as pair- The computer vision community has witnessed an explo-
wise token interaction across all spatial locations is com- sion of vision transformers in the past two years [1, 14, 15,
puted. A series of works attempt to alleviate this problem 29, 44, 46]. Among these works, a popular topic is to im-
by introducing handcrafted and content-agnostic sparsity prove the core building block, i.e., attention. In contrast to
into attention, such as restricting the attention operation to convolution, which is intrinsically a local operator, a cru-
be inside local windows, axial stripes, or dilated windows. cial property of attention is the global receptive field, which
In contrast to these approaches, we propose a novel dy- empowers vision transformers to capture long-range depen-
namic sparse attention via bi-level routing to enable a more dency [42]. However, such a property comes at a cost: as
flexible allocation of computations with content awareness. attention computes pairwise token affinity across all spatial
Specifically, for a query, irrelevant key-value pairs are first locations, it has a high computational complexity and incurs
filtered out at a coarse region level, and then fine-grained heavy memory footprints.
token-to-token attention is applied in the union of remain- To alleviate the problem, a promising direction is to in-
ing candidate regions (i.e., routed regions). We provide troduce sparse attention [6] to vision transformers, so that
a simple yet effective implementation of the proposed bi- each query attends to a small portion of key-value pairs
level routing attention, which utilizes the sparsity to save instead of all. In this fashion, several handcrafted sparse
both computation and memory while involving only GPU- patterns have been explored, such as restricting attention
friendly dense matrix multiplications. Built with the pro- in local windows [29], dilated windows [41, 46], or axial
posed bi-level routing attention, a new general vision trans- stripes [46]. On the other hand, there are also works try-
former, named BiFormer, is then presented. As BiFormer ing to make the sparsity adaptive to data [5, 48]. However,
attends to a small subset of relevant tokens in a query adap- while they use different strategies to merge or select key/-
tive manner without distraction from other irrelevant ones, value tokens, these tokens are query-agnostic, i.e., they are
it enjoys both good performance and high computational shared by all queries. Nonetheless, according to the visual-
efficiency, especially in dense prediction tasks. Empirical ization of pretrained ViT 1 [15] and DETR 2 [1], queries in
results across several computer vision tasks such as image different semantic regions actually attend to quite different
classification, object detection, and semantic segmentation key-value pairs. Hence, forcing all queries to attend to the
verify the effectiveness of our design. Code is available at same set of tokens may be suboptimal.
[Link] In this paper, we seek an attention mechanism with dy-
namic, query-aware sparsity. Basically, we aim for each
1. Introduction query to attend to a small portion of the most semantically
relevant key-value pairs. The first problem comes as how
Transformer has many properties that are suitable for
building powerful data-driven models. First, it is able to 1 [Link]

capture long-range dependency in the data [29,42]. Second, 2 https : / / colab . research . google . com / github /

facebookresearch/detr/blob/colab/notebooks/detr_
† Corresponding author. [Link]

1
 query key/value local window

(a) Vanilla Attention (b) Local Attention (c) Axial Attention

(d) Dilated Attention (e) Deformable Attention (f) Bi-level Routing Attention

Figure 1. Vanilla attention and its sparse variants. (a) Vanilla attention operates gloabally and incurs high computational complexity
and heavy memory footprint. (b)-(d) Several works attempt to alleviate the complexity by introducing sparse attention with different
handcrafted patterns, such as local window [29, 46], axial stripe [14], dilated window [41, 46]. (e) Deformable attention [48] enables
image-adaptive sparsity via deforming a regular grid. (f) We achieve dynamic, query-aware sparsity with bi-level routing attention, which
first searches top-k (k = 3 in this case) relevant regions, and then attends to the union of them.

to locate these key-value pairs to attend. For example, if we lution via gathering key/value tokens, where only hardware-
select key-value pairs in a per-query manner as done in [17], friendly dense matrix multiplications are involved. We refer
it still requires evaluation of pairwise affinity between all to this approach as Bi-level Routing Attention (BRA), as it
queries and keys, and hence has the same complexity of contains a region-level routing step and a token-level atten-
vanilla attention. Another possibility is to predict attention tion step.
offsets based on local context for each query [10, 48], and By using BRA as the core building block, we propose
hence pairwise affinity computation is avoided. However, BiFormer, a general vision transformer backbone that can
in this way, it is problematic to model long-range depen- be used for many applications such as classification, object
dency [48]. detection, and semantic segmentation. As BRA enables Bi-
To locate valuable key-value pairs to attend globally with Former to attend to a small subset of the most relevant key/-
high efficiency, we propose a region-to-region routing ap- value tokens for each query in a content-aware manner, our
proach. Our core idea is to filter out the most irrelevant model achieves a better computation-performance trade-off.
key-value pairs at a coarse-grained region level, instead of For example, with 4.6G FLOPs computation, BiFormer-T
directly at the fine-grained token level. This is done by first achieves 83.8% top-1 accuracy on ImageNet-1K classifi-
constructing a region-level affinity graph and then pruning it cation, which is the best as far as we know under similar
to keep only top-k connections for each node. Hence, each computation budgets without training with external data or
region only needs to attend to the top-k routed regions. With distillation [23,40]. The improvements are also consistently
the attending regions determined, the next step is to apply shown in downstream tasks such as instance segmentation
token-to-token attention, which is non-trivial as key-value and semantic segmentation.
pairs are now assumed to be spatially scattered. For this To summarize, our contributions are as follows. We in-
case, while the sparse matrix multiplication is applicable, troduce a novel bi-level routing mechanism to vanilla at-
it is inefficient in modern GPUs, which rely on coalesced tention, which enables content-aware sparse patterns in a
memory operations, i.e., accessing blocks of dozens of con- query-adaptive manner. Using the bi-level routing atten-
tiguous bytes at once [31]. Instead, we propose a simple so- tion as the basic building block, we propose a general vi-

2
sion transformer named BiFormer. Experimental results on ken pyramid and assembles messages from all levels of dif-
various computer vision tasks including image classifica- ferent granularities. In addition, the quad-tree requires deep
tion, object detection, and semantic segmentation show that recursion to cover the whole feature map, which hurts par-
the proposed BiFormer achieves significantly better perfor- allelism, while our bi-level routing attention can be more
mances over the baselines under similar model sizes. efficiently implemented by key/value token gathering, fol-
lowed by dense matrix multiplications. As a result, quad-
2. Related Works tree transformer is much slower than our BiFormer.
Vision transformers. Transformers are a family of neu- 3. Our Approach: BiFormer
ral networks that adopt channel-wise MLP blocks for per-
location embedding (channel mixing) and attention [42] This section elaborates the proposed approach. We start
blocks for cross-location relation modeling (spatial mix- by briefly summarizing the attention mechanism in Sec-
ing). Transformers were originally proposed for natural tion 3.1. We then introduce our novel bi-level routing atten-
language processing [13, 42] and then introduced to com- tion (BRA) mechanism, which enables dynamic and query-
puter vision by pioneering works such as DETR [1] and adaptive sparsity, in Section 3.2. We further show that BRA
4
ViT [15]. In comparison with CNNs, the biggest difference can achieve O((HW ) 3 ) complexity with a proper region
is that transformers use attention as an alternative to con- partition size in Section 3.3. Finally, using BRA as the core
volution to enable global context modeling. However, as building block, we present a new hierarchical vision trans-
vanilla attention computes pairwise feature affinity across former, named BiFormer, in Section 3.4.
all spatial locations, it incurs a high computation burden and
3.1. Preliminaries: Attention
heavy memory footprints, especially for high-resolution in-
puts. Hence, an important research direction is to seek more Taking queries Q ∈ RNq ×C , keys K ∈ RNkv ×C , and
efficient attention mechanisms. values V ∈ RNkv ×C as input, an attention function trans-
forms each query as a weighted sum of values, where the
Efficient attention mechanisms. A large volume of works weights are computed as normalized dot products between
have been proposed to reduce the computation and mem- the query and corresponding keys. It can be formally de-
ory complexity bottlenecks of vanilla attention by utiliz- fined in a compact matrix form, as:
ing sparse connection patterns [6], low-rank approxima- 
QKT

tions [43] or recurrent operations [11]. A thorough survey Attention(Q, K, V) = softmax √ V. (1)
of these attention variants can be found at [39]. In the scope C
√
of vision transformers, sparse attention gains its popular- Here, the scalar factor C is introduced to avoid concen-
ity recently due to the tremendous success of Swin trans- trated weights and gradient vanishing [42].
former [29]. In Swin transformer, attention is restricted In transformers, the de facto building block used is multi-
to non-overlapping local windows, and the shift window head self-attention (MHSA). By “self-attention”, it means
operation is introduced to enable inter-window communi- that queries Q, keys K and values V are derived as lin-
cation between adjacent windows. To enable larger and ear projections of the same input X ∈ RN ×C . (For vision
even quasi-global receptive fields under a reasonable com- transformers, X is a spatially flattened feature map, i.e.,
putation budget, several follow-up works introduce dif- N = H × W , where H and W are the height and width,
ferent handcrafted sparse patterns, such as dilated win- respectively, of the feature map.) As for “multi-head”, it
dows [41, 46] or cross-shaped windows [14]. There are also implies splitting the output into h chunks (i.e., heads) along
works that try to make the sparse pattern adaptive to data, the channel dimension with each chunk using an indepen-
such as DAT [48], TCFormer [53] and DPT [5]. While these dent group of projection weights. Formally,
works reduce the number of key/value tokens via different
merging or selection strategies, these key/value tokens are MHSA(X) = Concat(head0 , head1 , ..., headh )Wo ,
shared by all queries on an image. Instead, we explore headi = Attention(XWiq , XWik , XWiv ),
query-aware key/value token selection. The key observa- (2)
C
tion which motivates our work is that the attentive region where headi ∈ RN × h is the output of the ith attention
C
for different queries may differ significantly according to head. Wiq , Wik , Wiv ∈ RC× h are corresponding input
the visualization of pretrained ViT [15] and DETR [1]. As projection weights. An extra linear transformation with
we achieve the goal of query-adaptive sparsity in a coarse- weight matrix Wo ∈ RC×C is used to compose all heads.
to-fine manner, it shares some similarities with quad-tree MHSA has a complexity of O(N 2 ), as there are N
attention [38]. Different from quad-tree attention, the goal queries and each query will attend to N key-value pairs.
of our bi-level routing attention is to locate a few most rel- Such a high complexity causes severe scalability issues
evant key-value pairs, while quad-tree attention builds a to- w.r.t. the spatial resolution of the inputs.

3
Algorithm 1 Pseudocode of BRA in a PyTorch-like style.
# input: features (H, W, C). Assume H==W. mm &
mm
softmax
# output: features (H, W, C).
# S: square root of number of regions.
# k: number of regions to attend.

# patchify input (H, W, C) -> (Sˆ2, HW/Sˆ2, C)

x = patchify(input, patch_size=H//S)

# linear projection of query, key, value

query, key, value = linear_qkv(x).chunk(3, dim=-1)

# regional query and key (Sˆ2, C) gather

query_r, key_r = [Link](dim=1), [Link](dim=1)

# adjacency matrix for regional graph (Sˆ2, Sˆ2) Figure 2. By gathering key-value pairs in top k related windows,
A_r = mm(query_r, key_r.transpose(-1, -2))
we utilize the sparsity to skip computations in the most irrelevant
# compute index matrix of routed regions (Sˆ2, K) regions, while only GPU-friendly dense matrix multiplications are
I_r = topk(A_r, k).index
involved.
# gather key-value pairs
key_g = gather(key, I_r) # (Sˆ2, kHW/Sˆ2, C)
value_g = gather(value, I_r) # (Sˆ2, kHW/Sˆ2, C)

# token-to-token attention
Region-to-region routing with directed graph. We then
A = bmm(query, key_g.transpose(-2, -1)) find the attending relationship (i.e., the regions that should
A = softmax(A, dim=-1)
output = bmm(A, value_g) + dwconv(value) be attended for each given region) by constructing a directed
# recover to (H, W, C) shape
graph. Specifically, we first derive region-level queries and
2
output = unpatchify(output, patch_size=H//S) keys, Qr , Kr ∈ RS ×C , via applying per-region average
on Q and K, respectively. We then derive the adjacency
bmm: batch matrix multiplication; mm: matrix multiplication. dwconv: depthwise 2 2
convolution. matrix, Ar ∈ RS ×S , of region-to-region affinity graph
via matrix multiplication between Qr and transposed Kr :
3.2. Bi-Level Routing Attention (BRA) Ar = Qr (Kr )T . (4)
To mitigate the scalability issue of MHSA, several
works [14, 29, 41, 46, 48] propose different sparse attention Entries in the adjacency matrix, Ar , measure how much
mechanisms, in which each query attends to only a small two regions are semantically related. The core step that we
number of key-value pairs instead of all. However, these ex- perform next is to prune the affinity graph by keeping only
isting works either use handcrafted static patterns or share top-k connections for each region. Specifically, we derive a
2

the sampled subset of key-value pairs among all queries, as routing index matrix, Ir ∈ NS ×k , with the row-wise topk
shown in Figure 1. In this work, we explore a dynamic, operator:
query-aware sparse attention mechanism. Our key idea is to Ir = topkIndex(Ar ). (5)
filter out most irrelevant key-value pairs in a coarse region Hence, the ith row of Ir contains k indices of most relevant
level so that only a small portion of routed regions remain. regions for the ith region.
We then apply fine-grained token-to-token attention in the
union of these routed regions. To simplify the notations, we Token-to-token attention. With the region-to-region rout-
discuss the case of single-head self-attention with a single ing index matrix Ir , we can then apply fine-grained token-
input, although we use multi-head self-attention [42] with to-token attention. For each query token in region i, it will
batched input in practice. The whole algorithm is summa- attend to all key-value pairs residing in the union of k routed
rized with Pytorch-like [32] pseudo code in Algorithm 1. regions indexed with Ir(i,1) , Ir(i,2) , ..., Ir(i,k) . However, it is
We give a detailed explanation as follows. non-trivial to implement this step efficiently, as these routed
regions are expected to be scattered over the whole feature
Region partition and input projection. Given a 2D input map, while modern GPUs rely on coalesced memory opera-
feature map X ∈ RH×W ×C , we start by dividing it into tions that load blocks of dozens of contiguous bytes at once.
S×S non-overlapped regions such that each region contains We thus gather key and value tensor first, i.e.,
HW
S 2 feature vectors. This step is done by reshaping X as
2 HW
Xr ∈ RS × S2 ×C . We then derive the query, key, value Kg = gather(K, Ir ), Vg = gather(V, Ir ), (6)
2 HW
tensor, Q, K, V ∈ RS × S2 ×C , with linear projections: where Kg , Vg ∈ RS ×C 2
× kHW
are gathered key and value
S2

Q = Xr W q , K = Xr W k , V = Xr W v , (3) tensor. We can then apply attention on the gathered key-

q k v C×C
value pairs as:
where W , W , W ∈ R are projection weights for
the query, key, value, respectively. O = Attention(Q, Kg , Vg ) + LCE(V). (7)

4
Here, we introduce a local context enhancement term We instantiate BiFormer with 3 different model sizes by
LCE((V) as in [37]. Function LCE(·) is parametrized with scaling the network width (i.e., the number of base channels
a depth-wise convolution, and we set the kernel size to 5. C) and depth (i.e., the number of BiFormer blocks used in
each stage, Ni , i = 1, 2, 3, 4), as listed in Table 1. They
3.3. Complexity Analysis of BRA share other configurations. We set each attention head to 32
The proposed bi-level routing attention enables direct channels, and MLP expansion ratio e=3. For BRA, we use
long-range dependency modeling similar to vanilla atten- topk = 1, 4, 16, S 23 for the 4 stages, and region partition
tion. However, we show here that BRA has a much lower factor S = 7/8/16 for classification/semantic segmenta-
4
complexity of O((HW ) 3 ) with a proper region partition tion/object detection task, due to different input resolutions.
factor S compared to vanilla attention, which has a com-
plexity of O((HW )2 ), and to quasi-global axial atten- Models #Channels. #Blocks Params FLOPs
3
tion [14, 22], which has a complexity of O((HW ) 2 ). BiFormer-T 64 [2, 2, 8, 2] 13M 2.2G
The computation of BRA consists of three parts: linear BiFormer-S 64 [4, 4, 18, 4] 26M 4.5G
projection, region-to-region routing, and token-to-token at- BiFomrer-B 96 [4, 4, 18, 4] 57M 9.8G
tention. The total amount of computations is therefore:
Table 1. Network width and depth of different model variants. The
FLOPs = FLOPsproj + FLOPsrouting + FLOPsattn FLOPs are calculated with 224 × 224 input.
HW
= 3HW C 2 + 2(S 2 )2 C + 2HW k 2 C
S
2 4 k(HW )2 k(HW )2 FLOPs Params Top-1 Acc.
= 3HW C + C(2S + 2
+ ) Model
S S2 (G) (M) (%)
k(HW )2 k(HW )2 1 ResNet-18 [19] 1.8 11.7 69.8
≥ 3HW C 2 + 3C(2S 4 · · )3
S2 S2 RegNetY-1.6G [34] 1.6 11.2 78.0
2 4
= 3HW C 2 + 3Ck 3 (2HW ) 3 , PVTv2-b1 [45] 2.1 13.1 78.7
(8) Shunted-T [37] 2.1 11.5 79.8
where C is the token embedding dimension (i.e., number of QuadTree-B-b1 [38] 2.3 13.6 80.0
channels of the feature map), and k is the number of regions BiFormer-T 2.2 13.1 81.4
to attend (“k” in “top-k”). Here, the inequality of arith- Swin-T [29] 4.5 29 81.3
metic and geometric means has been applied. The equality CSWin-T [14] 4.5 23 82.7
)2
in Eq. 8 holds if and only if 2S 4 = k(HW
S2 . Therefore: DAT-T [48] 4.6 29 82.0
CrossFormer-S [46] 5.3 31 82.5
k 1 RegionViT-S [2] 5.3 31 82.6
S = ( (HW )2 ) 6 . (9)
2 QuadTree-B-b2 [38] 4.5 24 82.7
4 MaxViT-T [41] 5.6 31 83.6
In other words, BRA achieves O((HW ) 3 ) complexity if
ScalableViT-S [50] 4.2 32 83.1
we scale the region partition factor S w.r.t. the input resolu-
Uniformer-S* 4.2 24 83.4
tion according to Eq. 9. Wave-ViT-S* [51] 4.7 23 83.9
3.4. Architecture Design of BiFormer BiFormer-S 4.5 26 83.8
BiFormer-S* 4.5 26 84.3
Using BRA as a basic building block, we propose a new
Swin-B [29] 15.4 88 83.5
general vision transformer, BiFormer. As shown in Fig-
CSWin-B [14] 15.0 78 84.2
ure 3, we follow the recent state-of-the-art vision transform-
CrossFormer-L [46] 16.1 92 84.0
ers [14,29,41] to use a four-stage pyramid structure. Specif- ScalableViT-B [50] 8.6 81 84.1
ically, in stage i, we use an overlapped patch embedding in Uniformer-B* [25] 8.3 50 85.1
the first stage and a patch merging module [25, 37] in the Wave-ViT-B* [51] 7.2 34 84.8
second to fourth stages to reduce the input spatial resolu- BiFormer-B 9.8 57 84.3
tion while increasing the number of channels, followed by BiFormer-B* 9.8 58 85.4
Ni consecutive BiFormer blocks to transform the features.
In each BiFormer block, we follow recent works [7, 25, 41]
Table 2. Comparison of different backbones on ImageNet-1K.
to use a 3 × 3 depthwise convolution at the beginning to en- All models are trained and evaluated on images of resolution
code relative position information implicitly. We then apply 224 × 224. “*” indicates that the model is trained with token la-
a BRA module and 2-layer MLP module with expansion ra- beling [23]. Methods are grouped by the amount of computations.
tio e sequentially for cross-location relation modeling and
per-location embedding, respectively. 3 In the final stage, topk = S 2 means that we use full self-attention.

5
 +
Input: Stage 1: Stage 2: Stage 3: Stage 4:
MLP

LN

Patch Embedding

+
Patch Merging

Patch Merging
Patch Merging
BiFormer BiFormer BiFormer BiFormer Bi-level Routing
Attention
Block Block Block Block
LN

+
DWConv 3x3

Figure 3. Left: The overall architecture of our BiFormer. Refer to Table 1 for configurations. Right: Details of a BiFormer Block.

4. Experiments ter than the most competitive QuadTree-b1 [38]. For mod-
els in the second group (∼4G FLOPs), BiFormer-S achieves
We evaluate the effectiveness of our proposed BiFormer 83.8% top-1 accuracy. To the best of our knowledge, this is
experimentally on a series of mainstream computer vision the best result without extra training data or training tricks.
tasks including image classification (Sec. 4.1), object de- In addition, using the distillation technique named token
tection and instance segmentation (Sec. 4.2), and semantic labeling [23], the accuracy of BiFormer-S can be further
segmentation (Sec. 4.3). Specifically, we train from scratch boosted to 84.3%, which implies that there is a huge po-
on ImageNet1K [12] for image classification. We then fine- tential for the proposed architecture. For models in the
tune the pretrained backbones on COCO [28] for object de- largest group (∼10G FLOPs), BiFormer-B achieves an even
tection and instance segmentation, and on ADE20K [55] better performance than those of existing models with the
for semantic segmentation. Additionally, we conduct ab- amount of computations reaching up to ∼16G FLOPs, such
lation study to verify the effectiveness of the proposed bi- as Swin-B [29], CSWin-B [14] and CrossFormer-L [46].
level routing attention and other architecture design choices
of BiFormer in Sec. 4.4. Finally, to verify query-adaptive, 4.2. Object Detection and Instance Segmentation
sparse patterns are achieved by bi-level routing attention,
we visualize the attention map in Sec. 4.5. Settings. We evaluate the models for object detection and
instance segmentation on COCO 2017 [28]. For a fair com-
4.1. Image Classification on ImageNet-1K parison, all experiments are conducted with the MMDetec-
tion [3] toolbox. RetinaNet [27] and Mask R-CNN [18]
Settings. We conduct image classification experiments on frameworks are used for object detection and instance seg-
the ImageNet-1K [12] dataset, following the experimental mentation, respectively. Before training on COCO, we ini-
settings of DeiT [40] for fair comparison. Specifically, each tialize the backbone with weights pretrained on ImageNet-
model is trained 300 epochs with input size of 224 × 224. 1K, while leaving all other layers randomly initialized.
We take AdamW as the optimizer with weight decay of The models are trained with the standard 1× schedule (12
0.05, and apply cosine decay learning rate schedule with epochs) provided by MMDetection, except that we use the
an initial learning rate of 0.001, while the first 5 epochs AdamW optimizer [30], instead of SGD. We use an initial
are utilized for linear warm-up [16]. The batch size is learning rate of 1e − 4, and a batch size of 16, while the
set to 1024. To avoid overfitting, we apply regularization weight decay is set as 1e − 4 and 5e − 2 for RetinaNet and
techniques including RandAugment [9] (rand-m9-mstd0.5- Mask R-CNN, respectively. During training, we resize the
inc1), MixUp [54] (prob = 0.8), CutMix [52] (prob = 1.0), input images by fixing the shorter side to 800 pixels while
Random Erasing (prob = 0.25), and increasing stochas- keeping the longer side not exceeding 1,333 pixels.
tic depth [21] (prob = 0.1/0.15/0.4 for BiFormer-T/S/B, Results. We list results in Table 3. For object detection
respectively). To fairly compare the models trained with with RetinaNet, we report mean Average Precision (mAP ),
token labeling [23], including Uniformer [25] and Wave- Average Precision (AP ) at different IoU thresholds (50%,
ViT [51], we also provide a version trained with the same 75%) and for three object sizes (i.e. small, medium, and
recipe provided by WaveViT. large (S/M/L)). From the results, we can see that while
Results. We compare our method with several closely re- the overall performance of BiFormer is only comparable to
lated methods and/or recent state-of-the-arts. Quantitative some most competitive existing methods, such as WaveViT
results are listed in Table 2, where models are grouped by and QuadTree-B, the performance on small objects (APM )
the amount of computations (FLOPs). In all 3 groups, our outperforms these methods significantly. This may be be-
model consistently outperforms other compared ones. For cause the BRA saves computations via sparse sampling in-
example, for models in the smallest group (∼2G FLOPs), stead of downsampling. Hence, it preserves fine-grained de-
our BiFormer-T achieves 81.4% top-1 accuracy, 1.4% bet- tails, which are crucial for small objects. For instance seg-

6
 RetinaNet 1× schedule Mask R-CNN 1× schedule
Backbone
mAP AP50 AP75 APS APM APL mAP b b
AP50 b
AP75 mAP m AP50 m m
AP75
Swin-T [29] 41.5 62.1 44.2 25.1 44.9 55.5 42.2 64.6 46.2 39.1 61.6 42.0
DAT-T [48] 42.8 64.4 45.2 28.0 45.8 57.8 44.4 67.6 48.5 40.4 64.2 43.1
CSWin-T [14] - - - - - - 46.7 68.6 51.3 42.2 65.6 45.4
CrossFormer-S [46] 44.4 55.3 38.6 19.3 40.0 48.8 45.4 68.0 49.7 41.4 64.8 44.6
QuadTree-B2 [38] 46.2 67.2 49.5 29.0 50.1 61.8 - - - - - -
WaveViT-S* [51] 45.8 67.0 49.4 29.2 50.0 60.8 46.6 68.7 51.2 42.4 65.5 45.8
BiFormer-S 45.9 66.9 49.4 30.2 49.6 61.7 47.8 69.8 52.3 43.2 66.8 46.5
Swin-S [29] 44.5 65.7 47.5 27.4 48.0 59.9 44.8 66.6 48.9 40.9 63.4 44.2
DAT-S [48] 45.7 67.7 48.5 30.5 49.3 61.3 47.1 69.9 51.5 42.5 66.7 45.4
CSWin-S [14] - - - - - - 47.9 70.1 52.6 43.2 67.1 46.2
CrossFormer-B [46] 46.2 67.8 49.5 30.1 49.9 61.8 47.2 69.9 51.8 42.7 66.6 46.2
QuadTree-B3 [38] 47.3 68.2 50.6 30.4 51.3 62.9 - - - - - -
Wave-ViT-B* [51] 47.2 68.2 50.9 29.7 51.4 62.3 47.6 69.1 52.4 43.0 66.4 46.0
BiFormer-B 47.1 68.5 50.4 31.3 50.8 62.6 48.6 70.5 53.8 43.7 67.6 47.1

Table 3. Comparison based on the object detection (left group) and instance segmentation (right group) tasks, on the COCO 2017 dataset.

S-FPN Upernet Sparse Attention IN1K ADE20K

Backbone
mIoU(%) mIoU(%) MS mIOU(%) Top1(%) mIoU(%)
Swin-T [29] 41.5 44.5 45.8
Sliding window [35] 81.4 -
DAT-T [48] 42.6 45.5 46.4
CSWin-T [14] 48.2 49.3 50.7 Shifted window [29] 81.3 41.5
CrossFormer-S [46] 46.0 47.6 48.4 Spatially Sep [7] 81.5 42.9
Shunted-S [37] 48.2 48.9 49.9 Sequential Axial [20] 81.5 39.8
WaveViT-S* [51] - - 49.6 Criss-Cross [22] 81.7 43.0
BiFormer-S 48.9 49.8 50.8 Cross-shaped window [14] 82.2 43.4
Swin-S [29] - 47.6 49.5 Deformable [48] 82.0 42.6
DAT-S [48] 46.1 48.3 49.8 Block-Grid [41] 81.8 42.8
CSWin-S [14] 49.2 50.4 51.5 Bi-level Routing 82.7 44.8
CrossFormer-B [46] 47.7 49.7 50.6
Uniformer-B [25] 48.0 50.0 50.8 Table 5. Ablation study on different attention mechanisms. All
WaveViT-B* [51] - - 51.5 models follow the architecture design of the Swin-T model.
BiFormer-B 49.9 51.0 51.7
the same setting as Swin Transformer [29] to train the model
Table 4. Comparison based on semantic segmentation with two
160k iterations.
segmentation heads (Semantic FPN and UpperNet), on ADE20K.
Results. Table 4 shows the results of the two different
frameworks. It shows that with the Semantic FPN frame-
mentation with Mask R-CNN, we report bounding box and work, our BiFormer-S/B achieves 48.9/49.9 mIoU, respec-
mask Average Precision (AP b and AP m ) at different IoU tively, improving CSWin-T/S by 0.7 mIoU. A similar per-
thresholds (50%, 75%). As shown in Table 3, our method formance gain for the UperNet framework is also observed.
shows a clear advantage in this task on all metrics.
4.4. Ablation Study
4.3. Semantic Segmentation on ADE20K
The effectiveness of BRA. We compare BRA with several
Settings. Following existing works, we conduct our seman- existing sparse attention mechanisms. Following [14], we
tic segmentation experiments on the ADE20K [55] dataset align macro architecture designs with Swin-T [29] for a fair
based on MMSegmentation [8]. We do comparisons under comparison. Specifically, we use 2, 2, 6, 2 blocks for the
both Semantic FPN [24] and UperNet [49] frameworks. In four stages, non-overlapped patch embedding, set the initial
both cases, the backbone is initialized with ImageNet-1K patch embedding dimension C = 96 and MLP expansion
pretrained weights, and other layers use random initializa- ratio e = 4. The results are reported in Table 5. Our bi-
tion. Models are optimized with the AdamW optimizer and level routing attention has significantly better performance
the batch size is set as 32. For a fair comparison, our Se- than existing sparse attention mechanisms, in terms of both
mantic FPN experiments use the same setting as PVT [44] image classification and semantic segmentation.
to train the model 80k steps. Our Upernet experiments use Other architecture design choices. Using the Swin-T lay-

7
Figure 4. Visualization of the attention maps for two scenes. For each scene, we visualize two query positions on the input image (left),
corresponding routed regions (middle), and a final attention heatmap (right).

out as the baseline, we present a summary of other mod- regions cover the same or similar entities. In the second in-
ifications that we have applied, which further boost our door scene, when we place the query position on the mouse,
BiFormer-S model to state-of-the-art performances on the the routed regions contain part of the host, keyboard, and
ImageNet-1K dataset. These modifications include: (1) re- display, even though these regions are not adjacent to each
placing non-overlapped patch embedding [29] with over- other. This implies that our bi-level routing attention can
lapped one [14,37,45], (2) using deeper layout (i.e. stacking capture long-range inter-object relationships.
more blocks in each stage, while reducing the base chan-
nels from 96 to 64 and MLP expansion ratio from 4 to 3 to 5. Limitation and Future Work
keep similar FLOPs.), (3) adding convolution position en-
Compared to sparse attention with simple static patterns,
coding [7, 25] at the beginning of the BiFormer blocks, and
we introduce an extra step to locate the regions to attend,
(4) applying token labeling [23, 25, 51] training technique.
where we build and prune a region-level graph and gather
As shown in Table 6, simply using a deeper layout can im-
key-value pairs from the routed regions. While this step
prove the performance significantly. However, this factor is
does not incur much computation as it operates at a coarse
usually not discussed in existing works.
region level, it inevitably incurs extra GPU kernel launch
and memory transactions. Hence, BiFormer has lower
Architecture design Params FLOPs IN1K Top1
throughput than some existing models with similar FLOPs
(M) (G) (%)
on GPU due to overheads of kernel launch and memory bot-
Baseline (Swin-T layout) 29 4.6 82.7 tleneck. Nonetheless, this problem can be mitigated via en-
+Overlapped patch emb. 31 4.9 82.8 (+0.1)
gineering efforts, such as GPU kernel fusion. We will ex-
+Deeper layout 25 4.5 83.5 (+0.7)
+Convolution pos. enc. 26 4.5 83.8 (+0.3) plore efficient sparse attention and vision transformer with
+Token Labling 29 4.9 84.3 (+0.5) hardware awareness in our future works.

Table 6. Ablation path from Swin-T [29] layout architecture to 6. Conclusion

BiFormer-S. Note that the modifications are applied sequentially.
We propose bi-level routing attention to enable efficient
allocation of computations in a dynamic, query-aware man-
4.5. Visualization of Attention Map ner. The core idea of BRA is to filter out the most irrelevant
key-value pairs at a coarse region level. It is achieved by
To further understand how bi-level routing attention
first building and pruning a region-level directed graph, and
works, we visualize routed regions and attention response
then applying fine-grained token-to-token attention in the
w.r.t. query positions. For this visualization, we use the
union of routed regions. We have analyzed the computa-
routing indices and attention scores extracted from the final
tional complexity of BRA and demonstrated that it achieves
BiFormer block of the 3rd stage, which is the major stage 4
O((HW ) 3 ) with a proper region partition size. Using BRA
consuming most computations. We demonstrate two scenes
as the core building block, we propose BiFormer, a new vi-
in Figure 4. In both cases, we can clearly observe that se-
sion transformer that has shown superior performances on
mantically related regions are successfully located. For ex-
four popular vision tasks, image classification, object detec-
ample, in the first scene, which is a street view, if the query
tion, instance segmentation, and semantic segmentation.
position is on a building or a tree, the corresponding routed

8
Appendix Throupt comparison
Swin-T (4.5G FLOPs) 1079.5

1000 BiFormer-STL (4.6G FLOPs)

A. Discussion on Regional Representations QuadTree-STL (4.8G FLOPs)

In our proposed bi-level routing attention, we derive the 800 766.7

733.3
regional representations (Qr and Kr ) with average pooling

Throuput (image/s)
for region-to-region routing. We justify the choice here. 600
542.3
In fact, as the goal of region-to-region routing is to find
the most related tokens for token-to-token attention in the 400
next step, it is reasonable to maximize the average token- 321.4

to-token affinity scores between the two regions. However, 200

218.7
184.4 173.2
165.6
this is equivalent to maximizing the affinity score between 133.2

the average tokens of the two regions, because 0

27.5 28.8
FP32, train FP32, infer AMP, train AMP, Infer
P P
1 Qi j∈Ω0 Kj
XX
i∈Ω
0
Qi Kj = · , (10) Figure 5. Throughput comparison on a 32GB Tesla V100 GPU.
|Ω| · |Ω | 0
|Ω| |Ω0 | The suffix “STL” denotes Swin-T Layout, which means we use
i∈Ω j∈Ω
Swin-T [29] backbone with only attention module being replaced.
where we denote the set of token indices of the two regions We report results under both FP32 precision and automatic mixed
precision (AMP) modes.
with Ω and Ω0 .

S k #tokens to attend Acc im/s (FP32)

B. Throughput Comparison
7 1,4,16,49 64,64,64,49 82.7 522.3
To demonstrate the computation efficiency of the pro- 7 1,2,8,32 64,32,32,32 82.4 563.2
posed bi-level routing attention, we compare the through- 7 2,8,32,49 128,128,128,49 82.6 419.9
8,4,2,1 2,2,2,1 98,98,98,49 82.3 606.2
puts of models using different attention mechanisms.
Specifically, we replace the shift window attention mod- Table 7. Ablation study on top-k and partition factor S.
ules in Swin-T [29] with quad-tree attention [38] modules
to form QuadTree-STL, and with our bi-level routing at-
tention modules to form BiFormer-STL. We then use the
C. Choices of top-k and partition factor S
widely used timm [47] script to benchmark the training and
inference throughput on a 32 GB Tesla V100 GPU with a In the paper, S and k were chosen more with considera-
batch size of 128 and image resolution of 224 × 224. tion of engineering issues. (1) S is chosen as a divisor of the
As shown in Figure 5, Swin-T has the highest through- training size to avoid padding, which slows down the train-
put due to its simplicity. Switching to our bi-level rout- ing and may also degrade the performance. For example, in
ing attention(BRA), the training and inference throughput image classification where the resolution is 224 = 7 × 32,
of BiFormer-STL decrease by ∼30% and ∼40% respec- we use S = 7 so that it is a divisor of the size of fea-
tively in comparison with Swin-T. This is caused by ex- ture maps in every stage. This is similar to SWinTrans-
tra GPU kernel launch and memory transactions caused by former [29], which uses a window size of 7. (2) In dense
the routing process (i.e. locating the regions to attend and prediction tasks, we use larger S to balance the complexity
gather key-value pairs). Nonetheless, BiFormer-STL is still of region-level routing and token-level attention to achieve
3× ∼ 6× faster than QuadTree-STL. This is due to that overall lower complexity. One can find hints from Eq. 9 of
on the one hand the recursive nature of quad-tree attention the paper, though we do not strictly follow the scaling rule
hurts the parallelism, on the other hand quad-tree attention due to the size divisor constraint. (3) We gradually increase
relies on sparse matrix multiplications which are inefficient k to keep a reasonable number of tokens to attend as the
on GPUs, while our BRA can be efficiently implemented region size becomes smaller in later stages.
with key-value token gathering followed by GPU-friendly It is possible to try different combinations of S and k.
dense matrix multiplications. We show ablation results on IN-1K in Table 7, based on
It is worth noting that, the overheads of both memory BiFormer-STL (as in the paper). A key observation from
transactions and kernel launch incurred by the routing pro- these experiments is that increasing the number of tokens to
cess can be reduced via engineering efforts such as GPU attend may even hurt the accuracy. This implies the explicit
kernel fusion. We leave this optimization to our future sparsity constraint may serve as a regularization to avoid
work. distractions from the background.

9
Figure 6. More attention map visualization results. For each scene, We demonstrate 2-3 query positions on the input image (left), corre-
sponding routed regions (middle) and final attention heat map (right).

10
D. Adapting Pretrained Plain ViT with BRA [2] Chun-Fu Chen, Rameswar Panda, and Quanfu Fan. Region-
vit: Regional-to-local attention for vision transformers. In
Recently, to take advantage of large-scale pretrain- The Tenth International Conference on Learning Represen-
ing with masked image modeling, a new research direc- tations, ICLR 2022, Virtual Event, April 25-29, 2022. Open-
tion emerges to adapt plain ViT [15] for dense predic- [Link], 2022. 5
tion tasks [4, 26]. Here we explore adapting pre-trained [3] Kai Chen, Jiaqi Wang, Jiangmiao Pang, Yuhang Cao, Yu
plain ViT [15] for semantic segmentation with our proposed Xiong, Xiaoxiao Li, Shuyang Sun, Wansen Feng, Ziwei Liu,
BRA. Jiarui Xu, et al. Mmdetection: Open mmlab detection tool-
Specifically, we replace all or part of full multi-head self- box and benchmark. arXiv:1906.07155, 2019. 6
attention (MHSA) modules in DeiT-B [40] with our BRA [4] Zhe Chen, Yuchen Duan, Wenhai Wang, Junjun He, Tong
and directly load the weights pre-trained on ImageNet be- Lu, Jifeng Dai, and Yu Qiao. Vision transformer adapter for
dense predictions. arXiv preprint arXiv:2205.08534, 2022.
fore training on ADE20K dataset for semantic segmenta-
11
tion. In this way, the linear projection weights of BRA [5] Zhiyang Chen, Yousong Zhu, Chaoyang Zhao, Guosheng
modules are initialized with those of the original MHSA. Hu, Wei Zeng, Jinqiao Wang, and Ming Tang. Dpt: De-
We compare such an adaptation with those proposed in [26], formable patch-based transformer for visual recognition. In
i.e. using local window attention (window size w = 14) to- Proceedings of the 29th ACM International Conference on
gether with several global attention or convolution propaga- Multimedia, pages 2899–2907, 2021. 1, 3
tion blocks. We set window size w = 4 (which is equivalent [6] Rewon Child, Scott Gray, Alec Radford, and Ilya
to region partition size S = 8 since the feature map has a Sutskever. Generating long sequences with sparse transform-
resolution of 32 × 32) and the number of regions to attend ers. arXiv:1904.10509, 2019. 1, 3
k = 12, hence each query attends to 42 × 12 = 192 key- [7] Xiangxiang Chu, Zhi Tian, Yuqing Wang, Bo Zhang, Haib-
value pairs, which is comparable to the local window atten- ing Ren, Xiaolin Wei, Huaxia Xia, and Chunhua Shen.
tion where each query attends to 14 × 14 = 196 key-value Twins: Revisiting the design of spatial attention in vision
transformers. Advances in Neural Information Processing
pairs.
Systems, 34:9355–9366, 2021. 5, 7, 8
Table 8 shows the results. Without propagation blocks, [8] MMSegmentation Contributors. Openmmlab semantic seg-
the architecture using BRA significantly surpasses the one mentation toolbox and benchmark. [Link]
with local window attention by 2.4 mAP. When further com/open-mmlab/mmsegmentation, 2020. 7
equipped with 4 global propagation blocks, the performance [9] Ekin D Cubuk, Barret Zoph, Jonathon Shlens, and Quoc V
of both architectures is improved, while the one using BRA Le. Randaugment: Practical automated data augmenta-
still has an advantage of 0.2 mAP. tion with a reduced search space. In Proceedings of the
IEEE/CVF Conference on Computer Vision and Pattern
attention function mIoU(%) Recognition workshops, pages 702–703, 2020. 6
[10] Jifeng Dai, Haozhi Qi, Yuwen Xiong, Yi Li, Guodong
local window attention (w = 14) 43.55 Zhang, Han Hu, and Yichen Wei. Deformable convolutional
BRA(w = 4, k = 12) 45.92 networks. In Proceedings of the IEEE International Confer-
local window attention + 4 conv prop. blks. 44.68 ence on Computer Vision, pages 764–773, 2017. 2
local window attention + 4 global prop. blks. 46.64 [11] Zihang Dai, Zhilin Yang, Yiming Yang, Jaime G. Carbonell,
BRA + 4 global prop. blks. 46.84 Quoc Viet Le, and Ruslan Salakhutdinov. Transformer-xl:
Attentive language models beyond a fixed-length context. In
Anna Korhonen, David R. Traum, and Lluı́s Màrquez, ed-
Table 8. Adapting pretrained ViT [15] with BRA for semantic seg- itors, Proceedings of the Conference of the Association for
mentation on ADE20K. For decoder, we use the Simple Feature Computational Linguistics, ACL 2019, Volume 1: Long Pa-
Pyramid [26] followed by with Upernet [49] head. pers, pages 2978–2988, 2019. 3
[12] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li,
and Li Fei-Fei. Imagenet: A large-scale hierarchical image
E. More Visualization Results database. In 2009 IEEE Conference on Computer Vision and
Pattern Recognition, pages 248–255, 2009. 6
To further show how BRA works, we demonstrate more [13] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina
visualization results in Figure 6. Toutanova. BERT: Pre-training of deep bidirectional trans-
formers for language understanding. In Proceedings of the
References Conference of the North American Chapter of the Associa-
tion for Computational Linguistics: Human Language Tech-
[1] Nicolas Carion, Francisco Massa, Gabriel Synnaeve, Nicolas nologies, Volume 1 (Long and Short Papers), pages 4171–
Usunier, Alexander Kirillov, and Sergey Zagoruyko. End-to- 4186, June 2019. 1, 3
end object detection with transformers. In European Confer- [14] Xiaoyi Dong, Jianmin Bao, Dongdong Chen, Weiming
ence on Computer Vision, pages 213–229, 2020. 1, 3 Zhang, Nenghai Yu, Lu Yuan, Dong Chen, and Baining

11
 Guo. Cswin transformer: A general vision transformer [27] Tsung-Yi Lin, Priya Goyal, Ross Girshick, Kaiming He, and
backbone with cross-shaped windows. In Proceedings of Piotr Dollár. Focal loss for dense object detection. In Pro-
the IEEE/CVF Conference on Computer Vision and Pattern ceedings of the IEEE International Conference on Computer
Recognition, pages 12124–12134, 2022. 1, 2, 3, 4, 5, 6, 7, 8 Vision, pages 2980–2988, 2017. 6
[15] Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, [28] Tsung-Yi Lin, Michael Maire, Serge Belongie, James Hays,
Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Pietro Perona, Deva Ramanan, Piotr Dollár, and C Lawrence
Mostafa Dehghani, Matthias Minderer, Georg Heigold, Syl- Zitnick. Microsoft coco: Common objects in context. In
vain Gelly, Jakob Uszkoreit, and Neil Houlsby. An image is European conference on computer vision, pages 740–755.
worth 16x16 words: Transformers for image recognition at Springer, 2014. 6
scale. In International Conference on Learning Representa- [29] Ze Liu, Yutong Lin, Yue Cao, Han Hu, Yixuan Wei, Zheng
tions, ICLR 2021, 2021, 2021. 1, 3, 11 Zhang, Stephen Lin, and Baining Guo. Swin transformer:
[16] Priya Goyal, Piotr Dollár, Ross Girshick, Pieter Noord- Hierarchical vision transformer using shifted windows. In
huis, Lukasz Wesolowski, Aapo Kyrola, Andrew Tulloch, Proceedings of the IEEE/CVF International Conference on
Yangqing Jia, and Kaiming He. Accurate, large minibatch Computer Vision, pages 10012–10022, 2021. 1, 2, 3, 4, 5, 6,
sgd: Training imagenet in 1 hour. arXiv:1706.02677, 2017. 7, 8, 9
6 [30] Ilya Loshchilov and Frank Hutter. Decoupled weight decay
[17] Ankit Gupta, Guy Dar, Shaya Goodman, David Ciprut, and regularization. In 7th International Conference on Learning
Jonathan Berant. Memory-efficient transformers via top-k Representations, ICLR 2019, New Orleans, LA, USA, May
attention. In Nafise Sadat Moosavi, Iryna Gurevych, Angela 6-9, 2019. [Link], 2019. 6
Fan, Thomas Wolf, Yufang Hou, Ana Marasovic, and Sujith [31] Nvidia. How to access global memory efficiently in cuda
Ravi, editors, Proceedings of the Workshop on Simple and c/c++ kernels. https : / / developer . nvidia .
Efficient Natural Language Processing, 2021, pages 39–52, com / blog / how - access - global - memory -
2021. 2 efficiently - cuda - c - kernels/. Accessed:
[18] Kaiming He, Georgia Gkioxari, Piotr Dollár, and Ross Gir- 2022-10-25. 2
shick. Mask r-cnn. In Proceedings of the IEEE International
[32] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer,
Conference on Computer Vision, pages 2961–2969, 2017. 6
James Bradbury, Gregory Chanan, Trevor Killeen, Zeming
[19] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.
Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An
Deep residual learning for image recognition. In Proceed-
imperative style, high-performance deep learning library. In
ings of the IEEE Conference on Computer Vision and Pattern
Proceedings of Advances in Neural Information Processing
Recognition, pages 770–778, 2016. 5
Systems, volume 32, 2019. 4
[20] Jonathan Ho, Nal Kalchbrenner, Dirk Weissenborn, and Tim
[33] Alec Radford, Karthik Narasimhan, Tim Salimans, and Ilya
Salimans. Axial attention in multidimensional transformers.
Sutskever. Improving language understanding by generative
arXiv:1912.12180, 2019. 7
pre-training. 2018. 1
[21] Gao Huang, Yu Sun, Zhuang Liu, Daniel Sedra, and Kilian
[34] Ilija Radosavovic, Raj Prateek Kosaraju, Ross Girshick,
Weinberger. Deep networks with stochastic depth. In Euro-
Kaiming He, and Piotr Dollár. Designing network design
pean Conference on Computer Vision, pages 646–661, 2016.
spaces. In Proceedings of the IEEE/CVF Conference on
6
Computer Vision and Pattern Recognition, pages 10428–
[22] Zilong Huang, Xinggang Wang, Lichao Huang, Chang
10436, 2020. 5
Huang, Yunchao Wei, and Wenyu Liu. Ccnet: Criss-cross
attention for semantic segmentation. In Proceedings of the [35] Prajit Ramachandran, Niki Parmar, Ashish Vaswani, Irwan
IEEE/CVF International Conference on Computer Vision, Bello, Anselm Levskaya, and Jon Shlens. Stand-alone self-
pages 603–612, 2019. 5, 7 attention in vision models. In Proceedings of Advances in
[23] Zi-Hang Jiang, Qibin Hou, Li Yuan, Daquan Zhou, Yujun Neural Information Processing Systems, volume 32, 2019. 7
Shi, Xiaojie Jin, Anran Wang, and Jiashi Feng. All tokens [36] Mr D Murahari Reddy, Mr Sk Masthan Basha, Mr M Chin-
matter: Token labeling for training better vision transform- naiahgari Hari, and Mr N Penchalaiah. Dall-e: Creating im-
ers. Advances in Neural Information Processing Systems, ages from text. 2021. 1
34:18590–18602, 2021. 2, 5, 6, 8 [37] Sucheng Ren, Daquan Zhou, Shengfeng He, Jiashi Feng, and
[24] Alexander Kirillov, Ross Girshick, Kaiming He, and Piotr Xinchao Wang. Shunted self-attention via multi-scale token
Dollár. Panoptic feature pyramid networks. In Proceedings aggregation. In Proceedings of the IEEE/CVF Conference
of the IEEE/CVF Conference on Computer Vision and Pat- on Computer Vision and Pattern Recognition, pages 10853–
tern Recognition, pages 6399–6408, 2019. 7 10862, 2022. 5, 7, 8
[25] Kunchang Li, Yali Wang, Peng Gao, Guanglu Song, Yu Liu, [38] Shitao Tang, Jiahui Zhang, Siyu Zhu, and Ping Tan. Quadtree
Hongsheng Li, and Yu Qiao. Uniformer: Unified trans- attention for vision transformers. In The International Con-
former for efficient spatiotemporal representation learning. ference on Learning Representations, ICLR 2022, 2022,
arXiv:2201.04676, 2022. 5, 6, 7, 8 2022. 3, 5, 6, 7, 9
[26] Yanghao Li, Hanzi Mao, Ross Girshick, and Kaiming He. [39] Yi Tay, Mostafa Dehghani, Dara Bahri, and Donald Metzler.
Exploring plain vision transformer backbones for object de- Efficient transformers: A survey. ACM Computing Surveys
tection. arXiv preprint arXiv:2203.16527, 2022. 11 (CSUR), 2020. 3

12
[40] Hugo Touvron, Matthieu Cord, Matthijs Douze, Francisco equal: Human-centric visual analysis via token clustering
Massa, Alexandre Sablayrolles, and Hervé Jégou. Training transformer. In Proceedings of the IEEE/CVF Conference
data-efficient image transformers & distillation through at- on Computer Vision and Pattern Recognition, pages 11101–
tention. In International Conference on Machine Learning, 11111, 2022. 3
pages 10347–10357. PMLR, 2021. 2, 6, 11 [54] Hongyi Zhang, Moustapha Cissé, Yann N. Dauphin, and
[41] Zhengzhong Tu, Hossein Talebi, Han Zhang, Feng Yang, David Lopez-Paz. mixup: Beyond empirical risk minimiza-
Peyman Milanfar, Alan Bovik, and Yinxiao Li. Maxvit: tion. In International Conference on Learning Representa-
Multi-axis vision transformer. In ECCV, 2022. 1, 2, 3, 4, tions, ICLR 2018, 2018. 6
5, 7 [55] Bolei Zhou, Hang Zhao, Xavier Puig, Tete Xiao, Sanja Fi-
[42] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszko- dler, Adela Barriuso, and Antonio Torralba. Semantic under-
reit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia standing of scenes through the ade20k dataset. International
Polosukhin. Attention is all you need. Advances in neural Journal of Computer Vision, 127(3):302–321, 2019. 6, 7
information processing systems, 30, 2017. 1, 3, 4
[43] Sinong Wang, Belinda Z Li, Madian Khabsa, Han Fang, and
Hao Ma. Linformer: Self-attention with linear complexity.
arXiv:2006.04768, 2020. 3
[44] Wenhai Wang, Enze Xie, Xiang Li, Deng-Ping Fan, Kaitao
Song, Ding Liang, Tong Lu, Ping Luo, and Ling Shao.
Pyramid vision transformer: A versatile backbone for dense
prediction without convolutions. In Proceedings of the
IEEE/CVF International Conference on Computer Vision,
pages 568–578, 2021. 1, 7
[45] Wenhai Wang, Enze Xie, Xiang Li, Deng-Ping Fan, Kaitao
Song, Ding Liang, Tong Lu, Ping Luo, and Ling Shao. Pvt
v2: Improved baselines with pyramid vision transformer.
Computational Visual Media, 8(3):415–424, 2022. 5, 8
[46] Wenxiao Wang, Lu Yao, Long Chen, Binbin Lin, Deng Cai,
Xiaofei He, and Wei Liu. Crossformer: A versatile vision
transformer hinging on cross-scale attention. In Interna-
tional Conference on Learning Representations, ICLR, 2022.
1, 2, 3, 4, 5, 6, 7
[47] Ross Wightman. Pytorch image models. https :
/ / github . com / rwightman / pytorch - image -
models, 2019. 9
[48] Zhuofan Xia, Xuran Pan, Shiji Song, Li Erran Li, and Gao
Huang. Vision transformer with deformable attention. In
Proceedings of the IEEE/CVF Conference on Computer Vi-
sion and Pattern Recognition, pages 4794–4803, 2022. 1, 2,
3, 4, 5, 7
[49] Tete Xiao, Yingcheng Liu, Bolei Zhou, Yuning Jiang, and
Jian Sun. Unified perceptual parsing for scene understand-
ing. In Proceedings of the European conference on computer
vision (ECCV), pages 418–434, 2018. 7, 11
[50] Rui Yang, Hailong Ma, Jie Wu, Yansong Tang, Xuefeng
Xiao, Min Zheng, and Xiu Li. Scalablevit: Rethinking
the context-oriented generalization of vision transformer.
arXiv:2203.10790, 2022. 5
[51] Ting Yao, Yingwei Pan, Yehao Li, Chong-Wah Ngo, and Tao
Mei. Wave-vit: Unifying wavelet and transformers for visual
representation learning. In European Conference on Com-
puter Vision, pages 328–345. Springer, 2022. 5, 6, 7, 8
[52] Sangdoo Yun, Dongyoon Han, Seong Joon Oh, Sanghyuk
Chun, Junsuk Choe, and Youngjoon Yoo. Cutmix: Regular-
ization strategy to train strong classifiers with localizable fea-
tures. In Proceedings of the IEEE/CVF International Con-
ference on Computer Vision, pages 6023–6032, 2019. 6
[53] Wang Zeng, Sheng Jin, Wentao Liu, Chen Qian, Ping Luo,
Wanli Ouyang, and Xiaogang Wang. Not all tokens are

13