mlsanityData to 7 Oct 2026

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

arXiv 2310.04064 ↗First posted 6 Oct 2023cs.DS cs.CC cs.CLcited by 44

Not on the map. Why?

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.

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

Builds on

49 of 77 references.

References · 49

  1. 2017Attention Is All You Needcited by 59,932
  2. 2018BERT: Pre-training of Deep Bidirectional Transformers for Language Understandingcited by 40,204
  3. 2020Language Models are Few-Shot Learnerscited by 32,199
  4. 2023LLaMA: Open and Efficient Foundation Language Modelscited by 13,958
  5. 2023Llama 2: Open Foundation and Fine-Tuned Chat Modelscited by 12,865
  6. 2022PaLM: Scaling Language Modeling with Pathwayscited by 5,304
  7. 2022FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awarenesscited by 3,611
  8. 2022OPT: Open Pre-trained Transformer Language Modelscited by 3,464
  9. 2023FlashAttention-2: Faster Attention with Better Parallelism and Work Partitioningcited by 2,551
  10. 2023Code Llama: Open Foundation Models for Codecited by 2,105
  11. 2020Transformers are RNNs: Fast Autoregressive Transformers with Linear Attentioncited by 1,979
  12. 2020Reformer: The Efficient Transformercited by 1,658
37 more
  1. 2020Rethinking Attention with Performerscited by 1,584
  2. 2019Generating Long Sequences with Sparse Transformerscited by 1,523
  3. 2020Linformer: Self-Attention with Linear Complexitycited by 1,462
  4. 2022SmoothQuant: Accurate and Efficient Post-Training Quantization for Large Language Modelscited by 1,338
  5. 2022LLM.int8(): 8-bit Matrix Multiplication for Transformers at Scalecited by 881
  6. 2023H2O: Heavy-Hitter Oracle for Efficient Generative Inference of Large Language Modelscited by 805
  7. 2019Q8BERT: Quantized 8Bit BERTcited by 296
  8. 2022cosFormer: Rethinking Softmax in Attentioncited by 212
  9. 2019Tensor Programs I: Wide Feedforward or Recurrent Neural Networks of Any Architecture are Gaussian Processescited by 148
  10. 2020Tensor Programs II: Neural Tangent Kernel for Any Architecturecited by 139
  11. 2022On The Computational Complexity of Self-Attentioncited by 137
  12. 2023Representational Strengths and Limitations of Transformerscited by 132
  13. 2021Scatterbrain: Unifying Sparse and Low-rank Attention Approximationcited by 128
  14. 2023Fast Attention Requires Bounded Entriescited by 102
  15. 2021Pixelated Butterfly: Simple and Efficient Sparse training for Neural Network Modelscited by 75
  16. 2021Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Timecited by 62
  17. 2023KDEformer: Accelerating Transformers via Kernel Density Estimationcited by 58
  18. 2020Tensor Programs III: Neural Matrix Lawscited by 47
  19. 2017Relative Error Tensor Low Rank Approximationcited by 45
  20. 2020SMYRF: Efficient Attention using Asymmetric Clusteringcited by 43
  21. 2023Algorithm and Hardness for Dynamic Attention Maintenance in Large Language Modelscited by 37
  22. 2021Fast Sketching of Polynomial Kernels of Polynomial Degreecited by 33
  23. 2023A Fast Optimization View: Reformulating Single Layer Attention in LLM Based on Tensor and SVM Trick, and Solving It in Matrix Multiplication Timecited by 30
  24. 2017Sketching for Kronecker Product Regression and P-splinescited by 29
  25. 2019Optimal Sketching for Kronecker Product Regression and Low Rank Approximationcited by 29
  26. 2023Efficient Post-training Quantization with FP8 Formatscited by 29
  27. 2023Differentially Private Attention Computationcited by 25
  28. 2023GradientCoin: A Peer-to-Peer Decentralized Large Language Modelscited by 23
  29. 2020Algorithms and Hardness for Linear Algebra on Geometric Graphscited by 22
  30. 2022Sketching Meets Differential Privacy: Fast Algorithm for Dynamic Kronecker Projection Maintenancecited by 22
  31. 2023Training and inference of large language models using 8-bit floating pointcited by 20
  32. 2013Smoothed Analysis of Tensor Decompositionscited by 19
  33. 2018Hardness of Approximate Nearest Neighbor Searchcited by 19
  34. 2022Optimal-Degree Polynomial Approximations for Exponentials and Gaussian Kernel Density Estimationcited by 19
  35. 2023A Nearly-Optimal Bound for Fast Regression with ℓ_∞ Guaranteecited by 14
  36. 2023Faster Robust Tensor Power Method for Arbitrary Ordercited by 8
  37. 2023Streaming Semidefinite Programs: O(√n) Passes, Small Space and Fast Runtimecited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 5; 2024: 19; 2025: 18; 2026: 2.

