  Recently, Vision Transformer (ViT) has achieved promising performance in
image recognition and gradually serves as a powerful backbone in various vision
tasks. To satisfy the sequential input of Transformer, the tail of ViT first
splits each image into a sequence of visual tokens with a fixed length. Then
the following self-attention layers constructs the global relationship between
tokens to produce useful representation for the downstream tasks. Empirically,
representing the image with more tokens leads to better performance, yet the
quadratic computational complexity of self-attention layer to the number of
tokens could seriously influence the efficiency of ViT's inference. For
computational reduction, a few pruning methods progressively prune
uninformative tokens in the Transformer encoder, while leaving the number of
tokens before the Transformer untouched. In fact, fewer tokens as the input for
the Transformer encoder can directly reduce the following computational cost.
In this spirit, we propose a Multi-Tailed Vision Transformer (MT-ViT) in the
paper. MT-ViT adopts multiple tails to produce visual sequences of different
lengths for the following Transformer encoder. A tail predictor is introduced
to decide which tail is the most efficient for the image to produce accurate
prediction. Both modules are optimized in an end-to-end fashion, with the
Gumbel-Softmax trick. Experiments on ImageNet-1K demonstrate that MT-ViT can
achieve a significant reduction on FLOPs with no degradation of the accuracy
and outperform other compared methods in both accuracy and FLOPs.
