# How to Capture Higher-order Correlations? Generalizing Matrix Softmax Attention to Kronecker Computation

arXiv: https://arxiv.org/abs/2310.04064 · HTML: https://mlsanity.com/paper/2310.04064/

## Key facts

- Cited by 44 papers in the map (data through 14 Oct 2026).
- Builds on 49 of its 77 references that are in the map.
- First posted on arXiv 6 Oct 2023.

## Builds on (most cited first, 30 of 49)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [LLaMA: Open and Efficient Foundation Language Models](https://mlsanity.com/paper/2302.13971/) (2023)
- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [PaLM: Scaling Language Modeling with Pathways](https://mlsanity.com/paper/2204.02311/) (2022)
- [FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness](https://mlsanity.com/paper/2205.14135/) (2022)
- [OPT: Open Pre-trained Transformer Language Models](https://mlsanity.com/paper/2205.01068/) (2022)
- [FlashAttention-2: Faster Attention with Better Parallelism and Work Partitioning](https://mlsanity.com/paper/2307.08691/) (2023)
- [Code Llama: Open Foundation Models for Code](https://mlsanity.com/paper/2308.12950/) (2023)
- [Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention](https://mlsanity.com/paper/2006.16236/) (2020)
- [Reformer: The Efficient Transformer](https://mlsanity.com/paper/2001.04451/) (2020)
- [Rethinking Attention with Performers](https://mlsanity.com/paper/2009.14794/) (2020)
- [Generating Long Sequences with Sparse Transformers](https://mlsanity.com/paper/1904.10509/) (2019)
- [Linformer: Self-Attention with Linear Complexity](https://mlsanity.com/paper/2006.04768/) (2020)
- [SmoothQuant: Accurate and Efficient Post-Training Quantization for Large Language Models](https://mlsanity.com/paper/2211.10438/) (2022)
- [LLM.int8(): 8-bit Matrix Multiplication for Transformers at Scale](https://mlsanity.com/paper/2208.07339/) (2022)
- [H2O: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Models](https://mlsanity.com/paper/2306.14048/) (2023)
- [Q8BERT: Quantized 8Bit BERT](https://mlsanity.com/paper/1910.06188/) (2019)
- [cosFormer: Rethinking Softmax in Attention](https://mlsanity.com/paper/2202.08791/) (2022)
- [Tensor Programs I: Wide Feedforward or Recurrent Neural Networks of Any Architecture are Gaussian Processes](https://mlsanity.com/paper/1910.12478/) (2019)
- [Tensor Programs II: Neural Tangent Kernel for Any Architecture](https://mlsanity.com/paper/2006.14548/) (2020)
- [On The Computational Complexity of Self-Attention](https://mlsanity.com/paper/2209.04881/) (2022)
- [Representational Strengths and Limitations of Transformers](https://mlsanity.com/paper/2306.02896/) (2023)
- [Scatterbrain: Unifying Sparse and Low-rank Attention Approximation](https://mlsanity.com/paper/2110.15343/) (2021)
- [Fast Attention Requires Bounded Entries](https://mlsanity.com/paper/2302.13214/) (2023)
- [Pixelated Butterfly: Simple and Efficient Sparse training for Neural Network Models](https://mlsanity.com/paper/2112.00029/) (2021)
- [Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Time](https://mlsanity.com/paper/2112.07628/) (2021)
- [KDEformer: Accelerating Transformers via Kernel Density Estimation](https://mlsanity.com/paper/2302.02451/) (2023)
- [Tensor Programs III: Neural Matrix Laws](https://mlsanity.com/paper/2009.10685/) (2020)

## Built on by (most cited first, 30 of 44)

- [Uniform Memory Retrieval with Larger Capacity for Modern Hopfield Models](https://mlsanity.com/paper/2404.03827/) (2024)
- [Outlier-Efficient Hopfield Layers for Large Transformer-Based Models](https://mlsanity.com/paper/2404.03828/) (2024)
- [LazyDiT: Lazy Learning for the Acceleration of Diffusion Transformers](https://mlsanity.com/paper/2412.12444/) (2024)
- [Computational Limits of Low-Rank Adaptation (LoRA) Fine-Tuning for Transformer Models](https://mlsanity.com/paper/2406.03136/) (2024)
- [The Fine-Grained Complexity of Gradient Computation for Training Large Language Models](https://mlsanity.com/paper/2402.04497/) (2024)
- [Training Tensor Attention Efficiently: From Cubic to Almost Linear Time](https://mlsanity.com/paper/2405.16411/) (2024)
- [Circuit Complexity Bounds for RoPE-based Transformer Architecture](https://mlsanity.com/paper/2411.07602/) (2024)
- [Multi-Layer Transformers Gradient Can be Approximated in Almost Linear Time](https://mlsanity.com/paper/2408.13233/) (2024)
- [The Computational Limits of State-Space Models and Mamba via the Lens of Circuit Complexity](https://mlsanity.com/paper/2412.06148/) (2024)
- [Looped ReLU MLPs May Be All You Need as Practical Programmable Computers](https://mlsanity.com/paper/2410.09375/) (2024)
- [HSR-Enhanced Sparse Attention Acceleration](https://mlsanity.com/paper/2410.10165/) (2024)
- [T2VWorldBench: A Benchmark for Evaluating World Knowledge in Text-to-Video Generation](https://mlsanity.com/paper/2507.18107/) (2025)
- [Your Vision-Language Model Can't Even Count to 20: Exposing the Failures of VLMs in Compositional Counting](https://mlsanity.com/paper/2510.04401/) (2025)
- [Why Softmax Attention Outperforms Linear Attention](https://mlsanity.com/paper/2310.11685/) (2023)
- [Provable Differentially Private Computation of the Cross-Attention Mechanism](https://mlsanity.com/paper/2407.14717/) (2024)
- [RoPE Attention Can Be Trained in Almost Linear Time](https://mlsanity.com/paper/2412.17316/) (2024)
- [Theoretical Constraints on the Expressive Power of mathsfRoPE-based Tensor Attention Transformers](https://mlsanity.com/paper/2412.18040/) (2024)
- [On Computational Limits of FlowAR Models: Expressivity and Efficiency](https://mlsanity.com/paper/2502.16490/) (2025)
- [Theoretical Guarantees for High Order Trajectory Refinement in Generative Flows](https://mlsanity.com/paper/2503.09069/) (2025)
- [Modern Hopfield Networks Require Chain-of-Thought to Solve mathsfNC1-Hard Problems](https://mlsanity.com/paper/2412.05562/) (2024)
- [Fast RoPE Attention: Combining the Polynomial Method and Fast Fourier Transform](https://mlsanity.com/paper/2505.11892/) (2025)
- [The Expressibility of Polynomial based Attention Scheme](https://mlsanity.com/paper/2310.20051/) (2023)
- [Only Large Weights (And Not Skip Connections) Can Prevent the Perils of Rank Collapse](https://mlsanity.com/paper/2505.16284/) (2025)
- [A Theoretical Insight into Attack and Defense of Gradient Leakage in Transformer](https://mlsanity.com/paper/2311.13624/) (2023)
- [One Pass Streaming Algorithm for Super Long Token Attention Approximation in Sublinear Space](https://mlsanity.com/paper/2311.14652/) (2023)
- [Towards High-Order Mean Flow Generative Models: Feasibility, Expressivity, and Provably Efficient Criteria](https://mlsanity.com/paper/2508.07102/) (2025)
- [Neural Algorithmic Reasoning for Hypergraphs with Looped Transformers](https://mlsanity.com/paper/2501.10688/) (2025)
- [Scaling Law Phenomena Across Regression Paradigms: Multiple and Kernel Approaches](https://mlsanity.com/paper/2503.01314/) (2025)
- [Minimalist Softmax Attention Provably Learns Constrained Boolean Functions](https://mlsanity.com/paper/2505.19531/) (2025)
- [Too Easily Fooled? Prompt Injection Breaks LLMs on Frustratingly Simple Multiple-Choice Questions](https://mlsanity.com/paper/2508.13214/) (2025)

## Abstract (arXiv)

In the classical transformer attention scheme, we are given three n × d size matrices Q, K, V (the query, key, and value tokens), and the goal is to compute a new n × d size matrix D-1 exp(QK^top) V where D = diag( exp(QK^top) bf 1n ). In this work, we study a generalization of attention which captures triple-wise correlations. This generalization is able to solve problems about detecting triple-wise connections that were shown to be impossible for transformers. The potential downside of this generalization is that it appears as though computations are even more difficult, since the straightforward algorithm requires cubic time in n. However, we show that in the bounded-entry setting (which arises in practice, and which is well-studied in both theory and practice), there is actually a near-linear time algorithm. More precisely, we show that bounded entries are both necessary and sufficient for quickly performing generalized computations: bullet On the positive side, if all entries of the input matrices are bounded above by o(√[3]log n) then we show how to approximate the ``tensor-type'' attention matrix in n1+o(1) time. bullet On the negative side, we show that if the entries of the input matrices may be as large as Omega(√[3]log n), then there is no algorithm that runs faster than n3-o(1) (assuming the Strong Exponential Time Hypothesis from fine-grained complexity theory). We also show that our construction, algorithms, and lower bounds naturally generalize to higher-order tensors and correlations. Interestingly, the higher the order of the tensors, the lower the bound on the entries needs to be for an efficient algorithm. Our results thus yield a natural tradeoff between the boundedness of the entries, and order of the tensor one may use for more expressive, efficient attention computation.