mlsanityData to 14 Oct 2026

Theoretical Constraints on the Expressive Power of mathsfRoPE-based Tensor Attention Transformers

arXiv 2412.18040 ↗First posted 23 Dec 2024cs.LG cs.AI cs.CCcited by 12

Not on the map. Why?

Abstract (arXiv)

Tensor Attention extends traditional attention mechanisms by capturing high-order correlations across multiple modalities, addressing the limitations of classical matrix-based attention. Meanwhile, Rotary Position Embedding (mathsfRoPE) has shown superior performance in encoding positional information in long-context scenarios, significantly enhancing transformer models' expressiveness. Despite these empirical successes, the theoretical limitations of these technologies remain underexplored. In this study, we analyze the circuit complexity of Tensor Attention and mathsfRoPE-based Tensor Attention, showing that with polynomial precision, constant-depth layers, and linear or sublinear hidden dimension, they cannot solve fixed membership problems or (AF,r)^* closure problems, under the assumption that mathsfTC0 neq mathsfNC1. These findings highlight a gap between the empirical performance and theoretical constraints of Tensor Attention and mathsfRoPE-based Tensor Attention Transformers, offering insights that could guide the development of more theoretically grounded approaches to Transformer model design and scaling.

Key facts. Cited by 12 papers in the map (data through 14 Oct 2026). Builds on 57 of its 90 references that are in the map. First posted on arXiv 23 Dec 2024.

Builds on

57 of 90 references.

References · 57

  1. 2017Attention Is All You Needcited by 60,361
  2. 2023GPT-4 Technical Reportcited by 18,396
  3. 2024The Llama 3 Herd of Modelscited by 14,715
  4. 2021RoFormer: Enhanced Transformer with Rotary Position Embeddingcited by 4,703
  5. 2023Towards Revealing the Mystery behind Chain of Thought: A Theoretical Perspectivecited by 294
  6. 2022Transformers Learn Shortcuts to Automatacited by 268
  7. 2022The Parallelism Tradeoff: Limitations of Log-Precision Transformerscited by 193
  8. 2021Saturated Transformers are Constant-Depth Threshold Circuitscited by 139
  9. 2023Representational Strengths and Limitations of Transformerscited by 133
  10. 2017Recovery Guarantees for One-hidden-layer Neural Networkscited by 94
  11. 2022A Logic for Expressing Log-Precision Transformerscited by 67
  12. 2014Spectral Methods meet EM: A Provably Optimal Algorithm for Crowdsourcingcited by 63