44 papers.

Sort:

By area:

  1. 2024Uniform Memory Retrieval with Larger Capacity for Modern Hopfield Modelscited by 38
  2. 2024Outlier-Efficient Hopfield Layers for Large Transformer-Based Modelscited by 38
  3. 2024LazyDiT: Lazy Learning for the Acceleration of Diffusion Transformerscited by 35
  4. 2024Computational Limits of Low-Rank Adaptation (LoRA) Fine-Tuning for Transformer Modelscited by 31
  5. 2024The Fine-Grained Complexity of Gradient Computation for Training Large Language Modelscited by 30
  6. 2024Training Tensor Attention Efficiently: From Cubic to Almost Linear Timecited by 29
  7. 2024Circuit Complexity Bounds for RoPE-based Transformer Architecturecited by 26
  8. 2024Multi-Layer Transformers Gradient Can be Approximated in Almost Linear Timecited by 22
  9. 2024The Computational Limits of State-Space Models and Mamba via the Lens of Circuit Complexitycited by 21
  10. 2024Looped ReLU MLPs May Be All You Need as Practical Programmable Computerscited by 19
  11. 2024HSR-Enhanced Sparse Attention Accelerationcited by 19
  12. 2025T2VWorldBench: A Benchmark for Evaluating World Knowledge in Text-to-Video Generationcited by 18
32 more
  1. 2025Your Vision-Language Model Can't Even Count to 20: Exposing the Failures of VLMs in Compositional Countingcited by 17
  2. 2023Why Softmax Attention Outperforms Linear Attentioncited by 15
  3. 2024Provable Differentially Private Computation of the Cross-Attention Mechanismcited by 14
  4. 2024RoPE Attention Can Be Trained in Almost Linear Timecited by 13
  5. 2024Theoretical Constraints on the Expressive Power of mathsfRoPE-based Tensor Attention Transformerscited by 12
  6. 2025On Computational Limits of FlowAR Models: Expressivity and Efficiencycited by 10
  7. 2024Modern Hopfield Networks Require Chain-of-Thought to Solve mathsfNC1-Hard Problemscited by 9
  8. 2025Theoretical Guarantees for High Order Trajectory Refinement in Generative Flowscited by 9
  9. 2025Fast RoPE Attention: Combining the Polynomial Method and Fast Fourier Transformcited by 9
  10. 2023The Expressibility of Polynomial based Attention Schemecited by 7
  11. 2025Only Large Weights (And Not Skip Connections) Can Prevent the Perils of Rank Collapsecited by 7
  12. 2023A Theoretical Insight into Attack and Defense of Gradient Leakage in Transformercited by 6
  13. 2023One Pass Streaming Algorithm for Super Long Token Attention Approximation in Sublinear Spacecited by 6
  14. 2025Towards High-Order Mean Flow Generative Models: Feasibility, Expressivity, and Provably Efficient Criteriacited by 5
  15. 2025Scaling Law Phenomena Across Regression Paradigms: Multiple and Kernel Approachescited by 4
  16. 2025Minimalist Softmax Attention Provably Learns Constrained Boolean Functionscited by 4
  17. 2025Too Easily Fooled? Prompt Injection Breaks LLMs on Frustratingly Simple Multiple-Choice Questionscited by 4
  18. 2024When big data actually are low-rank, or entrywise approximation of certain function-generated matricescited by 3
  19. 2025Neural Algorithmic Reasoning for Hypergraphs with Looped Transformerscited by 3
  20. 2025When Can We Solve the Weighted Low Rank Approximation Problem in Truly Subquadratic Time?cited by 3
  21. 2024Differentially Private Kernel Density Estimationcited by 2
  22. 2025Time and Memory Trade-off of KV-Cache Compression in Tensor Transformer Decodingcited by 2
  23. 2025Theoretical Foundation of Flow-Based Time Series Generation: Provable Approximation, Generalization, and Efficiencycited by 2
  24. 2024Binary Hypothesis Testing for Softmax Models and Leverage Score Modelscited by 1
  25. 2024Long Sequence Modeling with Attention Tensorization: From Sequence to Tensor Learningcited by 1
  26. 2025Towards Sampling Data Structures for Tensor Products in Turnstile Streamscited by 1
  27. 2025Unifying Learning Dynamics and Generalization in Transformers Scaling Lawcited by 1
  28. 2023Fast Heavy Inner Product Identification Between Weights and Inputs in Neural Network Trainingcited by 0
  29. 2025Fundamental Limits of Crystalline Equivariant Graph Neural Networks: A Circuit Complexity Perspectivecited by 0
  30. 2025How Smoothing is N-simplicial Attention?cited by 0
  31. 2026Tracking High-order Evolutions via Cascading Low-rank Fittingcited by 0
  32. 2026Beyond Sparse Weights: When Is Attention Compressible?cited by 0