When Vision Transformers (ViTs) emerged, they revolutionized computer vision by treating images as sequences of patches, much like words in a sentence. However, this architectural shift introduced a severe computational tax: the self-attention mechanism scales quadratically with the number of tokens. As Yu et al. note in their work on Unified Visual Transformer Compression, this scaling behavior creates a massive computational overhead that complicates deployment on resource-constrained hardware.
To understand why this happens, consider how self-attention operates. If a standard $224 \times 224$ image is divided into $16 \times 16$ patches, it yields 196 tokens. The attention matrix requires computing $196 \times 196 = 38,416$ pairwise interactions. However, if we scale to a high-resolution $1024 \times 1024$ image—a necessity for tasks like medical imaging or remote sensing—the token count jumps to over 4,000, exploding the attention matrix to over 16 million entries. As Chu et al. point out in Twins: Revisiting the Design of Spatial Attention in Vision Transformers, this quadratic complexity makes standard self-attention prohibitively expensive for dense prediction tasks like object detection and semantic segmentation.
To bypass this bottleneck, researchers have developed three primary paradigms: token pruning, token merging, and linearized attention structures.
Token Pruning: Dropping Redundant Background
The most direct way to fix $O(N^2)$ scaling is to make $N$ smaller. Images contain massive spatial redundancy; a large expanse of blue sky or a blank wall contains very little unique information compared to the main subject. Token pruning algorithms identify and discard these uninformative tokens mid-way through the network.
[Input Image] ──> [Early Layers] ──> [Token Evaluator] ──> [Drop Uninformative Tokens] ──> [Deep Layers (Heavy Compute)]
In Evo-ViT: Slow-Fast Token Evolution for Dynamic Vision Transformer, Xu et al. introduced a selection strategy that routes highly informative "VIP" tokens through a full attention path, while updating background tokens via a fast, coarse path. This preserves the overall spatial structure while focusing the heavy computation only where it matters.
However, completely discarding tokens early in a network can be risky for downstream tasks like object detection, where a previously ignored background patch might contain a crucial detail. To solve this, Liu et al. proposed a Selective Vision Transformer in Revisiting Token Pruning for Object Detection and Instance Segmentation. Their architecture preserves pruned tokens in a memory bank, allowing them to "reactivate" in later layers if the evolving global context deems them necessary.
In multimodal settings, token importance can be guided by other modalities. For instance, Jiang et al. developed TRIPS: Efficient Vision-and-Language Pre-training with Text-Relevant Image Patch Selection, which leverages accompanying text to intelligently prune image patches that do not relate to the textual description, optimizing the visual backbone dynamically.
Token Merging: Conserving Information Without the Cost
While pruning throws tokens away, token merging seeks to combine similar tokens. This prevents information loss while still reducing the total token count $N$.
In Token Merging: Your ViT But Faster, Daniel Bolya demonstrated that similar tokens can be gradually matched and partitioned using a lightweight, parameter-free bipartite matching algorithm. By averaging the features of highly similar tokens rather than dropping them, the network maintains its mathematical expressivity without requiring retraining.
To make this process robust across diverse visual tasks without fine-tuning, Haurum et al. introduced Agglomerative Token Clustering. This method applies bottom-up hierarchical clustering to group redundant visual features dynamically. Alternatively, to optimize this process during training, Dong Hoon Lee developed Learning to Merge Tokens via Decoupled Embedding for Efficient Vision Transformers, utilizing a separate, lightweight embedding module to make the token selection and soft-merging process fully differentiable.
[Token A: Sky] \
[Token B: Sky] ──> [Merge Operator] ──> [Averaged Token: Sky (Weight=3)]
[Token C: Sky] /
However, token reduction strategies must be designed carefully to cooperate with modern hardware. As Lu et al. demonstrated in ToMA: Token Merge with Attention for Diffusion Models, naive token merging can sometimes conflict with highly optimized hardware kernels like FlashAttention, which rely on fixed block sizes. The authors show that hardware-aware token management is essential to translate theoretical FLOP reductions into actual wall-clock speedups.
Linearizing Attention and Structural Alternatives
Instead of reducing the number of input tokens, a third strategy alters the attention mechanism itself so that its complexity scales linearly, $O(N)$, with the sequence length.
One prominent approach is the use of proxy tokens for global routing. In PT-T2I/V: An Efficient Proxy-Tokenized Diffusion Transformer for Text-to-Image/Video-Task, Wang et al. replaced full global self-attention with a proxy mechanism. Local regions are summarized into a small set of averaged proxy tokens. These proxies handle long-range communication across the network, completely bypassing the need for every individual pixel patch to attend to every other pixel patch.
Another strategy breaks the global attention matrix into interleaved local and global components. The authors of Twins achieved this by alternating between locally-grouped self-attention (which looks only at neighboring patches) and globally-subsampled attention (which looks at a downsampled summary of the entire image). Similarly, Chang et al. proposed CoAtFormer: Vision Transformer with Composite Attention, which runs a linear-complexity spatial attention branch in parallel with a graph-based channel dependency branch to achieve global context at a fraction of the cost.
Finally, a growing contingent of researchers argues for replacing the self-attention mechanism entirely with alternative architectures that scale linearly by design. State Space Models (SSMs), such as Mamba, process inputs sequentially or via parallelizable scans that maintain a hardware-efficient hidden state. As detailed by Liu et al. in Vision Mamba: A Comprehensive Survey and Taxonomy, these architectures successfully capture long-range global dependencies with $O(N)$ complexity, offering a promising path forward for high-resolution visual synthesis and dense prediction tasks without the quadratic tax of traditional transformers.
Key Foundational Work
Evo-ViT: Slow-Fast Token Evolution for Dynamic Vision Transformer (2022) — contributed 1 concept elements to this direction.
Twins: Revisiting the Design of Spatial Attention in Vision Transformers (2021) — contributed 1 concept elements to this direction.
TRIPS: Efficient Vision-and-Language Pre-training with Text-Relevant Image Patch Selection (2022) — contributed 1 concept elements to this direction.