Vision Transformers are Circulant Attention Learners

AI summary

Overview

Research area: Efficient vision Transformer architectures — specifically, replacing dense self-attention with a structured, Fourier-accelerable attention operator for image classification, object detection, and semantic segmentation.

Technical level: Advanced. The paper assumes familiarity with self-attention, circulant/block-circulant matrices, the discrete Fourier transform, and the FFT algorithm, though the central idea (attention maps look like a structured pattern) is stated in plain terms.

Scope: The paper identifies that vision Transformer attention maps approximate Block Circulant matrices with Circulant Blocks (BCCB), and proposes "Circulant Attention" to explicitly enforce that structure for O(N log N) computation without substantially losing expressiveness.

What This Paper Is About

Standard self-attention compares every image token with every other token, which costs O(N²) and becomes impractical at high resolutions. Prior fixes hard-code handcrafted patterns (local windows, sparsity), which act as external constraints that damage long-range modeling. This paper instead shows that vision Transformers already learn a computationally efficient structure — attention maps that closely resemble BCCB matrices — and builds an attention module that computes directly in that structure using the 2D DFT.

Key Contributions

1. Discovery of an intrinsic efficient pattern. The authors reveal that self-attention maps in vision Transformers frequently approximate the Block Circulant matrix with Circulant Blocks (BCCB), a 2D generalization of the circulant matrix. They provide detailed analyses and visualizations of this phenomenon, including the near shift-invariance of attention distributions for adjacent query tokens.

2. Circulant Attention, an O(N log N) attention mechanism. They project the raw attention map onto its nearest BCCB matrix (the orthogonal projection in the BCCB subspace), and show that the resulting attention scores and output features can be computed via 2D DFT and its inverse, reducing complexity from O(N²) to O(N log N).

3. A token reweighting module. Because a BCCB/Softmax attention map forces both row sums and column sums to equal one, it cannot readily highlight salient tokens. The authors add an input-dependent, SiLU-gated reweighting factor T = SiLU(xW_T) applied either pre- or post-attention to restore capacity.

4. Broad empirical validation as a plug-in module. Circulant attention is inserted into DeiT (global attention), PVT (sparse attention), and Swin Transformer (local attention), plus a dedicated Circulant Attention Transformer (CAT) family, with results on ImageNet-1K, COCO, and ADE20K.

Main Findings

• Attention maps are nearly BCCB. Visualizations of 14×14 (N = H×W, H = W = 14) attention matrices from DeiT show near block-circulant patterns, and consecutive queries show convolution-like translation invariance.

• ImageNet-1K improvements across all three baselines. CA-DeiT-T reaches 75.0% top-1 versus DeiT-T's 72.2% (+2.8); CA-DeiT-S 81.0% versus 79.8 (+1.2); CA-DeiT-B 82.3% versus 81.8 (+0.5). CA-PVT-T improves 75.1 → 78.1 (+3.0), CA-PVT-S 79.8 → 81.7 (+1.9), CA-PVT-M 81.2 → 82.6 (+1.4), CA-PVT-L 81.7 → 82.9 (+1.2). CA-Swin-T 81.3 → 82.2 (+0.9), CA-Swin-S 83.0 → 83.6 (+0.6), CA-Swin-B 83.5 → 83.9 (+0.4) at 224², and 84.5 → 85.1 (+0.6) at 384².

• Parameter/FLOP efficiency. The paper reports that CA-PVT-S matches PVT-L's accuracy using 30% of the parameters and 40% of the FLOPs.

• COCO object detection. CA-PVT-S outperforms the larger PVT-L by 1.3 box AP with substantially fewer FLOPs, a larger gain than in classification. All CA variants beat their PVT and Swin counterparts on APᵇ and APᵐ, under both 1x and 3x schedules.

• ADE20K semantic segmentation. Circulant attention consistently improves PVT (with SemanticFPN) and Swin (with UperNet) backbones, with up to 3.7% mIoU gain at comparable or lower computation and parameters (e.g., PVT-T 35.7 → CA-PVT-T 39.4).

• Efficiency gains. CA-DeiT-T requires 8× fewer FLOPs at a 1536² image resolution, delivers a 7× speedup at 1536², and gives up to 1.5× faster inference at the default 224² resolution with improved performance (throughput measured on an RTX3090 GPU).

• Explicit BCCB structure costs little. In the ablation on DeiT-S, simply introducing circulant attention leads to a negligible 0.1% drop (79.8 → 79.7). Setting head dimension d = 1 improves accuracy to 80.2%; adding token reweighting reaches 80.9% (pre) and 81.0% (post), with post-reweighting adopted as the default. Token reweighting offers limited gains on the DeiT-S baseline itself.

• Theoretically cheaper. The stated cost is Ω(CA) = N(log₂N)(4d+2) + 4Nd versus Ω(SA) = 2N²d.

• Interpretable kernels. Because BCCB matrices correspond to 2D global convolution, the learned attention can be visualized as equivalent global convolution kernels; CA-DeiT produces diverse input-dependent kernels (bird-, wire-, local-, global-, half-plane-, strip-, and cross-shaped).

Methodology in Plain English

The starting observation is that when you look at attention maps learned by a vision Transformer, each block of the map is roughly a shifted copy of the previous one — the hallmark of a BCCB matrix. A BCCB matrix of size N×N (with N = H×W) is completely determined by its first row, and multiplying by it is mathematically the same as a 2D circular cross-correlation, i.e., a 2D convolution with circular padding. That operation can be done by transforming both operands with the 2D DFT, multiplying element-wise in the frequency domain, and transforming back — using FFT, this is O(N log N).