38 more
  1. 2021Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Timecited by 62
  2. 2023An Over-parameterized Exponential Regressioncited by 45
  3. 2023How to Capture Higher-order Correlations? Generalizing Matrix Softmax Attention to Kronecker Computationcited by 44
  4. 2024On Computational Limits of Modern Hopfield Models: A Fine-Grained Complexity Analysiscited by 41
  5. 2024On Statistical Rates and Provably Efficient Criteria of Latent Diffusion Transformers (DiTs)cited by 40
  6. 2024Do Large Language Models Have Compositional Ability? An Investigation into Limitations and Scalabilitycited by 40
  7. 2024Discovering the Gems in Early Layers: Accelerating Long-Context LLMs with 1000x Input Token Reductioncited by 39
  8. 2013Sequential Transfer in Multi-armed Bandit with Finite Set of Modelscited by 38
  9. 2024Uniform Memory Retrieval with Larger Capacity for Modern Hopfield Modelscited by 38
  10. 2017Tensor Robust Principal Component Analysis: Exact Recovery of Corrupted Low-Rank Tensors via Convex Optimizationcited by 35
  11. 2023STanHop: Sparse Tandem Hopfield Model for Memory-Enhanced Time Series Predictioncited by 35
  12. 2024Conv-Basis: A New Paradigm for Efficient Attention Inference and Gradient Computation in Transformerscited by 32
  13. 2024Computational Limits of Low-Rank Adaptation (LoRA) Fine-Tuning for Transformer Modelscited by 31
  14. 2024Training Tensor Attention Efficiently: From Cubic to Almost Linear Timecited by 30
  15. 2016Solving a Mixture of Many Random Linear Equations by Tensor Decomposition and Alternating Minimizationcited by 26
  16. 2024Circuit Complexity Bounds for RoPE-based Transformer Architecturecited by 26
  17. 2024Transformers in Uniform TC0cited by 25
  18. 2024Fourier Circuits in Neural Networks and Transformers: A Case Study of Modular Arithmetic with Multiple Inputscited by 22
  19. 2024Multi-Layer Transformers Gradient Can be Approximated in Almost Linear Timecited by 22
  20. 2024Bypassing the Exponential Dependency: Looped Transformers Efficiently Learn In-context by Multi-step Gradient Descentcited by 22
  21. 2024Fundamental Limits of Prompt Tuning Transformers: Universality, Capacity and Efficiencycited by 22
  22. 2024BiSHop: Bi-Directional Cellular Learning for Tabular Data with Generalized Sparse Modern Hopfield Modelcited by 21
  23. 2024The Computational Limits of State-Space Models and Mamba via the Lens of Circuit Complexitycited by 21
  24. 2019SF-Net: Structured Feature Network for Continuous Sign Language Recognitioncited by 20
  25. 2024Beyond Linear Approximations: A Novel Pruning Approach for Attention Matrixcited by 20
  26. 2022What is my math transformer doing? -- Three results on interpretability and generalizationcited by 19
  27. 2024A Tighter Complexity Analysis of SparseGPTcited by 19
  28. 2024Looped ReLU MLPs May Be All You Need as Practical Programmable Computerscited by 19
  29. 2024HSR-Enhanced Sparse Attention Accelerationcited by 19
  30. 2024Provably Optimal Memory Capacity for Modern Hopfield Models: Transformer-Compatible Dense Associative Memories as Spherical Codescited by 19
  31. 2024Provable Differentially Private Computation of the Cross-Attention Mechanismcited by 14
  32. 2022A Nearly Optimal Size Coreset Algorithm with Nearly Linear Timecited by 13
  33. 2021Deep Online Fused Video Stabilizationcited by 11
  34. 2024On Fine-Grained I/O Complexity of Attention Backward Passescited by 11
  35. 2021Attentive Walk-Aggregating Graph Neural Networkscited by 10
  36. 2023A Theoretical Analysis Of Nearest Neighbor Search On Approximate Near Neighbor Graphcited by 10
  37. 2023An Automatic Learning Rate Schedule Algorithm for Achieving Faster Convergence and Steeper Descentcited by 9
  38. 2024Modern Hopfield Networks Require Chain-of-Thought to Solve mathsfNC1-Hard Problemscited by 9

50 most cited of 57 All 57 (JSON)

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 10; 2026: 2.

12 papers.

  1. 2025Your Vision-Language Model Can't Even Count to 20: Exposing the Failures of VLMs in Compositional Countingcited by 18
  2. 2025Circuit Complexity Bounds for Visual Autoregressive Modelcited by 10
  3. 2025On Computational Limits of FlowAR Models: Expressivity and Efficiencycited by 10
  4. 2025Neural Algorithmic Reasoning for Hypergraphs with Looped Transformerscited by 4
  5. 2025Scaling Law Phenomena Across Regression Paradigms: Multiple and Kernel Approachescited by 4
  6. 2025Minimalist Softmax Attention Provably Learns Constrained Boolean Functionscited by 4
  7. 2025Too Easily Fooled? Prompt Injection Breaks LLMs on Frustratingly Simple Multiple-Choice Questionscited by 4
  8. 2025Time and Memory Trade-off of KV-Cache Compression in Tensor Transformer Decodingcited by 2
  9. 2025Theoretical Foundation of Flow-Based Time Series Generation: Provable Approximation, Generalization, and Efficiencycited by 2
  10. 2026Geometric Capacity of Transformers: A Tropical Geometry Perspectivecited by 1
  11. 2026Revisiting Padded Transformer Expressivity: Which Architectural Choices Matter and Which Don'tcited by 1
  12. 2025Fundamental Limits of Crystalline Equivariant Graph Neural Networks: A Circuit Complexity Perspectivecited by 0