Research map / Architectures and efficiency / Attention and transformers
CAT: Circular-Convolutional Attention for Sub-Quadratic Transformers
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes CAT, a circulant (FFT-based circular convolution) softmax attention variant that reduces cost to O(N log N) with fewer parameters, evaluated on ImageNet-1k (ViT CLIP-B/L) and WikiText-103 (Transformer-XL, GPT-2 small).
Problem
Standard self-attention costs O(N^2) in sequence length, and existing sub-quadratic alternatives (linear/kernel, sparse, SSM) either break the global softmax weighting or add hyperparameters or architectural changes.
Approach
Replace the N×N softmax(QK^T) map with a circulant matrix built from a single softmaxed length-N vector produced by a learned projection X W_A (merged query-key), applied to values via FFT-based circular convolution; the paper also defines an 'Engineering-Isomorphic Transformer' class of softmax-preserving sub-quadratic models.
Key results
- On ImageNet-1k with avg pooling, CLIP-L CAT reaches 0.694 accuracy vs 0.646 for standard attention, while CLIP-L token pooling CAT is 0.559 vs 0.574.
- On WikiText-103 masked LM, GPT-2 small CAT reaches word PPL 8.32 vs 9.82 for attention; CAT-Alter reaches 7.54.
- The gather-based CAT reports about 10-25% lower iteration time than self-attention on V100 GPUs; in causal LM CAT reverts to O(N^2) and underperforms (GPT-2 PPL 32.36 vs 27.84).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Replace attention layers with CAT | CLIP-B · ImageNet-1k, token pooling | accuracy: 0.574 -> 0.540 | Hurt |
| Replace half of attention layers with CAT | CLIP-B · ImageNet-1k, token pooling | accuracy: 0.574 -> 0.582 | Helped |
| Replace attention layers with CAT | CLIP-L · ImageNet-1k, average pooling | accuracy: 0.646 -> 0.694 | Helped |
| Replace half of attention layers with CAT | CLIP-L · ImageNet-1k, average pooling | accuracy: 0.646 -> 0.681 | Helped |
| Replace attention layers with CAT | Transformer-XL · WikiText-103, masked | word perplexity: 13.94 -> 10.28 | Helped |
| Replace half of attention layers with CAT | GPT-2 small · WikiText-103, masked | word perplexity: 9.82 -> 7.54 | Helped |
| Replace attention layers with CAT | Transformer-XL · WikiText-103, causal | word perplexity: 30.82 -> 36.71 | Hurt |
| Replace half of attention layers with CAT | GPT-2 small · WikiText-103, causal | word perplexity: 27.84 -> 27.68 | Helped |
| Use separate query, key, and value projections instead of merged qv (ablation) | Circular CAT on CLIP-L · ImageNet-1k, average pooling | accuracy: 0.694 -> 0.696 | Helped |
| Use only the query-side learned projection instead of qv (ablation) | Circular CAT on CLIP-L · ImageNet-1k, average pooling | accuracy: 0.694 -> 0.637 | Hurt |
| Use only the value-side learned projection instead of qv (ablation) | Circular CAT on CLIP-L · ImageNet-1k, average pooling | accuracy: 0.694 -> 0.625 | Hurt |
| Replace attention with CAT using cuFFT | CLIP-L · Runtime profile | average iteration time (ms): 1467.5 -> 1187.9 | Helped |
Surprising findings
- Plain CAT is worse than standard attention under causal language modeling and token pooling, and the causal setting reverts it to O(N^2).
- Splitting qkv (Averaged-Key) gives slightly higher accuracy than the merged qv CAT design at the cost of more parameters.
Limitations
- Causal language modeling requires explicit masking or repeated shifts, reverting complexity to O(N^2).
- Results have no error bars or multiple seeds due to limited compute; FFT implementation gains are minimal at moderate N (e.g., N=256) and it is weak with mixed precision for non-power-of-two lengths.
- Code is not released and the paper's linear and sparse baselines were omitted or unstable.
Experimental setup
Datasets: ImageNet-1k WikiText-103
Benchmarks: ImageNet-1k WikiText-103
Metrics: top-1 validation accuracy word perplexity iteration time peak memory parameter count
Baselines: Self-Attention (ViT CLIP-B/L) Transformer-XL attention GPT-2 small attention GQA FlashAttention Linear Transformer
Builds on: Vision Transformer Transformer-XL GPT-2 FlashAttention
Closest papers by meaning
- MonarchAttention: Zero-Shot Conversion to Fast, Hardware-Aware Structured Attention (NeurIPS 2025 · similarity 0.88)
- Rethinking Attention: Exploring Shallow Feed-Forward Neural Networks as an Alternative to Attention Layers in Transformers (Student Abstract) (AAAI 2024 · similarity 0.88)
- Viewing Transformers Through the Lens of Long Convolutions Layers (ICML 2024 · similarity 0.87)
- You Only Need Less Attention at Each Stage in Vision Transformers (CVPR 2024 · similarity 0.87)
- Transformers Learn Faster with Semantic Focus (NeurIPS 2025 · similarity 0.87)
- kNN Attention Demystified: A Theoretical Exploration for Scalable Transformers (ICLR 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.