Transformer's Quadratic Complexity and Black-Box Problem: Alternatives and the Causal Grassmann Transformer

Introduction

Since the 2017 paper *Attention Is All You Need* (Vaswani et al.), Transformer-based models have become the foundation of NLP and much of deep learning. However, two inherent challenges have grown more prominent as models scale:

1. Quadratic computational complexity of self-attention 2. The "black-box" interpretability problem

The post argues that the paper *Attention Is Not What You Need* (arXiv:2512.19428), which proposes the Causal Grassmann Transformer, offers an innovative combined solution to both problems.

Key points

1. Core challenges of the Transformer

• Quadratic complexity: Self-attention computes pairwise relations between all tokens via Attention(Q, K, V) = softmax(QK^T / sqrt(d_k))V. The n×n attention score matrix dominates costs:
• O(n²·d_k) for the QKᵀ matrix multiplication
• O(n²) for the softmax operation
• O(n²·d_v) for the weighted sum
• Overall approximately O(n²·d) in both time and memory.
• Black-box problem: The core Transformer operation is a "high-dimensional tensor lifting" that raises each token's d-dimensional hidden state into an L×L pairwise compatibility tensor space. This space of L² elements has huge degrees of freedom, attention tensor "clouds" evolve across layers and heads, and there is no clear family of invariants describing global effects — making the process mathematically intractable.

2. Existing alternatives

For complexity:

• Sparse attention: restricting each token to attend to a small subset — Longformer (sliding window + global), BigBird (local + global + random), Reformer (locality-sensitive hashing).
• Linear attention: kernel approximations of softmax exploiting associativity of matrix multiplication — Linformer (low-rank projection), Performer (FAVOR+), FlashAttention (IO-aware exact optimization).

For interpretability:

• White-box architectures such as CRATE (Coding and Rate Reduction Transformer), where every layer has an explicit mathematical objective — maximizing coding rate reduction.
• Geometry/physics-inspired designs: replacing hard-to-track high-dimensional tensor operations with evolution on manifolds with clear mathematical structure.

3. New model: Causal Grassmann Transformer

The paper's fundamental question: is the explicit L×L self-attention weight tensor truly necessary for strong sequence modeling and reasoning?

• It proposes an attention-free sequence model that reduces complexity from O(n²) toward O(n) for long sequences.
• It provides inherent geometric interpretability via an architecture based on Grassmann manifolds, where model dynamics are evolutions on a space with well-defined mathematical structure rather than opaque tensor operations.

4. Conclusion and outlook

The post concludes that explicit pairwise attention may not be a fundamental requirement for sequence modeling, and that geometric approaches like the Causal Grassmann Transformer point toward architectures that are simultaneously more efficient and more interpretable — though practical validation at scale remains an open question.

References cited in the post:

• Attention Is Not What You Need (arXiv:2512.19428)
• Complexity analysis of self-attention (CSDN)
• Sparse attention survey (Juejin)
• Linear attention overview (CSDN)
• CRATE white-box Transformer (BAAI Hub)