Research map / Learning theory and algorithms / Matrix and tensor methods
How to Capture Higher-order Correlations? Generalizing Matrix Softmax Attention to Kronecker Computation
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Generalizes matrix softmax attention to a triple-wise (Kronecker) tensor attention and proves a sharp bounded-entry threshold B = Θ(∛log n) separating near-linear-time approximation from SETH-based n^{3-o(1)} hardness.
Problem
Attention captures only pairwise token correlations; a tensor generalization capturing triple-wise correlations appears to cost cubic time, and the fine-grained complexity of approximating it was unknown.
Approach
Define tensor attention via column-wise Kronecker products of key/value matrices, show that exp of the Kronecker-structured score matrix admits a low-rank polynomial approximation (polynomial method) when entries are bounded by o(∛log n), enabling n^{1+o(1)} time, and prove a matching SETH lower bound via a 3-party MaxIP-style gap problem built from an MA protocol with algebraic geometry codes.
Key results
- Bounded-entry tensor attention (entries o(∛log n)) can be approximated in n^{1+o(1)} time.
- For entries Ω(∛log n), no algorithm runs in n^{3-o(1)} time under SETH.
- For k-th order tensors the threshold becomes B < ∛... i.e., k-th root of log n, giving a tradeoff between entry bound and tensor order.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Bound all input entries by B = o(∛log n) | Tensor attention computation (ATAttC) · ATAttC with d = O(log n) and ε_a = 1/poly(n) | runtime: n^{1+o(1)} | Helped |
| Allow entries as large as B = C_b ∛log n | Tensor attention computation (ATAttC) · ATAttC with d = C log n and ε_a = n^{-C_a} | runtime: O(n^{3-q}) | Hurt |
| Increase attention order to k and require B < √[k]{log n} | Higher-order attention · k-th order tensor attention | runtime: near-linear time | Helped |
| Use entries at or above B = √[k]{log n} for k-th order attention | Higher-order attention · k-th order tensor attention | runtime: O(n^k) | Hurt |
Surprising findings
- The entry bound for tensor attention is stricter (∛log n) than for matrix attention (√log n), so higher-order expressivity requires tighter boundedness for efficiency.
Limitations
- Purely theoretical; no experiments on trained transformers.
- Upper bound requires entries bounded by o(∛log n), which may not hold in practice.
Experimental setup
Metrics: running time complexity entrywise approximation error
Baselines: standard matrix attention computation trivial cubic-time tensor attention algorithm
Builds on: fast attention computation via polynomial method (Alman and Song 2023) SETH-based hardness of attention computation tensor generalization of attention (Sanford et al. triple-wise task)
Closest papers by meaning
- Improved Algorithms for Kernel Matrix-Vector Multiplication Under Sparsity Assumptions (ICLR 2025 · similarity 0.86)
- Customizing the Inductive Biases of Softmax Attention using Structured Matrices (ICML 2025 · similarity 0.85)
- Metric Transforms and Low Rank Representations of Kernels for Fast Attention (NeurIPS 2024 · similarity 0.85)
- Mind the Gap: a Spectral Analysis of Rank Collapse and Signal Propagation in Attention Layers (ICML 2025 · similarity 0.85)
- Understanding the Kronecker Matrix-Vector Complexity of Linear Algebra (ICML 2025 · similarity 0.84)
- LevAttention: Time, Space and Streaming Efficient Algorithm for Heavy Attentions (ICLR 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.