CAT: Circular-Convolutional Attention for Sub-Quadratic Transformers
Authors: Yoshihiro Yamada
Venue: NeurIPS 2025 poster ()
Keywords: Attention Models
Efficient Inference Methods
Computer Vision
Natural Language Processing
Representation Learning
Primary area: deep_learning

Abstract: Transformers have driven remarkable breakthroughs in natural language processing and computer vision, yet their standard attention mechanism still imposes $O(N^2)$ complexity, hindering scalability to longer sequences. We introduce Circular-convolutional ATtention (CAT), a Fourier-based approach that efficiently applies circular convolutions to reduce complexity without sacrificing representational power. CAT achieves $O(N \log N)$ computations, requires fewer learnable parameters by streamlining fully connected layers, and introduces no heavier operations, resulting in consistent accuracy improvements and about a 10\% speedup in naive PyTorch implementations. Based on the engineering-isomorphic transformer framework, CAT's design not only offers practical efficiency and ease of implementation, but also provides insights to guide the development of future high-performance Transformer architectures. Finally, our ablation studies highlight the key conditions underlying CAT’s success, shedding light on broader principles for scalable attention mechanisms.

CAT: Cireular-Convolutional Attention for Sub-Quadratic Transformers
Yoshihiro Yamada
Preferred Networks vyamada@preferred. jp
Self-Attention O(N2)
Linear
CAT O(N2)
Linear
CAT O(NiogN)
Linear
NxD
Softmax
Matmul
Softmax
Matmul
IFFT
Hadamard
Lightweight Attention Map
FFT
Acceleration
NxN
NxN
Nx1
NxD
Matmul
Gather
FFT
FFT
Softmax
NxD
NxD
NxD
Nx1
Nx1
Linear
Linear
Linear
Linear
Linear
Linear
Linear
Figure 1: From Self-Attention to CAT with two implementations. Left: standard Self-Attention with dense N N attention map (O(N2)). Middle: CAT (O(N?)), a ceftmax-preeerviin circulant form of attention that reduces intermediate computations but remains quadratic overall. Right: CAT (O(N log N)), the same circulant attention computed the frequency domain using the Fast Fourier Transform (FFT), its inverse (IFFT), and element-wise Hadamard product, achieving sub-quadratic complexity.
Abstract
Transformers have driven remarkable breakthroughs in natural language processing and computer vision, yet their standard attention mechanism still imposes O(N2) complexity, hindering scalability
longer sequences. We introduce Cireular- convolutional ATtention (CAT), a Fourier- baaed approach that efficiently applies circular convolutions to reduce complexity without sacrificing representational power. CAT achieves O(N log N) computations, requires fewer learnable pa- rameters by streamlining fully connected layers, and introduces no additional heavy operations, resulting in consistent accuracy improvements and about 10% speedup naive PyToorch implementations. Based on the Engineering-Isomorte Transformers (EIT's) framework, CAT's design not only offers practical efficiency and ease of implementation, but also provides insights to guide the development future high perf-peeffrmacce Transformer architectures. Finally, our ablation studies
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

highlight the key conditions underlying CAT's success, shedding light on broader principles for scalable attention mechanisms.
Introduction
Transformers have become the cornerstone of modern deep learning, excelling in natural language processing, computer vision, and beyond Vaswani el al. [2017]. Kaplan et al. (2020). Dosovitskiy et al.
[2021]. However, the ((N2) complexity of standard Sell-Attentin poses formidable challenge for
large-scale or real-world tasks Zhou et al. [2021] Wu et al. 2019)] Liu et al. [2024). To mitigate this,
Linear Transformers attempt to reduce the complexity to O ( by adopting various kernel functions instead of softmax Katharopoulos et al. [2020], Choromanski et al. [202]] Although these methods can handle long sequences, they often struggle to maintain the essential softmax-baa weighting structure, leading to training instability and accuracy degradation Zhang et al. (2024). Moreover, alternative architectures such as Mamba Gu and Dao (2023 2024 deviate substantially from the original Transformer blueprint, increasing parameter counts and altering core mechanisms rather than serving as a true drop-in replacement Waleffe et al. [2024].
In this work, we introduce Engineering models that must retain the core softmax weighting while achieving sub-quadratic time. This concept helps preserve the strong representational power of standard attention, avoiding many of the pitfalls (e.g., numerical instability, partial token coverage) seen previous approximations. As a concrete instantiation, we propose fircular-convolutiona ATtention (CAT), which leverages Fast Fourier Transform (FFT) and its inverse (IFFT) based circular convolutions to reduce the naive O(N2) cost to O(N log N). Unlike kernel sparse approximations, CAT maintains global softmax and does not introduce extra hyperparameters tied to the sequence length. We validate CAT on large-scale vision (ImageNet-Il Ik) and language (WikiText-101) 103) tasks, demonstrating consistent speedups over standard attention and comparable or improved accuracy. In addition, an ablation study reveals key design factors, such as merging query and key projections, that enable CAT to serve as a drop-in replacement under the EIT principles.
penpeerinngIssmorphie Isomorphic Transformers (EITs), a class of attention-
Our main contributions are as follows.
EITs: A new framework. We formally define Engineering-Isomorre Transformers
(EITs), class of sub-quadratic yet fully softmax preennrxireeeiinggggg architectures that clarifies how efficiency and the softmax-based weighting form can coexist.
CAT: FFT-based attention. We propose Circnlar-comvolatioe ATtention (CAT), which uses FFT-based circular convolutions to reduce the naive O(N2) cost to O log N), while maintaining global softmax behavior and requiring fewer parameters, matrix operations, and no hyperparameters.
Empirical validation. On ImageNet-Ik and WikiText-103, CAT consistently matches exceeds standard attention under simpler token mixing (e.g. average pooling, masked inputs), providing speedup in naive implementations. Looking ahead, we believe CAT's sub-quadratic design, solidly grounded in EIT principles, opens new directions for longer- sequence modeling across language and vision tasks. Combining CAT with other efficient attention mechanisms or advanced GPU kernels may unlock even greater scalability in future Transformer architectures.
2 Engineering-Lsomrphie Transformers (EITs)
Standard Self-Attention Recap. Let X E N be input sequence of length N and feature dimension standard Transformer projects X into queries, keys, and values:
Q = XXQq XWK, V XxWW,
where Wq WK. Wv DDD, Then, the Self-Attention is computed as
QK T Dr
Attention Q, V = softmax
V E NxD

---