So the authors take the raw attention scores A = QKᵀ/√d and replace them with their nearest BCCB matrix Ã, defined as the orthogonal projection of A onto the BCCB subspace. Because the one-hot-row BCCB matrices form an orthogonal basis with ⟨Bₖ, Bₖ⟩ = N, the projection coefficients reduce to circular cross-correlations between Q and K. The first row of à turns out to be (1/(N√d))(Q ⊛ K)·1_(d×1), computed with 2D DFT. Softmax is applied to that first row to get σ(a), and since Softmax of a BCCB matrix is still BCCB, the output is simply O = σ(a) ⊛ V, again computed with 2D DFT and inverse DFT. Head-wise scaling and summation are handled as in vanilla attention.

The token reweighting module compensates for the fact that BCCB attention forces both row and column sums of the normalized map to one, which prevents certain keys from accumulating more total attention than others. An input-dependent factor T = SiLU(xW_T) is multiplied into V before attention (pre-reweighting) or into the output after attention (post-reweighting).

The module is a drop-in replacement: the authors swap the original attention in DeiT, PVT, and Swin, restricting the replacement to the first two stages in hierarchical models so that high-resolution feature maps can be processed directly at N log N cost. They also design a CAT model family. Training for ImageNet-1K uses 300 epochs, AdamW with cosine decay, a 20-epoch linear warmup, learning rate 1×10⁻³, weight decay 0.05, and RandAugment/Mixup/CutMix/random erasing, matching the baseline settings.

Why This Matters

Impact on research. The paper reframes efficiency in attention as a matter of exploiting structure the model already learns, rather than imposing new handcrafted constraints from the outside. This is a different design philosophy from window attention, sparse attention, or token downsampling, and it links vision Transformer attention directly to the classical signal-processing literature on circulant/BCCB matrices and the FFT. If attention is implicitly already circulant, then the expressive capacity usually "given up" for efficiency may not have to be given up at all.

Real-world applications.

• High-resolution image understanding, such as medical imaging and remote sensing, where the paper's 8× FLOP reduction and 7× speedup at 1536² resolution matter most.
• Dense prediction pipelines like autonomous driving perception and satellite mapping, where per-pixel segmentation and detection at large input sizes are the bottleneck.
• On-device or edge vision, where the throughput-accuracy trade-off at 224² translates into faster inference at fixed hardware budgets.
• Video and multimodal systems that process many tokens per frame, since the N log N scaling is favorable as token counts grow.

Industry relevance. Because circulant attention is presented as a plug-in module that improves DeiT, PVT, and Swin backbones (and, in the wider comparison, reaches 83.6/84.5/85.0 top-1 for CAT-T/CAT-S/CAT-B at 4.3G/7.9G/15.2G FLOPs), it is a relatively low-friction upgrade path for teams already operating these architectures rather than a wholesale replacement requiring new training recipes. The COCO and ADE20K results show the gains carry over to downstream deployment tasks, not just classification benchmarks.

Future Directions

• Extending beyond the first two stages. The authors restrict attention replacement to the first two stages of hierarchical models such as Swin and PVT; whether the same pattern and gains hold at every stage, or at even higher resolutions, is left open.

• Broadening architecture coverage. The study uses DeiT, PVT, and Swin as representatives of global, sparse, and local attention; testing circulant attention in other families (the comparison lists Mamba variants and hybrid models) would clarify how general the BCCB observation is.

• Refining the token reweighting design. Post-reweighting is adopted by default, but the authors note the mechanism only partially restores the ability to emphasize salient tokens that BCCB's row-and-column-sum constraint removes; further remedies for this capacity limitation are a natural next step.

• Understanding when the BCCB approximation breaks down. The projection in Eq. 9 always produces a nearest BCCB matrix, but no analysis is given of which inputs, tasks, or data distributions make the original attention map deviate most from BCCB, or how much accuracy that deviation costs.

Target Audience

Researchers and engineers working on efficient vision Transformer architectures, attention mechanism design, or high-resolution dense prediction. It is also valuable for readers interested in the intersection of deep learning and classical signal processing (FFT-based layers such as GFNet, FNO, AFNO, AFFNet), and for practitioners choosing attention modules for deployment-constrained vision systems. Readers without a background in structured matrices and DFT will need supplementary reading to follow Sections 3 and 4.

Authors’ abstract

The self-attention mechanism has been a key factor in the advancement of vision Transformers. However, its quadratic complexity imposes a heavy computational burden in high-resolution scenarios, restricting the practical application. Previous methods attempt to mitigate this issue by introducing handcrafted patterns such as locality or sparsity, which inevitably compromise model capacity. In this paper, we present a novel attention paradigm termed \textbf{Circulant Attention} by exploiting the inherent efficient pattern of self-attention. Specifically, we first identify that the self-attention matrix in vision Transformers often approximates the Block Circulant matrix with Circulant Blocks (BCCB), a kind of structured matrix whose multiplication with other matrices can be performed in $\mathcal{O}(N\log N)$ time. Leveraging this interesting pattern, we explicitly model the attention map as its nearest BCCB matrix and propose an efficient computation algorithm for fast calculation. The resulting approach closely mirrors vanilla self-attention, differing only in its use of BCCB matrices. Since our design is inspired by the inherent efficient paradigm, it not only delivers $\mathcal{O}(N\log N)$ computation complexity, but also largely maintains the capacity of standard self-attention. Extensive experiments on diverse visual tasks demonstrate the effectiveness of our approach, establishing circulant attention as a promising alternative to self-attention for vision Transformer architectures. Code is available at https://github.com/LeapLabTHU/Circulant-Attention.