where softmax is applied row-wise, D3 is the keylquery dimension, and each row in the resulting N N matrix sums to
Segginerinn--somorppre Transformers. We now formalize a class of Transformers that preserve the softmax-based weighting form of standard Self-Attention while achieving sub-quadratic complexity. We refer to such models as Engineering-Isomon helps reason about efficiency and representational fidelity in a unified framework, offering clear guidelines for designing novel attention mechanisms.
Transformers (EITs). The notion of EITs
Formally, EIT' must satisfy four requirements:
1. Softmax Preservation. There exist functions Fatin (X) and F Fvalue (X) such that the core attention mechanism can be written as
Fout (X softmax (Fattu (X) F Fvalue (X),
mirroring QK T based weighting and row-wise normalization in standard attention. This ensures the global context dependencies remain intact.
2. Sub-Quadratic Complexity. Fout (X) must be computable in strictly less than O(N2) time (where N is the sequence length).
3. Parameter Efficiency. The total number of trainable parameters should remain comparable to (or smaller than) standard multi-head attention.
4. Minimal Hyperparameter Overhead. No sequence-lengthe dependent hyperparameters that require careful tuning (c.g., block sizes, custom sparsity patterns) should be introduced.
Design space. EITs are not tied to single construction. general, any mechanism that retains the softmax-based weighting form of standard attention while executing the attention computation in time below quadratic (e.g., O(N log N) or O(N)) falls within the EIT design space. Examples include value-stream reductions that keep global row-wise softmax (e.g., average or learned pooling prior to value mixing), biasing or Hadamard gating that does not alter the row-wise normalization, and other Toeplitz/circulant-lik transforms. CAT should be viewed as one concrete instance in this broader space, rather than the only one.
Why preserve softmax? We do not claim that exact softmax is universally optimal; efficiency, accuracy, and theory ultimately decide. Still, keeping softmax is a pragmatic axis to explore: maintains normalized and interpretable token weights, remains compatible with established training stacks and inference kernels (c.g.. Flash-style implementations, KV caching, tross-attention), and avoids token-subset coverage effects. This axis complements kernel/linear approaches that discard softmax and search a different approximation space: EITs keep the softmax form while seeking implementations below quadratic time. Our results with CAT indicate that this branch can be made efficient (e.g., an O(N log N) realization with favorable wall-clock and memory profiles) without sacrificing accuracy.
2.1 Properties and Theoretical Insights
In defining EITs, two key challenges must be addressed to ensure that Fout (X) meets sub-quadratic requirements and remains practically viable. First, we need to establish theoretical efficiency, the attention operation must truly cireumvent the O bottleneck. Second, even we achieve a lower computational complexity on paper, the method must exhibit practical performance validity when scaled real-world applications.
Theoretical Efficiency A core requirement of EIT's is the capacity to compute Fout (X) in strictly less than (NN2) time. Naively multiplying an N x N matrix by N D matrix would ordinarily incur (N22) complexity, particularly if Fatta (X) directly corresponds to QKT. To circumvent this, one must either avoid explicitly constructing the full attention matrix or leverage specialized transforms that reduce the overall cost. For instance, in Sec. 4 we introduce CAT, which exploits Fourier-based circular convolutions to achieve O(N log N) complexity Cooley and Tukey [1965), all while retaining the softmax-based weighting structure central Self-Attention.
Practical Performance Validity However, merely satisfying sub-quadratic complexity does not guarantec strong empirical performance. Large-scale tasks in language processing vision demand
3

---

not just efficient computations but also robust training stability and high accuracy. Many existing approximations. though efficient in principle, struggle with degraded performance when confronted by real-world data scales. Thus, practical performance validity becomes essential: an EIT must demonstrate that theoretical gains not come at the expense representational capacity or overall results. In Sec we present empirical evidence verifying that our approach preserves (and often improves) the performance of standard Transformers, illustrating that a sub-quadratic softmax-based mechanism can indeed align with practical, large-scale demands.
3 Related Work
Having established the concept of EITs, we now evaluate how widely used attention-redduction techniques align with or diverge from this framework.
Approaches like Zaheer specific regions compressed representations, effectively pushing complexity below O(N2). While such strategies preserve row-wise softmax, it is only applied to a subset tokens, thereby breaking the global weighting that consider essential for ElTs. Moreover, many sparse low-rank architectures rely on carefully tuned patterns (c.g., block sizes, sparsity thresholds) that may need readjustment sequence length N grows, introducing additional hyperparameter overhead. This conflicts with the moniimal-hyeeppraame
Zaheer et al. [020] and Longformer et al. 2020 reduce attention
principle we outlined above.
Performer Choromanski et al. [2021] and Linear Transformers Katharopoulos al. 2020) introduce kernel-based feature mappings to approximate softmax. Although this yields ( scaling, the exact
softmax structure is lost, which may affect training stability and interpretability Zhang al. [024]]
Methods such as S4 Gu tirely, employing continuous-time time RNN-like mechanisms. While efficient, they diverge from the fundamental idea of a data-dependent softmax weighting over all pairs of tokens.
[0022 or Mamba Gu and Dao 2023 2024 eschew attention en-
By contrast, EIT' preserve a global softmax mechanism and still operate with sub-quadratic com- plexity. In Sec. we introduce CAT as a concrete instantiation of this principle, illustrating how Fourier- approach can retain the core benefits of attention while breaking the ((N2) barrier.
4 Proposed Method
We propose Cireular-convolutionall ATtention (CAT), an approach that meets the EITs criteria (Sec. 2 CAT applies circular convolutions in the frequency domain reduce the O(N)) cost of Self-Auter Attentien to O(N log N), while preserving the essential global softmax structure.
Key Idea. Rather than explicitly computing softmax (QK ). CAT interprets the attention weights as a circulant (or circular shift) matrix. Specifically, we learn single projection matrix WA E Dx1 map the input X E NxD into vector
Z Z E Nx1
then apply row-wise softmax, yielding = softmax(Z). This Z serves as the first row of circulant matrix circ(Z*), thus representing global pairwise interactions. In particular, we define
Z
Z
Z
N
Z
circ(Z") (Z*)
72
73
7
so each row is a one-step circular shift of the previous row. Convolving this matrix with XW (where Wv E DxD) can performed via FFT, thereby avoiding the naive N N multiplication. Formally, let V XW Then,
F cas = circ (
IFFT (Z') O FFT(V)),
where c denotes the Hadamard (element- wise) product applied in the frequency domain, and the overall computation is performed in O(N log N) time.

---

Unlike kemne- based approximations, this FFT-based procedure does not distort the softmax distribu- tion, since the circulant structure is exactly equivalent to circular convolution (up floating point rounding). Qualitative attention-map analyses in Appendix A are consistent with this interpretation, showing structured, thie patterns induced by the circulant design.
Multi-head Extension. CAT naturally extends to multi-head attention by maintaining separate sets of (W& A. Wv) per head. Except for this, no additional modifications are needed. We refer readers to Sec. 5 for performance results in image classification and language modeling. Moreover, CAT naturally integrates typical attention optimizations, such as key-value caching during inference.
4.1 Implementation Details
We consider two ways of implementing CAT. The gather-based version, while nominally O(N2) due to indexing overhead, consistently yields about 10% speedup of each iteration in naive PyTorch. Complete runtime and memory profiles are provided Appendix B In contrast, a full FFT-based version can theoretically achieve O log N) complexity, although we currently observe minimal gains at moderate N. We detail these comparisons below.
Gather-based Approach. By rolling the value matrix V via torch. gather, avoid large matrix multiplications. Despite having an O(N2) indexing, we see a net 10% speedup over standard attention (e.g., for ViT CLIP-L on NVIDIA V100 GPUs). We attribute this to simpler dataflows and fewer partial matrix operations.
FFT-based Approach. Applying FFM/FFF directly to Z' and V realizes the sub-quadratic O(N log N) complexity. However, for N = 256, the overhead of FFT calls (and their GPU kernels) often offsets the theoretical advantage. We anticipate greater speedups for larger N and specialized GPU FFT implementations, which we leave for future work.
4.2 Key Theoretical Considerations and Advantages
Beyond achieving sub-quadratic complexity, our CAT design offers several theoretical merits that ensure remains faithful the core properties of Self-Attentio.. We briefly summarize these points here.
Minimal Row- Wise Softmax Structure. A key insight is that CAT maintains exact row-wise softmax normalization by leveraging circulant matrices. Formally, for any Z,
(aftmax(ccir(22)
cire(softmax(2))
since both the circulant operator and the softmax function act independently rows. Thus, CAT meets the strict EIT requirement of a global nownnormalzzed weighting, providing a "minimal" row- wise transform that does not distort the softmax attention. Introducing additional transformations would typically break this row-wise property and lose the exact softmax coverage.
Dramatically Reduced Attention Materialization. Unlike standard QK attention, which computes an x matrix of attention scores at runtime, CAT represents attention with a length-N cireulant kernel Z derived from XW A. from which the full attention matrix is generated by circular shifts. This reduces the number of attention coefficients that must be produced and operated on from 2 to N (per head), lowering intermediate compute and memory traffic and enabling O(N log N) FFT-based execution. We observe that this structured reduction can stabilize optimization and, in some configurations, improve generalization (e.g., Tab.
Explicit Relative Positioning. In many tasks, the relative ordering of tokens (c.g. word positions, time steps. spatial locations) plays vital role. While classical Transformers rely on positional embeddings to hint at absolute positions, they lack a dedicated mechanism for handling relative offsets. Empirical studies of early Transformer layers Clark et al. [2019] suggest attention maps often exhibit shift-like or local patterns. By explicitly enforcing a circulant structure, CAT encodes this shift-based symmetry from the outset. Hence, early layers more naturally capture local recurrences or repeated patterns in the data, which may lead to faster convergence and improved feature extraction.
Complementarity with Standard Attention. Despite these advantages, our experiments (Sec.) show cases where standard Self-Attention still excels, especially if highly flexible global interactions
5

---

Model
Pool Type
Mechanism
Learnable
Complexity
Acc.t
CLIP-B
token
Attention
3D²
O(N2)
0,574
CLIP-B
token
CAT (ours)
(D + HYD
O(N log N)
0.540
CLIP-B
token
CAT-Alter (ours)
(2D + H/2)D
O(N²)
0.582
CLIP-L
token
Attention
3D²
O(N²)
0,574
CLIP-L
token
CAT (ours)
(D + H)D
O(N log N)
0.559
CLIP-L
token
CAT-Alter (ours)
(2D + H/2)D
O(N2)
0.593
CLIP-B avg
Attention
3D
O(Nz)
0.638
CLIP-B avg
CAT (ours)
(D HDD
O(N log N)
0.649
CLIP-B avg
CAT-Alter (ours)
(2D + H/2)D
O(N2)
0.662
CLIP-L avg
Attention
3D²
O(N2)
0.646
CLIP-L avg
CAT (ours)
(D + HYD
O(N log N)
0.694
CLIP-L avg.
CAT-Alter (ours)
(2D + H/2)D
O(N2) 0.681
Table ImageNet-IK results ViT CLIP-B/L with different pooling strategies. Here, D is the input embedding dimension, and H is the number of attention heads. Recent optimizations can reduce this overhead, but are not considered in our baseline. CAT excels when the token mixing is simpler (e.g.. avg), while CAT-Alter is competitive or superior across most settings.
Model
LM Type
Mechanism
Learnable
Complexity
Word PPL.
Transformer-X XL
masked
Attention
3D²
O(N2)
13.94
Transformer-XI.
masked
CAT (ours)
10+H)J
O(N log N)
10.28
Transformer-XL
masked
CAT-Alter (ours)
(2D) - -H/2)D
O(N2)
8.51
GPT-2 small
masked
Attention
31"2
O(N*)
9.82
GPT-2 small
masked
CAT (ours)
(D + H)D
O(N O(Voog N)
8.32
GPT-2 small
masked
CAT-Alter (ours)
(2D) - -H/2)D
O(N²)
7.54
Transformer- XL
causal
Attention
3D²
O(N*)
30.82
Transformer-Xi
causal
CAT (ours)
(D H)D
O(N")
36.71
Transformer-XL
causal
CAT-Alter (ours)
(2D - HH/2DD
O(N")
30,93
GPT-2 small causal
Attention
3D²
O(N*)
27.84
GPT-2 small
causal
CAT (ours)
(D+ + H)D
O(N")
32.36
GPT-2 small
causal
CAT-Alter (ours)
(2D - H/2)D
O(N)
27.68
Table 2: WikiText-IOS (masked and causal language modeling). Here, D is the input embedding
dimension, and H is the number of attention heads. CAT shows notable gains in the masked setting, while CAT-Alter remains more robust in the causal setup.
required. However, combining CAT and standard attention within single network (e.g., CAT- Alter) can yield complementary benefits, as CAT enforces shift-based regularization while standard attention remains fully expressive. Thus, even if CAT alone occasionally suboptimal, this hybrid approach can surpass both purely circulant and purely attention-based methods, offering practical balance between efficiency and accuracy.
Overall, CAT embodies a "least complex" row-wise transform that fully preserves the softmax mechanism while drastically reducing the attention overhead. In the following sections, detail how these properties translate into strong empirical performance, especially under simpler token mixing (avg pooling) masked language modeling regimes (Sec. 5).
Experiments
We evaluate our CAT on two major benchmarks: ImageNet-Ik Russakovsky et al. (2015) for image classification and WikiText- 1033 Merity et al. (2016) for language modeling. Our main focus is to demonstrate (1) whether CAT can maintain or improve performance despite its sub-quadratic design, and (2) how hybrid variant that partially retains standard attention might further boost robustness.

---

Linear
Softmax
Matmul
Gather
Matmul
1xD mean
NxD (learnable)
Nx1 (learnable)
Linear
circular qkv (Averaged-Key)
circular qv (CAT)
circular
circular v
Figure 2: Ablation study comparing different parameterization strategies for query, key, and value (qkv, qv, q. v). Although fully splitting qkv (Averaged- Key) can yield slightly higher accuracy, it reintroduces attention-leve parameter budgets. Our qv variant (CAT) strikes practical balance, maintaining sub-quadratic complexity and competitive performance.
Model
Pool Type
Mechanism
Circular qky
Learnable
Complexity
Acc.t
CLIP-L
avg
Attention
3Dz
O(N*)
0.646
CLIP-L
avg
Cireular
qkv (Averaged-Key)
3D
O log N)
0.696
CLIP-L
avg
Circular
qv (CAT)
(D + H)D
(NNlog N
0.694
CLIP-L
avg
Cireular
q
(N H)D
O OoNoo N)
0.637
CLIP-L
avg Circular v
(N + D)D
O(N log N)
0.625
Table 3: Ablation key-value parameterization under circular convolution. Here, D is the input embedding dimension, is the number of attention heads, and N is the input time series. While qkv achieves slightly higher accuracy, qv (CAT) remains competitive with fewer parameters.
We primarily use VIT CLIP-B/ Radford et al. [202] Cherti et al. [0233 for image classification and a Tr Dai al. (2019) GPT-2 small Radford et [ [2099] backbone for language model- ing. We follow the original architectures for CLIP-B (12 heads), CL.IP-L (16 heads), Transformer-Xl (10 heads), and GPT-2 small (12 heads) preserving the same number attention heads in both standard and CAT layers. Training hyperparameters, such learning rate and batch size, are likewise inherited from each respective baseline. Where indicated, we replace attention layers with CAT (denoted CAT) or half of them (denoted CAT-Alter), while the rest remain standard attention. In the latter case, the network interleaves CAT and standard attention blocks. Although half the layers still run in O(N2), the other half operate in O log N) via CAT, yielding net speedup in practice. Moreover, because CAT merges query and key projections, these replaced layers reduce the overall number of learnable parameters relative to fully attentive models.
Our comparisons include the original Transformer attention each architecture. report standard validation accuracy on ImageNet- 1k and validation word perplexity (word PPL.) on WikiText-1003 Complete runtime and memory profiles are provided in Appendix
5.1 Training Details
We train our models on the ImageNet-Ik 1k training dataset Russakovsky et al. (015 using batch size of 256 and standard input resolution of 224 on 4 NVIDIA V100 GPUs. The initial learning rate is set to 2 x 10-5, with weight decay of 1 x 10-1 All models randomly initialized. We train

---

for 50 epochs, applying a 10-epoch warmup phase followed by cosine-annealing scheduler. We use AdamW with default hyperparameters (i.e., B1 0.9, B2 0.999). Data augmentation consists of random cropping and horizontal flipping.
For language modeling the Wiki training dataset Meeity et al. (2066), train with batch size of 128 and an initial learning rate of 2.5 x 10 on 4 NVIDIA VI00 GPUs. We run 50 total epochs, employing a 1000-iteration warmup. We the maximum sequence length to 256. A dropout rate of 0.1 is applied, and gradient norms are clipped at a maximum of 0.25, As with ImageNet-Ik, we use AdamW Loshchilov and Hutter (2019) under default settings unless stated otherwise. Models are also randomly initialized in this setup. Finally, for masked language modeling experiments, we use a masking probability of 0.15.
In causal language modeling, we shift to ensure each position attends only up to its current timestep. However, enforcing strict causality reintroduces computational overhead, typically reverting CAT's complexity to ( via explicit masking or repeated circular shifts. Fully sub-quadratic implementations under causal constraints remain an important open challenge.
5.2 Experimental Results
We examine image classification tasks on ImageNet-Ik Ik (Tab. D We test two pooling strategies: token pooling via a special classification token, and avg pooling over the entire sequence. Overall, CAT tends to excel under simpler token mixing. seen with average pooling, while CAT-Alter appears more robust across different setups. Notably, CAT-Alter can outperform standard attention in several configurations, illustrating that a partial replacement can deliver improvements without fully discarding the attention mechanism.
We further examine masked and causal language modeling WikiText-103 103 (Tab. 2 CAT attains strong gains in masked modeling scenarios, suggesting that its sub-quadratic structure remains highly effective when masking simpler token manipulations are involved. In contrast, CAT-Alter often achieves performance close to, or slightly better than, standard attention across a wider range of conditions, indicating that partial adoption of CAT can preserve the benefits of attention while introducing computational advantages for parts of the network.
The compatibility results with GQA and the hybrid GQA-CAT-Alter accuracy snapshot are summa- rized in Appendix C
5.3 Additional Baselines: Linear and Sparse Attentions
For completeness, we also experimented with Linear Attention variant as in Katharopoulos et al. [2020). Choromanski et al. [2021), hoping to achieve O(N) complexity under the same training conditions. However, on CLIP-L we encountered repeated training instabilities (e.g., NaN loss values) and could not obtain stable convergence. Such issues are consistent with prior reports of kernel-based attention struggling to maintain numerical stability at larger scales.
We further examined representative sparse-attention methods such as BigBird BaggeerZZaherrrr Zaheer et al. [2020] and Longformer (BenterrrBygyyaaa al. [2020). However, these approaches introduce sequence- dependent sparsity hyperparameters (e.g., block size or global token selection). which complicate direct compar- ison under fixed training settings. As CAT inherently hyperparameter-fieee by design, we focus on standard Attention to ensure a fair and controlled comparison.
Hence, we omit further comparisons with Linear and sparse attention variants in the main results.
5.4 Discussion
Taken together, these results show that CAT can reduce complexity while maintaining or even improving accuracy in settings with simpler token mixing requirements, particularly when using average pooling or masked inputs. Notably, avg pooling often outperforms token pooling across our baselines (Tab. []. highlighting a broader trend in vision models that prefer global summarization over relying on specialized classification token. Hence, the fact that CAT excels under avg pooling especially significant: aligns well with designs where tokens are mixed more globally, suggesting broad applicability in future ViT-like architectures. In addition, the strong gains in the masked setup
8

---

in language modeling are particularly noteworthy, given the recent surge of competitive Transformer variants that also adopt masked language modeling objectives Nie et al. [202]]
Meanwhile, CAT-Alter offers a balanced compromise, often exceeding standard attention's perfor- mance in both vision and language tasks. We hypothesize that employing CAT layers for parts of the network unlocks notable efficiency gains, while retaining the expressive power of full attention elsewhere. This hybrid-layer behavior aligns with the snapshots in Appendix Caaenddxx[[nn and mirrors findings in recent STMnsformer/SSM hybrids such as H3 Fu et al. 2023) and Jamba Lenz et al. 2025 where mixing attention with sate-space components yields stronger or more stable performance than either mechanism alone. Achieving high accuracy under masked language modeling underscores CAT's potential for mext-generation models where masking or simplified token interactions are central to performance.
6 Ablation Study
Thus far, we have primarily used a combined query-key projection WA alongside separate value matrix Wy. However, one can define or omit independent Q. K, and V in various ways, for example, by adopting an averaged key or partially splitting the query and key. To clarify how these design choices affect performance and parameter count, we conduct an ablation on ViT CLIP-L, comparing:
qkv (Averaged-Key): Retains separate query, key, and value modules (with 3D² param- eters), leveraging circular convolutions for sub-quadratic complexity. Its explicit q-k-v structure facilitates simpler integration into existing cross-attention pipelines compared to CAT's merged-query design.
qy (CAT): Our default approach (Sec. where Q is absorbed into a single projection WA. while V remains separate.
q only only: Attempts for comparison to simplify by learning parameters either for the query or value, but relying on a dimension proportional to N. We denote these strategies as "q-only" and 'v-only' for brevity.
For completeness, we summarize the formulations of each variant in the same notation as Sec. Let X E N denote the input sequence, let circ(-) represent the circulant operator, and let mean(-) represent the mean operator from R to p1xD
(I) circular qkv Keveraged-Key):
Q XWQ Q. Kavg mean (X XWWk Wk),
QK DDz
Z softmax
F cire XWv:
(2) circular qv (CAT):
Z softmax XW A); F cire(Zz) XWv:
(3) circular q only:
Z" softmax XW A). F = circ(Z*) (TT)
(4) circular v only: z softmax(Zn) (ZT), F = circ(Z') XWv,
where VT E NDD and ZT E Nx are trainable parameters replacing XWv and XWA.
All variants share the same circulant attention mechanism but differ in how query-key projections parameterized. The qky version retains full independence among (Wq. WK. Wv); CAT (qv) merges query and key through WA: q-only and v-only restrict learnable parameters to a single branch.
Observations. While splitting into qkv yields a slight performance edge, it reintroduces learnable parameters. Conversely, q-only or v-only designs compromise accuracy and can inflate parameter requirements with respect to N. Therefore, our qv approach provides practical balance, effectively emulating attention's capacity without incurring quadratic parameter overhead.
1. qkv vs. qv: Retaining fully distinct query, key, and value (qkv) yields the highest accuracy (0.696) but also the largest parameter budget (3D²). In contrast, our qv design maintains nearly the same accuracy (0.694) with fewer specialized matrices and matrix operations.
2. q or v alone: Eliminating either query or value parameters reduces the complexity of one component but allocates learnable dimensions proportional to N. This approach not only

---

falls behind in accuracy (down to 0.637 or 0.625) but also scales poorly for larger sequence lengths.
3. Balancing cost and performance: The qu (CAT) configuration achieves a good trade-off, preserving global softmax weighting, keeping complexity at O(N log N), and attaining competitive accuracy.
Parallels to Input-Based Control. Beyond these core ablations, we note conceptual parallel to state-space models such as Mamba Gu and Dao 2023 2024), which incorporate input-driven control signals to update internal states more dynamically. l. Specifically, Mamba injects control variables from the imput directly into its state equations, often improving accuracy via data-dependent updates. In a similar vein, our qv configuration merges query-like transformations (Q) with the primary value projection (V), effectively supplying an input-driven mechanism modulate attention weights per-token basis. We hypothesize that this design fosters the same kind of dynamic control observed in Mamba, potentially explaining the qv variant's strong performance despite fewer learnable parameters than qkv. Exploring this connection, e.g., by systematically contrasting different imput-ineetiion strategies across attention and state-space frameworks, represents intriguing direction for future research.
Conclusion
We introduced crinneerinn-lsomorphhe Transformers (EITs), a framework that retains the essential softmax-based attention structure while reducing theoretical complexity below O(N²). Within this perspective (Sec. 2} our CAT results (Appendix [B indicate that a softmax-pressrving below- quadratic design can be both efficient and competitive scale. As concrete realization, our CAT leverages FFT-based circular convolutions to achieve O(N log N) runtime. Through extensive experiments on ImageNet-II Ik and WikiText-103, we demonstrated that CAT can match surpass standard attention under simpler token operations (e.g., average pooling, masked language modeling), an important result, given that avg pooling increasingly outperforms token-based approaches in certain vision tasks, and that masked language modeling has become a highly competitive paradigm in recent Transformer research. Furthermore, our partial substitution scheme (CAT-Alter) remained robust across broader scenarios, at times exceeding full attention. An ablation study (Sec. (6) further revealed that merging query-key (qv) offers a practical balance of parameter efficiency and accuracy, outperforming alternatives like k-only or e-only projections. We believe this qv-based CAT design effectively emulates key aspects of standard attention without incurring quadratic complexity or parameter overhead.
Open Challenges and Scalability. Although CAT ensures sub-quadratic runtime in principle. validating its training stability and accuracy for extremely large sequences (e.g., tens of thousands of tokens) remains an open challenge. particular, understanding how CAT scales in both efficiency and representational quality at these lengths would further solidify its real-world applicability Gu and Dao [223). Another promising direction is integrating CAT with other efficient attention variants, such as sparse, low-rank, or kernel-based methods, to push large Transformer architectures even further. From an implementation standpoint, hardware-optimizzed FFT kernels on GPUs or specialized accelerators could amplify the observed gains Dao et al. (0222. Beyond language and vision, applying EIT's principles to domains like speech or time-series forecasting may unveil new advantages of sub-quadratic models. We hope our work sparks further innovation in balancing efficiency and representational power, positioning EITs as a versatile foundation for the next generation of scalable deep learning.
Broader Impact and Future Work. While our sub-quadratic approach lowers the computational barrier and can democratize acage-scale model training. it may also inadvertently accelerate the widespread usage of essource-intensii models, potentially increasing energy consumption and enabling misuse in certain applications. Addressing these concerns will require careful consideration of environmental sustainability, governance, and ethical guidelines future work. We believe that ongoing efforts to develop hardware-optimizee kernels and efficient deployment strategies will complement our method, helping to ensure that sub-quadratic Transformers can be harnessed responsibly and sustainably.
10

---

References
I. Beltagy, M. E. Peters, and A. Cohan. Longformer: The long-document transformer. arXiv preprint 051v:20044005/50, 2020.
M. Cherti, R. Beaumont, R. Wightman, M. Wortsman, G. Ilharco, C. Gordon, C. Schuhmann, L. Schmidt, and J. Jitsev. Reproducible scaling laws for contrastive language-image learning. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2023.
K. Choromanski, V. Likhosherstov, D. Dohan, X. Song, Gane, Sarloós, P. Hawkins, Davis, A. Mohiuddin, L. Kaiser, D. Belanger, L. Colwell, and A. Weller. Rethinking attention with performers. In International Conference on Learning Representations (ICLR), 2021.
K. Clark, U. Khandelwal, O. Levy, and C. D. Manning. What Does BERT Look at? An Analysis of BERT's Attention. In Proceedings of the 2019 ACL Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP, 2019.
J. W. Cooley and J. W. Tukey, An algorithm for the machine calculation of complex fourier series. Mathematics of Computation, 1965.
7. Dai, 7. Yang. Y. Yang, J. Carbonell, V. Q. Le, and R. Salakhutdinov. Transformer-xl: Attentive language models beyond a fixed-length context. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics (ACL), 2019.
T. Dao, D. Y. Fu, S. Ermon, A. Rudra, and C. Ré. Flashattention: Fast and memory-efficient exact attention with io-awareness. In Advances in Neural Information Processing Systems (NeurIPS), 2022.
A. Dosovitskiy, L. Beyer, A. Kolesnikov, D. Weissenborn, X. Zhai, T. Unterthiner, M. Dehghani, M. Minderer, G. Heigold, S. Gelly, J. Uszkoreit, and N. Houlsby. An image is worth 16x16 words: Transformers for image recognition at scale. In International Conference on Learning Representations (ICLR), 2021.
D. Y. Fu, T. Dao, K. K. Saab, A. W. Thomas, A. Rudra, and C. Ré. H3: Hungry hungry hippos: Towards language modeling with state space models. In International Conference on Learning Representations (ICLR), 2023.
A. Gu and T. Dao. Mamba: linear-time sequence modeling with selective state spaces. arXiv preprint 1220:23322.00552, 2023.
A. Gu and T. Dao. Transformers are ssms: Generalized models and efficient algorithms through structured state space duality. International Conference Machine Learning (ICMI.,, 2024.
A. Gu, K. Goel, and C. Ré. Efficiently modeling long sequences with structured state spaces. In International Conference Learning Representations (ICLR), 2022.
Kaplan, S. McCandlish, Henighan, T. B. Brown, B. Chess, R. Child, S. Gray, A. Radford, Wu, and D. Amodei. Scaling Laws for Neural Language Models. arXiv preprint 2rXiv:2001.08361, 2020.
A. Katharopoulos, A. Vyas, N. Pappas, and F. Fleuret. Transformers are mns: Fast autoregressive transformers with linear attention. In International Conference on Machine Learning (ICML), 2020.
B. Lenz, O. Lieber, A. Arazi, A. Bergman, A. Manevich, B. Peleg, B. Aviram, C. Almagor, Fridman, D. Padnos, et al. Jamba: Hybrid transformer-mann language models. In International Confer- on Learning Representations (ICLR), 2025. URL https:://pperreieeett nwt.:/rmm//f/ JFPaD71pBD
N. F. Liu, K. Lin, J. Hewitr, A. Paranjape, M. Bevilacqua, F. Petroni, and P. Liang. Lost in the Middle: How Language Models Use Long Contexts. Trunsactions of the Association for Computational Linguistics, 2024.

---

I. Loshchilov and F. Hutter. Decoupled weight decay regularization. In International Conference on Learning Representations (ICLR), 2019.
S. Merity, C. Xiong, J. Bradbury, and R. Socher. Pointer sentinel mixture models. arXiv preprint 160.0044,,,,7844, 2016.
S. Nie, F. Zhu, Z. You, X. Zhang, J. Ou, Hu, J. Zhou, Y. Lin, J. Wen, and C. Li. Large language diffusion models. arXiv preprint arXiv:2502.0999 09992, 2025.
A. Radford, J. Wu, R. Child, D. Luan, D. Amodei, and I. Sutskever. Language models are unsupervised multitask learners. 2019.
A. Radford, J. W. Kim, C. Hallacy, A. Ramesh, Goh, S. Agarwal, G. Sastry, A. Askell, Mishkin,
J. Clark, G. Krueger, and I. Sutskever. Learning transferable visual models from natural language supervision. International Conference on Machine Learning (ICML), 2021.
O. Russakovsky, J. Deng, H. Su, Krause, Satheesh, S. Ma, Z. Huang, A. Karpathy, A. Khosla, M. Bernstein, A. C. Berg, and L. Fei-Fei. Imagenet large scale visual recognition challenge. International Journal of Computer Vision (JCV)), 2015.
A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and I. Polosukhin. Attention is all you need. In Advances in Neural Information Processing Systems (NeurIPS), 2017.
R. Waleffe, W. Byeon, D. Riach, B. Norick, V. Korthikanti, T. Dao, Gu, A. Hatamizadeh, Singh, D. Narayanan, G. Kulshreshtha, V. Singh, J. Casper, J. Kautz, M. Shoeybi, and B. Catanzaro. An empirical study of mamba-based language models. arXiv preprint arXiv:2406.077: 078877 2024.
C. Y. Wu, C. Feichtenhofer, H. Fan, K. He, Krähenbühl, and R. Girshick, Long-Term Feature Banks for Detailed Video Understanding. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), 2019.
M. Zaheer, G. Guruganesh, A. Dubey, Ainslic, C. Alberti, S. Ontanon, Pham, A. Ravula, Q. Wang, L. Yang, and A. Ahmed. Big Bird: Transformers for longer sequences. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
M. Zhang, K. Bhatia, H. Kumbong, and C. Ré. The hedgehog & the porcupine: Expressive linear attentions with softmax mimicry. In International Conference Learning Representations (ICLR), 2024.
H. Zhou, S. Zhang, J. Peng, S. Zhang, J. Li, H. Xiong, and W. Zhang. Informer: Beyond efficient transformer for long sequence time-series forecasting. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI), 2021.
12

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We clearly state in the abstract and introduction that our proposed method reduces the complexity from O(N2) O O(Nlog.N) while maintaining the exact softmax structure, and our experiments confirm these claims in Sec. 5 and 6.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Sec. 7 discusses scenarios where our approach might underperform, such as extremely large sequence lengths, hardware-optimizztion.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "I "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and prool's
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
13

---

Answer:
[Yes]
Justification:
We state all assumptions for our sub-quadratic claim in Sec. 4.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof's can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Question:
Answer: [Yes]
Justification: We detail dataset splits, preprocessing, model hyperparameters, and training settings (in Sec. 5), providing all configurations required to replicate our main results.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is new model (e-g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path reproducing verifying the results. 5. Open access to data and code
14

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [No]
Justification: We use publicly available datasets (ImageNet- IK, WikiText-103). but we have not released our code due to ongoing internal requirements.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips... cc/
for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Sec. details our data splits, optimization hyperparameters, and optimization algorithms.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
Justification: We primarily reported our results but did not include standard deviation due to limited computation. We acknowledge this is a limitation and plan include extended runs in future work.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
15

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification: Sec. 5 states that we conducted our experiments on a cluster of NVIDIA V100 GPUs. Each training run took approximately 1-2 days.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics htttpp//..aarrrr.....///o///haat
Answer: [Yes]
Justification: Our study follows all ethical guidelines and uses public datasets (ImageNet- lk and WikiText- 103) with proper citations. Neither confidential nor sensitive data involved, and the methodology does not raise specific ethical concerns.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: In Section 7 we discuss the ecological benefits of reducing training compute, as well as potential negative implications of enabling more large-scale models, including concerns about misinformation.
16

---

Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (c.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploymemt of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA].
Justification: Our work focuses on general attention mechanism improvements and does not introduce high-risk data or models requiring special safeguards.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We cite the original references for ImageNet and WikiText- 103 in Sec. 5 and mention their licenses. We also acknowledge the standard open-source Py Porch and FFT libraries.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
17

---

The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g.. website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if it has changed) should provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: We do not introduce new datasets models beyond the standard ones; thus, no new asset documentation is required.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: Our work is purely algorithmic and does not involve human subjects or crowdsoureing.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: No human subjects participant- based studies involved in research.
18

---

Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: We employ standard Transformer-Xi XLL and GPT-2 small as conventional lan- guage models, but do not rely on any large-scale LLM for core methodology or data generation.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non standard components.
Please refer to our LLM policy (https://neure) /atp:uuppp...o/ooofeeeeeeee///2 for what should or should not be described.
19

---

A Visualization of Attention Maps
We provide qualitative visualizations to illustrate how CAT and CAT-Alter differ from standard Self-Attention in terms of structural attention patterns. For CLIP-B (ViT-B/16), we visualize token-to- token attention maps the patch level (196x 196). Each bottom panel in Figs. Sa shows a 12x 12 mosaic: rows correspond to attention heads (h-1... 12, left to right), and columns correspond to layers (1=1. ... 12, top to bottom). All maps are computed from per-head attention weights after softmax and are individually min max normalized for visualization, using a shared colormap across methods. No averaging across heads layers is applied before plotting.
In these visualizations, standard Self- Attenttttnnion typically exhibits two canonical motifs: (1) woven, grid-like stripes representing cross-token interactions, and (2) near-identity diagonal bands capturing self-alignment. CAT, in contrast, produces more regular and shift-like diagonal structures that reflect its circulant formulation. While visually distinct, CAT achieves comparable or higher accuracy, as reported in the main tables. CAT-Alter combines both behaviors: it retains structured diagonal patterns early layers while showing more globally diffuse attention in deeper layers. Interestingly, this mixture of localized and global dynamics coincides with its superior overall performance among all compared mechanisms, perhaps because combining fine graiira local structure with broader global context yields more balanced representation.
B Runtime and Efficiency Analysis
To provide quantitative evidence of CAT's computational advantages, we present detailed run- time and memory profiles that clarify the extent of its speed and memory benefits over stan- dard Self-Attention. All measurements were conducted on NVIDIA V100 GPUs (FP16 pre- cision, batch size = 32) using the Adam optimizer. Experiments used PyTorch 2.7.0 + cu126 cuDNN 9.5.1, with cuFFT as the FFT backend for CAT and FlashAttention for Self-Attention baselines. We measure iteration time as the sum of the forward, backward, and optimizer passes, averaged over 10 steps. Table reports this aggregate figure.
(torch. mn. funccininalll scaled_
Table summarizes runtime and memory usage for CLIP-L and GPT-2 small. CAT consistently reduces iteration time by 10-25% compared with Self- Sttf-Attention, and the cuFFT implementation additionally lowers peak memory by about 25%.
Nonetheless, two practical bottlenecks still remain: (1) limited mixed-precision support, where performance degrades for sequence lengths not equal to powers of two. (2) Overhead for short sequences, where the gather version can outperform the FFT version.
Looking ahead, future GPU architectures with optimized FFT kernels and planning caches expected to further accelerate the O(N log N) variant, especially for long-sequence applications.
C
Compatibility with FlashAttention and GQA
Efficient attention mechanisms are often combined in practice to balance speed, memory, and accuracy. To facilitate adoption and to position CAT among widely used baselines, we note that CAT integrates with both FlashAttention and GQA (Grouped-Query Attention), and is expected to offer complementary efficiency gains when used together. Below we discuss how CAT interacts with each method, relate these observations sketch together with small empirical results.
FFT-based findings, and present concise computational
C.1 FlestAttention Integration
FlashAttention'' 's streaming formulation of exact softmax eliminates the need to materialize the full N N attention map. substantially reducing memory traffic. A similar idea can be applied to CAT: implementing streaming circulant variant allows the circular mixing to be computed on the fly without constructing intermediate matrices. This approach reduces transient buffers in the gather step and lowers peak memory, which is expected to provide FlashAttention-lik benefits in runtime and memory efficiency, particularly when FFT planning overhead dominates small sequence lengths (cf. Appendix B).
20

---

(a) Attention-map visualization, input: siamese cat.
8118
(b) Attention-map visualization, input: catamaran.
Figure 3: Attention-map visualizations using CLIP-B (average pooling). Top-left: input image.
Bottom row (leht~rright): Self-Attention, CAT, and CAT-Alter. Each panel shows 196x 196 token- to-token attention maps arranged as a 12x 12 grid: rows correspond to attention heads (h=1... 12) within each layer, and columns correspond to layers (I=1... 12) from top to bottom. All maps share the same colormap and are normalized by min max scaling.
min-max
21

---

Variant
Param (M)
Peak Mem (MB)
Avg Time (ms)
CLIP-
Self-Atienion (Py Torch MatMul))
304.2
16654
1463.7
Self-Attention (FlashAttention)
304.2
13594
1467.5
CAT (gather, ((N2))
254.2
14931
1188.5
CAT (cuFFT, O(N log N))
254.2
11882
1187.9
GPT-2 small
Sclf-Attention (PyTorch MatMull)
T07.5
3289
521.6
Sclf-Attention (FlashAttentionn
107.5
5259
531.0
CAT (gather, ((V2))
93.5
4651
441.8
Table 4: Runtime and memory profiles for CLIP-L and GPT-2 small on NVIDIA V100 GPUs (FP16,
batch size 32). CAT shows shorter iteration time than the Self- Attentioo baselines across both models, and the cuFFT variant further reduces peak memory on CLIP-L
Variant
Param (M)
Peak Mem (MB)
Avg Time (ms)
CLIP-L
SeTf-Attention (PyTorch MatMul)
307.2
T6654
1465.72 72
GQA (K=1/4)
260.3
16510
1307.26
GQA (K=1/16)
257.0
16474
1270.39
CAT (gather, ((N3))
254.2
14931
1188.48
Table 5: Runtime snapshot for CLIP-L (V100 FP16, batch size competitive and often faster than typical GQA configurations.
32). CAT (gather) appears
C.2 GQA Enhancement (Runtime, Memory, Accuracy)
compact projection-side compute model for the attention block can be written as
GQA: 2ND (D + 2DK),
CAT: 2ND (D + H),
where is sequence length, D hidden size, H number of heads, and K the key-reduction ratio in GQA. In regimes where 2DK H (typical in large models), CAT is generally not slower in practice and tends to use fewer parameters within the attention block. To check this trend empirically, Table reports like-for-like comparison of GQA and CAT under identical settings.
The empirical results are consistent with the analytical model: CAT achieves lower runtime and comparable smaller parameter counts than GQA, suggesting that their theoretical relation holds in practice.
In this small-scale sweep, with GQA) achieves both reduced parameter count and improved runtime compared with standard GQA, while maintaining comparable accuracy. Although limited in scale, this consistent trend indicates that incorporating CAT principles into GQA is promising direction for further exploration.
(i.e., replacing the attention component of CAT-Alter
C.3 Summary
Taken together, these observations suggest that replacing standard GQA with CAT-based designs (GQA-CAT-Alter) offers consistent advantages in runtime, memory, and parameter efficiency while maintaining comparable or better accuracy. This direction appears to be viable and promising path for extending GQA-style models, while potentially enabling FlashAttention-lit streaming benefits and helping mitigate FFT-related memory overheads for small sequences.
D Permutation Equivariance and Domain Applicability
When we reorder the input tokens, should the model's output stay unchanged, follow the same reordering, respond differently? This choice fixes the model's inductive bias toward order: it specifies whether the representation should ignore the order (invariance). respect up to relabeling (cquivariance), treat different orders different meanings. Match the symmetry to the task: CNNs
22

---

Model
Pool Type
Mechanism
Setting
Acc.
CLIP-B
token
Attention
0.574
CLIP-B
token
CAT-Alter
0.582
CLIP-B
token
GQA
K-1/4
0.561
CLIP-B
token
GQA-CAT-Alter
K-1/4
0.571
CLIP-B
Attention
0.638
CLIP-B avg
CAT-Alter
0,662
C
avg
GQA
K=I/I 1 0.629
CLIP-B
avg
GQA-CAT-Alter
K-1/4
0.658
Table 6: Accuracy comparison on CLIP-B (token and average pooling). CAT-Alter consistently
outperforms vanilla MHA, while the hybrid GQA-CAT-Alter improves upon standard GQA in both pooling settings. These small-scale results are consistent with our runtime findings, indicating that CAT-based extensions of GQA are empirically stable and practically efficient.
translation-cquivariane the layer level and can yield translation invariance after pooling/readout; position-fii -rre Transformers for permutation-equivaiiee In natural language. by contrast, the order of words often carries meaning (e.g., "dog bites man" vs. "man bites dog"; ; the scope of items like only negation; long-range dependencies), so the full permutation symmetry must be broken by injecting positional information (absolute or relative). This makes relative order and distance representable and typically yields small but consistent gains in practice. Spelling out the required symmetry up front clarifies what gained or lost when we modify the attention mechanism or add positional encodings.
order-agnostic inputs (c.g., sets, point clouds).
Without positional signals, self-attention layer is equivariant any permutation in the full symmetric group Sx. and becomes permutation invariant only when paired with an invariant read-out (c.g.. global pooling). By contrast, CAT's circulant mixing makes the layer equivariant cyclic shifts in Cv: with an order-agnostic read-out the overall mapping becomes invariant to cyclic shifts. Since ON a strict subgroup of Sv. cyclic-shift equivariance/iivariance does not imply equivariance/iivarianee to arbitrary permutations.
When permutation symmetry is required, for true set-structured inputs certain graph/particle systems, the symmetry must be engineered into the model explicitly. Two lightweight, design-intent examples (i) imposing canonical order via differentiable sorting (e.g., SoftSort) before applying CAT; and (ii) adopting hybrid pipeline in which an order-assigning encoder precedes CAT and permutation invarian read-out aggregates the final representation.
23


Reviews:
[{"review_id": "DJx1IIrDMa", "reviewer": "Reviewer_UTRX", "summary": "The paper is aims to improve the quadratic complexity of attention, while keeping the softmax component of it. The main approach is to define an attention operator that uses circulant operator, which can be efficiently computed via FFT. Experiments are conducted to compare the accuracy and efficiency of the proposed CAT with respect to standard self attention.", "questions": "The reviewer would love to see the concerns in the above addressed and revise the rating.", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "## Significance\n\n1. The first contribution of “EITs: a new framework” is questionable.   \n- Firstly, for a framework/class to be non-trivial, one needs multiple instances under the framework. However, it appears that the only instance the authors mention is CAT. Thus, EIT seems more like the properties of the proposed method, rather than a framework.  \n- Moreover, I do not understand why “Softmax preservation” is a property that is a priori ideal. At the end of the day, what matters seem to be efficiency (space / time), accuracy, theoretical grounds, among others. It is unclear whether “Softmax preservation” is sufficient or necessary to any of these metrics.  \n2. The proposed CAT is not well motivated and justified.   \n- The definition of CAT comes out of the blue, without any motivation on why one should use this design.   \n- The proposed CAT loses a property that self-attention has, which is permutation equivariance.   \n  1. In self-attention, if one exchanges the first two tokens in the input x, the output tokens are the same as the original ones, except that the tokens at the first two tokens are swapped.   \n     2. In CAT, one can see that $$o\\_1=z\\_1^\\*v\\_1 \\+ z\\_2^\\*v\\_2 \\+ \\\\dots \\+ z\\_Nv\\_N $$ $$o\\_2 \\= z\\_N^\\*v\\_1+z\\_1^\\*v\\_2 \\+ \\\\dots \\+ z\\_{N-1}^\\*v\\_N $$, which does not satisfy permutation equivariance. \n\n  Why would this be a good choice? \n\n3. The efficiency claim of the third contribution lacks detailed evidence.  \n- The paper mentioned multiple times that they gained 10% speedup. For the results in tables 1-3, what are the running times? Which libraries are self-attention and FFT implemented in?   \n- The authors claimed that calling FFT often “offsets theoretical advantage” \\- did the authors observe time or space usage? Again, how was FFT implemented? There seems to be a few efficient FFT implemetnations \\- have the authors tried?  \n  - [https://developer.nvidia.com/cufft](https://developer.nvidia.com/cufft)  \n  - [https://github.com/fkodom/fft-conv-pytorch](https://github.com/fkodom/fft-conv-pytorch)  \n- The ideal comparison would be to compare efficient self-attention (e.g., flashattention) with efficient CAT implementation, since this is the regime that would make an impact. \n\n## Clarity\n\n1. Notations: the notation convention is a bit confusing: Q, W\\_Q and x are all matrices, but x is the only one lower cased.   \n2. I was trying to understand the variants in the ablation study. Can the authors write down the expressions of each of the variants just as how they define CAT in section 4? Otherwise, it is hard to understand what these variants are.", "was_revised": true, "final_justification": "Thank you for the detailed clarification! It has addressed my concerns. I encourage the authors to integrate them in a revised version of the paper.", "rebuttal": "We are delighted to have this rare opportunity to receive your comments, and we greatly appreciate the time you invested in a detailed review. While the rules prevent us from updating the manuscript at this stage, we are already using your feedback to improve the next version (with replacing figures, etc). \nBelow, we address your remarks one by one.\n\n1. The first contribution of “EITs: a new framework” is questionable.\n\n> Firstly, for a framework/class to be non-trivial, one needs multiple instances under the framework. However, it appears that the only instance the authors mention is CAT. Thus, EIT seems more like the properties of the proposed method, rather than a framework. \n\nCAT is only our first concrete instantiation; we do not claim it is the only one.\nIn fact, the EIT definition is satisfied by many other transformations.\nFor example, a simple average pooling (or any learnable weighted sum) along the value stream already meets all four EIT criteria.\nLikewise, adding a constant bias or multiplying with Hadamard product before the CAT's softmax + gather operation still produces an EIT's layer, because the exact row‑wise softmax is preserved.\nBeyond circular convolutions, other Toeplitz‑structured transforms can also be devised.\n\nPut differently, once we insist on exact softmax but allow any sub‑quadratic implementation, the design space becomes as rich as the kernel choices explored by the LinearAttention family after they drop the softmax constraint. We therefore view CAT as only the first step; we expect\nfuture work, either variants of CAT or entirely different constructions, to populate the broader EIT family.\n\n> Moreover, I do not understand why “Softmax preservation” is a property that is a priori ideal.\n\nWe do not claim that exact softmax is universally optimal; efficiency, accuracy, and solid theory ultimately decide. Still, keeping softmax is worth exploring:\n- LinearAttention methods begin by discarding softmax, then explore a huge kernel space. EITs take the mirror position: we keep softmax but allow any sub‑quadratic implementation. The two lines of work are therefore complementary. exploring only one side leaves the other side under‑investigated and risks missing the sweet spot if exact soft‑max should turn out to be important.\n- Our CAT layer, which preserves softmax, is faster than baseline while matching or improving accuracy. This shows the softmax branch can be both efficient and competitive.\n\nThus, soft‑max preservation is not an article of faith, but a plausible design axis that deserves systematic investigation; CAT is simply the first data point on that axis.\n\n\n2. The proposed CAT is not well motivated and justified.\n\nThank you for highlighting the role of permutation equivariance.\nIts importance strongly depends on the domain, so we address the issue by task category below.\n\n2.1 Tasks where order carries meaning (language, vision, etc.)\n\nIn these domains, permutation equivariance is already broken on purpose by positional encodings, because absolute or relative position improves accuracy. While cat retains cyclic-shift equivariance, a restricted form of permutation equivariance in which the output permutes correctly under any circular shift of the input, CAT therefore operates under exactly the same assumptions as standard self-attention.\n\n2.2 Tasks where order is undefined or irrelevant (sets, graphs, particle systems)\n\nFor inputs that are true sets, full permutation equivariance is essential. The current form of CAT does not satisfy this requirement. However, two clear research avenues exist:\n\n    i) Explicit order prediction — adopt a learnable sorting layer (e.g., SoftSort ) and re-order the output to match the input exactly.\n    ii) Hybrid models – combine CAT with an order-assigning encoder (e.g., self-attention equipped with a positional encoding) so that CAT captures local cyclic patterns within that imposed order, while a subsequent permutation invariant read-out aggregates the final set representation.\n\nExploring these directions is outside the scope of this paper but, in our view, represents a promising next step for applying CAT-style efficiency to truly order-agnostic data.\n\n3. The efficiency claim of the third contribution lacks detailed evidence.\n\nPlease refer to the profile table (V100, FP16, Adam, Batchsize = 32):\ntorch2.7.0+cu126+cudnn9.5.1 default's cuFFT(torch.fft) / FlashAttention(F.scaled_dot_product_attention) used.\nFor each entry we report the average over 10 consecutive steps, with the runtime decomposed into three parts:\n“fwd” = forward pass, “bwd” = backward pass, and “opt” = optimizer update.\n\n| CLIP-L Variant                    | Param | Peak mem | Average time (1 iter.)|\n|-----------------------------|---------:|--------:|------------:|\n| Self‑Attn (PyTorch MatMul)     | 304.2M | 16654 MB | 1465.72 ms (fwd: 490.05 / bwd: 940.28 / opt: 35.39) |\n| Self‑Attn (FlashAttention)     | 304.2M | 13594 MB | 1467.50 ms (fwd: 465.77 / bwd: 966.46 / opt: 35.27) |\n| CAT (gather, O (N²))        | **254.2 M** | 14931 MB | 1188.48 ms (fwd: 401.12 / bwd: 757.52 / opt: 29.84) |\n| CAT (cuFFT, O (N log N))    | **254.2 M** |**11 882 MB** | **1187.85 ms** (fwd: 401.34 / bwd: 756.63 / opt: 29.88)|\n\n| GPT2-small Variant                    | Param | Peak mem | Average time (1 iter.)|\n|-----------------------------|---------:|---------:|------------:|\n| Self‑Attn (PyTorch MM)      | 107.5 M |5289.1MB | 521.57  ms (fwd: 168.99 / bwd: 339.69 / opt: 12.88) |\n| Self‑Attn (FlashAttention)     | 107.5 M |  5258.5MB | 531.05 ms (fwd: 164.75 / bwd: 350.50 / opt: 12.75) |\n| CAT (gather, O (N²))        | **93.5 M** | **4651.3 MB** | **441.78 ms** (fwd: 114.37 / bwd: 286.17 / opt: 11.24) |\n\nWe use cuFFT as the FFT backend. As the table shows, cuFFT is both fast and memory-efficient in its standard configuration, but we observed two practical issues that leave room for improvement:\n- Limited mixed-precision support — Performance drops noticeably for sequence lengths that are not powers of two.\n- High overhead for short sequences — For small N, the kernel launch and planning cost dominates, so the non-FFT (gather) version of CAT often runs faster than the cuFFT-based implementation.\n\nWe also checked fft‑conv‑pytorch, but it supports only normal convolutions and cannot handle the 4‑D circulant tensors required by CAT. Future GPUs with faster FFT kernels can furtherimprove the O (N log N) path.\n\n\nIf any of our replies are unclear or leave questions unanswered, please feel free to add further comments or adjust your evaluation. Once again, thank you very much for your thoughtful review!"}, {"review_id": "YCgyU4yY2Q", "reviewer": "Reviewer_nMKS", "summary": "The paper introduces Circulant Attention Transformer (CAT), a variant that replaces dense soft-max attention with a circulant structure amenable to FFT, yielding sub-quadratic theoretical complexity. It formalizes four “Engineering-Isomorphic Transformer (EIT)” principles showing how CAT integrates seamlessly into standard Transformer blocks, then supplies proofs-of-concept on vision (ImageNet/ViT, CLIP) and language (Transformer-XL, GPT-2) tasks. Experiments indicate comparable or slightly better accuracy in several masked- or average-pooling settings while reducing memory and wall-clock time, and the approach generalizes across modalities without architectural changes.", "questions": "* The abbreviation “FFT” (line 32) is not written out in full the first time it appears, nor is it explained.\n* “RFFT” (lines 136-137) is not explained.\n* Some of the font sizes in Figure 1 are too small and hard to read without zooming in. Also, the icons for different operations in Figure 1 are a bit small. Since there is still a lot of space in Figure 1, it is suggested to increase the font size and the size of the icons.\n* Typo: In Table 1, the “A” in “attention” in the fifth row and the third row from the bottom should be capitalized.", "limitations": "Yes", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strengths:**\n\n* Researching and optimizing foundational model architectures is a valuable and important direction.\n\n* This work offers clear complexity analysis and provides an explanation for why circulant softmax preserves key properties of full attention.\n\n* In terms of experiments, the authors demonstrate the method’s viability on both image (ViT, CLIP) and text (language modeling) benchmarks, rather than focusing on a single domain.\n\n* Even with a naïve PyTorch gather implementation, the paper reports about a 10% wall-clock speed-up and a 25% peak memory reduction on 256-token sequences. The authors suggest that larger gains are possible with custom FFT kernels.\n\n**Weaknesses:**\n\n* The scale of the experiments is somewhat small and does not reach the long-sequence capability claimed in the paper. All experiments are limited to 256-token or 224×224 image scales, while the paper’s motivation emphasizes “substantially longer sequences” (see lines 49-50: “opens new directions for longer-sequence modeling across language and vision tasks”). The experiments do not include longer context benchmarks like Long Range Arena, PG-19, or Books3, which raises concerns about the feasibility and stability of the method in real long-sequence scenarios. Although the authors mention in the conclusion that experimenting with sequences of tens of thousands of tokens is still an open challenge, evidence from only 256-token experiments is not very convincing for supporting the method’s effectiveness in long-sequence modeling.\n\n* Missing baselines: The experiments only compare standard Attention with the proposed CAT method, without comparing to other efficient attention methods such as BigBird or Longformer as mentioned in the paper. While the authors state that they tried to reproduce linear attention but gave up due to NaN issues, they did not provide details about tuning or attempts to stabilize the method.\n\n* No end-to-end latency and throughput tests: Although the paper provides theoretical analysis showing CAT’s advantages in algorithmic complexity, the experiments mainly focus on comparing CAT to standard attention in terms of performance, lacking more direct end-to-end latency and throughput tests. For example, in text generation tasks, it would be helpful to record the end-to-end generation time (in seconds) and throughput (in tokens/s) under different input/output settings. Reference can be made to works like “H$\\_2\\$O: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Models” and “Model Tells You What to Discard: Adaptive KV Cache Compression for LLMs”.\n\n* Lack of explanation for experimental phenomena: In at least half of the experimental results, the CAT method performs worse than the baseline, but the CAT-alter variant performs better than the baseline. This is confusing, because CAT-alter is essentially a mixture of CAT attention and standard attention. Intuitively, CAT-alter’s performance should fall between CAT and standard attention, not exceed the baseline when CAT itself underperforms. For example, Table 1 shows that under the pool type “token,” CAT performs worse than Attention, but CAT-alter is significantly better than Attention. Similar results can be seen in Table 2 for the LLM type “causal” experiments.\n\n* The statement “avoiding many of the pitfalls (e.g., numerical instability, partial token coverage) seen in previous approximations” (lines 29-30) is not easy for readers unfamiliar with efficient attention research to understand, and the high level of summarization does not resonate well. Also, I assume “previous approximations” refers to previous work on attention approximations? If so, I suggest the authors add proper citations.", "was_revised": true, "final_justification": "Thank you to the authors for their detailed and thoughtful rebuttal. I appreciate the effort to provide additional results and clarifications. However, after careful consideration, I have decided to maintain my original score. While the authors' responses are helpful, I believe that addressing them would require substantial new work beyond the scope of a rebuttal.\n\nIn summary, to be a compelling contribution, the paper would need to be strengthened with:\n\n1.\tExperiments on established long-sequence benchmarks to empirically validate its core claims.\n2.\tComparisons against other widely-recognized efficient attention baselines (minor concern).\n3.\tA deeper investigation or at least a plausible hypothesis for the surprising CAT-alter results.\n4.\tInference-focused benchmarks that measure end-to-end latency and throughput.\n\nThese changes may represent a significant amount of new experimental work and analysis. Nevertheless, I still see merit in this work.", "rebuttal": "We are truly grateful for the many perspectives you brought to our work! Your detailed examination covered angles we had not previously considered. Thank you for your generous contribution!\nWherever the submission format allows, we have incorporated additional material and clarifications directly into the text. For the shortcomings you identified, we share all details that we can at this stage.\n\n\n> The scale of the experiments is somewhat small and does not reach the long-sequence capability claimed in the paper. All experiments are limited to 256-token or 224×224 image scales, while the paper’s motivation emphasizes “substantially longer sequences” (see lines 49-50: “opens new directions for longer-sequence modeling across language and vision tasks”). The experiments do not include longer context benchmarks like Long Range Arena, PG-19, or Books3, which raises concerns about the feasibility and stability of the method in real long-sequence scenarios. Although the authors mention in the conclusion that experimenting with sequences of tens of thousands of tokens is still an open challenge, evidence from only 256-token experiments is not very convincing for supporting the method’s effectiveness in long-sequence modeling.\n\nOur goal was to demonstrate the asymptotic benefit of the (O(N log N)) design. \nFor truly long sequences, the quadratic cost of self‑attention grows exponentially and makes any real‑time service impossible, regardless of accuracy.  \nIn contrast, (O(N log N)) keeps computation feasible even when N is in the tens of thousands, something unattainable for standard self‑attention and still superior to sparse methods that must retune their receptive field for every sequence length.\n\nTo complement the 256‑token results in the paper, we can share one internal\nrun at 1 024 tokens (WikiText‑103):\n\n| model | task | mechanism | word PPL |\n|-------|------|-----------|---------:|\n| GPT‑2‑small | masked | Attention | 10.78 |\n| GPT‑2‑small | masked | CAT | 8.05 |\n| GPT‑2‑small | masked | **CAT‑Alter** | **6.54** |\n| GPT‑2‑small | causal | **Attention** | **24.29** |\n| GPT‑2‑small | causal | CAT | 29.80 |\n| GPT‑2‑small | causal | CAT‑Alter | 24.87 |\n\n---\n\n#### Why we did not use longer public benchmarks\n\n1. **Most reliable baselines** – ImageNet‑1k and WikiText‑103 are still the\n   most carefully vetted datasets with widely reproduced self‑attention\n   baselines.  By contrast, *Long Range Arena* can no longer be fully\n   reproduced in 2025 because several source files are unavailable; our own\n   reruns failed to match the original accuracy.  We therefore prioritized\n   benchmarks with solid ground truth.\n\n2. **Token count vs. real‑world relevance** – Artificially extending\n   ImageNet‑1k or WikiText‑103 to tens of thousands of tokens would deviate\n   from established practice and create sequences far longer than typical\n   problem settings (e.g., 256 tokens already cover about seven English\n   sentences on average).  Truly evaluating \"very long\" contexts requires\n   not just longer input but datasets where such long‑range dependencies\n   actually occur, which currently exist only in projects like *Haystack* (https://github.com/OpenGVLab/MM-NIAH) —\n   an open challenge even for conventional self‑attention.\n\nIn short, reliable long‑sequence datasets large enough to stress every\nmethod equally are still scarce.  Within the best‑validated corpora that the\ncommunity trusts today, CAT already shows promising evidence.  We believe\nfuture work on ultra‑long corpora (e.g., Haystack) will further test\nboth self‑attention and CAT, and we welcome such evaluation.\n\n\n> Missing baselines: The experiments only compare standard Attention with the proposed CAT method, without comparing to other efficient attention methods such as BigBird or Longformer as mentioned in the paper. While the authors state that they tried to reproduce linear attention but gave up due to NaN issues, they did not provide details about tuning or attempts to stabilize the method.\n\nWe intentionally excluded sparse baselines such as BigBird and Longformer, because they require sequence‑length–specific sparsity hyper‑parameters.\nOur goal was to compare against the most basic setting that involves *no* hyper‑parameter tuning, i.e., standard Attention vs CAT (vs LinearAttentions).  This rationale has now been added to Section 5.3 for clarity.\n\n\n\n> Lack of explanation for experimental phenomena: In at least half of the experimental results, the CAT method performs worse than the baseline, but the CAT-alter variant performs better than the baseline. This is confusing, because CAT-alter is essentially a mixture of CAT attention and standard attention. Intuitively, CAT-alter’s performance should fall between CAT and standard attention, not exceed the baseline when CAT itself underperforms. For example, Table 1 shows that under the pool type “token,” CAT performs worse than Attention, but CAT-alter is significantly better than Attention. Similar results can be seen in Table 2 for the LLM type “causal” experiments.\n\nWe find this phenomenon puzzling as well: combinations that we expected to decrease accuracy instead improve it. \nInterestingly, a similar effect has been reported in recent hybrid models such as Jamba, suggesting that it may reflect a deeper property of attention architectures.  Although surprising, we believe the result is reliable and have kept it as‑is while noting the open question in the discussion.\n\n\n> No end-to-end latency and throughput tests: Although the paper provides theoretical analysis showing CAT’s advantages in algorithmic complexity, the experiments mainly focus on comparing CAT to standard attention in terms of performance, lacking more direct end-to-end latency and throughput tests. For example, in text generation tasks, it would be helpful to record the end-to-end generation time (in seconds) and throughput (in tokens/s) under different input/output settings. Reference can be made to works like “HO: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Models” and “Model Tells You What to Discard: Adaptive KV Cache Compression for LLMs”.\n\nPlease refer to the profile table (V100, FP16, Adam, Batchsize = 32):\ntorch2.7.0+cu126+cudnn9.5.1 default's cuFFT(torch.fft) / FlashAttention(F.scaled_dot_product_attention) used.\nFor each entry we report the average over 10 consecutive steps, with the runtime decomposed into three parts:\n“fwd” = forward pass, “bwd” = backward pass, and “opt” = optimizer update.\n\n| CLIP-L Variant                    | Param | Peak mem | Average time (1 iter.)|\n|-----------------------------|---------:|--------:|------------:|\n| Self‑Attn (PyTorch MatMul)     | 304.2M | 16654 MB | 1465.72 ms (fwd: 490.05 / bwd: 940.28 / opt: 35.39) |\n| Self‑Attn (FlashAttention)     | 304.2M | 13594 MB | 1467.50 ms (fwd: 465.77 / bwd: 966.46 / opt: 35.27) |\n| CAT (gather, O (N²))        | **254.2 M** | 14931 MB | 1188.48 ms (fwd: 401.12 / bwd: 757.52 / opt: 29.84) |\n| CAT (cuFFT, O (N log N))    | **254.2 M** |**11 882 MB** | **1187.85 ms** (fwd: 401.34 / bwd: 756.63 / opt: 29.88)|\n\n| GPT2-small Variant                    | Param | Peak mem | Average time (1 iter.)|\n|-----------------------------|---------:|---------:|------------:|\n| Self‑Attn (PyTorch MatMul)      | 107.5 M |5289.1MB | 521.57  ms (fwd: 168.99 / bwd: 339.69 / opt: 12.88) |\n| Self‑Attn (FlashAttention)     | 107.5 M |  5258.5MB | 531.05 ms (fwd: 164.75 / bwd: 350.50 / opt: 12.75) |\n| CAT (gather, O (N²))        | **93.5 M** | **4651.3 MB** | **441.78 ms** (fwd: 114.37 / bwd: 286.17 / opt: 11.24) |\n\nRegarding the issues you raised, we believe the rebuttal now provides substantial evidence, especially the new experimental results, that CAT is already a viable option for large‑scale use. If these additions address your concerns, we would appreciate a reconsideration of your overall score. Should any reservations remain, please feel free to let us know; your comments will not only improve our paper but also guide future researchers working on related methods.\nOnce again, thank you for investing your time and effort in such a thorough review, we sincerely appreciate it!"}, {"review_id": "tRB1TuLTj0", "reviewer": "Reviewer_NYeX", "summary": "This work introduces Circular Convolutional Attention (CAT), a Fourier-based alternative to standard attention that replaces the O(N^2) complexity with a more scalable O(N log N) formulation. By leveraging circular convolutions in the frequency domain, CAT preserves representational capacity while reducing computational cost and parameter count by simplifying the fully connected layers. The method reports ~10% speedups in naive PyTorch implementations without relying on heavier operations. CAT demonstrates improvements in accuracy and perplexity across both vision and language tasks, under both masked and causal transformer settings.", "questions": "1. Compatibility: Can CAT be combined with other efficient attention mechanisms like GQA or FlashAttention, or is it intended as a standalone replacement? Please provide numerical comparisons for this.\n\n2. Deployment: Does CAT support transfer to pretrained models (e.g., via fine-tuning), or does it require full training from scratch? If from scratch, then this should be discussed in the paper regarding its practicality.\n\n3. Scope of Modifications: Are the convolutional replacements limited to QK projections, or can the same principle be extended to FFN layers or other modules?\n\n4. Target Efficiency: Is the focus of CAT primarily on improving inference speed or training efficiency? Can the authors provide wall-clock runtimes and detailed bottleneck breakdowns for the baseline and method in the target setting? Also, consider both the FLOPs scaling and memory costs.\n\n5. Visual Evidence: Can the authors include attention map visualizations or other forms of qualitative analysis to demonstrate that CAT preserves the structure and utility of standard attention?\n\nCurrently, my biggest concern with the work is that I am uncertain whether it really performs better than existing, well used and performing sparse or optimized attention algorithms such as GQA.", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. The proposed approach achieves O(N log N) complexity by leveraging the fourier transform and viewing attention as a circular shift matrix, which is a creative and well-motivated direction. I believe there is novelty in this approach, which makes it an interesting solution.\n\n2. The authors target a known bottleneck—attention's quadratic complexity—so the potential savings are practically meaningful, especially in long-sequence settings. Reducing parameter count and maintaining accuracy while improving speed is a valuable contribution.\n\nWeaknesses:\nDespite the well-motivated and creative interpretation, I have some concerns:\n\n1. Limited Baselines: The paper primarily compares CAT to a standard baseline model, without including other relevant efficiency-focused attention methods. Notably, BlockSparse Attention variants and Grouped Query Attention (GQA) are not included. These are commonly used in practice to reduce computation and memory. Without such comparisons, it's unclear how CAT performs relative to the current state-of-the-art. The discussion on MHA in the main paper is sufficient; however, MHA won't have savings natively (i.e, parameters are still full rank, only head-independence aids in performance). In a case like GQA, LLama3 may have 1/4 output channels on KV, meanwhile Qwen2 is far less (~1/8), so to validate the effectiveness of CAT it should be compared with current methods of compute reduction.\n\n2. Training from Scratch: It is not clearly stated whether CAT can be applied to existing pretrained models or if it requires training from scratch with new parameters. If the latter, this significantly limits its adoption potential, especially in settings where full retraining is infeasible.\n\n3. Ambiguity in Efficiency Target: The paper does not clearly distinguish whether the proposed method targets training efficiency, inference speed, or both. These have different runtime bottlenecks and trade-offs. Furthermore, the absence of a detailed runtime profile or FLOPs breakdown for the baseline makes it difficult to assess the real-world impact of the claimed 10% speedup.\n\n4. Memory Reduction Claims: The claim of reduced parameter count is made, but no concrete statistics are given for memory usage or parameter reduction in practice -- the same applies to the latency/runtime; very little information is provided about it.\n\n5. Representation: Since CAT replaces traditional attention weights with a form of circular convolution (circular shift matrix), it's important to validate that representational capacity is preserved. However, the paper lacks any qualitative or visual support (e.g., attention maps) to demonstrate this.\n\n6. Unclear Scope: In Figure 2, the improvements seem to target the V projection paths. However, with the original goal being to optimize the N^2 component (i.e, QK) it begs the question that if the V is considered, why not the linear layers in the FFN, which would have similar scaling to the linear V projection.\n\n7. Presentation: The paper’s explanation of the method, particularly in Figure 1, lacks clarity. The overall changes to the attention architecture are not well localized or visualized. This makes it difficult to understand exactly what components are being modified or replaced. Overall, the writing clarity/quality (and inclusion of related works, which is missing many sparse attention works) needs significant improvement.", "was_revised": true, "final_justification": "The author addressed my main concern on compatibility with efficient attention techniques, hence I have increased my score. I do still have other concerns with this work, however my main concern was resolved.", "rebuttal": "We deeply appreciate the careful reading and detailed understanding you have shown; receiving such thorough feedback is a rare and valuable opportunity for us!\nFigures 1 & 2 and the attention maps visualizations have already been updated in the manuscript. Because mid‑review edits are prohibited, we cannot share the revised PDF here, but we are re‑drawing the figures with explicit intermediate‑tensor sizes and clearer captions. Several items you asked about can nevertheless be reported below.\n\n> Compatibility: Can CAT be combined with other efficient attention mechanisms like GQA or FlashAttention, or is it intended as a standalone replacement? Please provide numerical comparisons for this.\n\nAll mechanisms you listed can in fact be combined with CAT, and we expect CAT to be advantageous in both complexity and accuracy.\n\nConceptual analysis\n* FlashAttention + CAT – Flash’s streaming soft‑max removes the temporary attention matrix; applying the same idea to CAT is straightforward and should eliminate the extra memory from the gather step, especially useful when FFT overhead dominates at small N.\n* GQA + CAT – In theory, CAT still wins on arithmetic cost. Let N=sequence length, D=hidden size, H=#heads, K=GQA’s key reduction ratio. For the feed‑forward part only: GQA: 2ND(D+2DK), CAT: 2ND(D+H). Whenever 2DK>H (true for Llama‑3 70B, Qwen 2, etc.), CAT is no slower even in O(N^2) form and offers lower parameter count.\n\nRuntime evidence\n\nPlease refer to the profile table (V100, FP16, Adam, Batchsize = 32):\ntorch2.7.0+cu126+cudnn9.5.1 default's cuFFT(torch.fft) / FlashAttention(F.scaled_dot_product_attention) used.\nFor each entry we report the average over 10 consecutive steps, with the runtime decomposed into three parts:\n“fwd” = forward pass, “bwd” = backward pass, and “opt” = optimizer update.\n\n| CLIP-L Variant                    | Param | Peak mem | Average time (1 iter.)|\n|-----------------------------|---------:|--------:|------------:|\n| Self‑Attn (PyTorch MatMul)     | 304.2M | 16654 MB | 1465.72 ms (fwd: 490.05 / bwd: 940.28 / opt: 35.39) |\n| **GQA K=1/4 (PyTorch MatMul)**     | 260.3M | 16510 MB | 1307.26 ms (fwd: 436.12 / bwd: 839.86 / opt: 31.28) |\n| **GQA K=1/16 (PyTorch MatMul)**     | 257.0M | 16474 MB | 1270.39 ms (fwd: 430.02 / bwd: 810.05 / opt: 30.33) |\n| CAT (gather, O (N²))        | **254.2 M** | **14931 MB** | **1188.48 ms** (fwd: 401.12 / bwd: 757.52 / opt: 29.84) |\n\nAccuracy on a small sweep\n| model | task | mechanism | Accuracy |\n|-------|------|-----------|---------:|\n| CLIP-B | token | MHA  | 0.574 |\n| CLIP-B | token | CAT-alter  | 0.582 |\n| CLIP-B | token | **GQA K=1/4**  | 0.561 |\n| CLIP-B | token | **GQA-CAT-alter K=1/4**  | **0.571** |\n| CLIP-B | avg | MHA | 0.638 |\n| CLIP-B | avg | CAT-alter | 0.662 |\n| CLIP-B | avg | **GQA K=1/4**  | 0.629 |\n| CLIP-B | avg | **GQA-CAT-alter K=1/4**  | **0.658** |\n\nBoth tables suggest CAT is at least competitive and often ahead in practice. While a comprehensive large‑scale study would be ideal, these results provide a strong indication that CAT integrates well with existing efficiency techniques.\n\nWhy we benchmark mainly against vanilla MHA.  Since its original proposal in 2017, plain MHA has served as the community’s de‑facto “anchor.”  Many lightweight variants  are explicitly advertised as faster but sometimes less accurate than that anchor (e.g., GQA: https://arxiv.org/abs/2305.13245 / https://arxiv.org/abs/2412.20677 ). \n\nIn our study CAT‑alter matches MHA’s accuracy, so the logical forecast is\n\n GQA ≤ MHA ≤ CAT‑alter ⇒  GQA ≤ GQA‑CAT‑alter ≤ CAT‑alter.\n\nOur small‑scale test confirms this inequality.  Moreover, CAT’s (O(N log N)) arithmetic cost dominates the constant‑factor reductions offered by GQA, and CAT keeps comparable accuracy.  \nEven without an exhaustive grid search over all hyper‑parameter combinations, these results provide a reliable prediction: replacing MHA with CAT (or CAT‑alter) is at least as safe, and often strictly better, as replacing it with GQA.\n\n> Scope of Modifications: Are the convolutional replacements limited to QK projections, or can the same principle be extended to FFN layers or other modules?\n\nCAT is designed for the attention block; it cannot be dropped into an FFN unchanged. That said, sub‑quadratic FFN designs might borrow the same frequency‑domain trick.\nhttps://arxiv.org/abs/1901.10255\n\n\n> Target Efficiency: Is the focus of CAT primarily on improving inference speed or training efficiency? Can the authors provide wall-clock runtimes and detailed bottleneck breakdowns for the baseline and method in the target setting? Also, consider both the FLOPs scaling and memory costs.\n\nCAT reduces FLOPs and activations regardless of training or inference, so both phases speed up.\n(The wall‑clock numbers and bottleneck breakdowns are included in the profile following.)\n\nPlease refer to the profile table (V100, FP16, Adam, Batchsize = 32):\ntorch2.7.0+cu126+cudnn9.5.1 default's cuFFT(torch.fft) / FlashAttention(F.scaled_dot_product_attention) used.\n\n| CLIP-L Variant                    | Param | Peak mem | Average time (1 iter.) |\n|-----------------------------|---------:|--------:|------------:|\n| Self‑Attn (PyTorch MatMul)     | 304.2M | 16654 MB | 1465.72 ms (fwd: 490.05 / bwd: 940.28 / opt: 35.39) |\n| Self‑Attn (FlashAttention)     | 304.2M | 13594 MB | 1467.50 ms (fwd: 465.77 / bwd: 966.46 / opt: 35.27) |\n| CAT (gather, O (N²))        | **254.2 M** | 14931 MB | 1188.48 ms (fwd: 401.12 / bwd: 757.52 / opt: 29.84) |\n| CAT (cuFFT, O (N log N))    | **254.2 M** |**11 882 MB** | **1187.85 ms** (fwd: 401.34 / bwd: 756.63 / opt: 29.88)|\n\n| GPT2-small Variant                    | Param | Peak mem | Average time (1 iter.)|\n|-----------------------------|---------:|---------:|------------:|\n| Self‑Attn (PyTorch MatMul)      | 107.5 M |5289.1MB | 521.57  ms (fwd: 168.99 / bwd: 339.69 / opt: 12.88) |\n| Self‑Attn (FlashAttention)     | 107.5 M |  5258.5MB | 531.05 ms (fwd: 164.75 / bwd: 350.50 / opt: 12.75) |\n| CAT (gather, O (N²))        | **93.5 M** | **4651.3 MB** | **441.78 ms** (fwd: 114.37 / bwd: 286.17 / opt: 11.24) |\n\n\nIf these clarifications resolve your concerns, or if questions remain, we would welcome an updated score or additional comments.Thank you again for dedicating so much time and effort to our work; we truly appreciate it!"}]

Author rebuttal:

Meta-review: The paper proposes an alternative to standard attention in Transformers that is based on circular convolutions and allows efficient speedup through Fourier domain computation, reducing complexity to be n log n instead of quadratic in sequence length.

While the final scores stand at accept, borderline accept, and borderline reject, all reviewers acknowledge the merit of the idea and work. Overall, the rebuttal added experimental evaluations that helped ameliorate many of the reviewers' concerns. While two of the reviewers are positive, the borderline negative reviewer notes that the paper may need more experimental results to fully resolve their concerns.

After considering all reviews and the rebuttal, AC believes that while additional results could add value to the paper, they are not strictly necessary. The novelty of the method and the existing results (in the paper and the rebuttal) are sufficient to clear the bar for acceptance, and the work is likely to be of considerable interest to the NeurIPS audience.
Decision: Accept (poster)