# A Fast Optimization View: Reformulating Single Layer Attention in LLM Based on Tensor and SVM Trick, and Solving It in Matrix Multiplication Time

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

## Key facts

- Cited by 30 papers in the map (data through 14 Oct 2026).
- Builds on 158 of its 207 references that are in the map.
- First posted on arXiv 14 Sep 2023.

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

- [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)
- [Direct Preference Optimization: Your Language Model is Secretly a Reward Model](https://mlsanity.com/paper/2305.18290/) (2023)
- [Scaling Laws for Neural Language Models](https://mlsanity.com/paper/2001.08361/) (2020)
- [Neural Machine Translation by Jointly Learning to Align and Translate](https://mlsanity.com/paper/1409.0473/) (2014)
- [Prefix-Tuning: Optimizing Continuous Prompts for Generation](https://mlsanity.com/paper/2101.00190/) (2021)
- [OPT: Open Pre-trained Transformer Language Models](https://mlsanity.com/paper/2205.01068/) (2022)
- [Locating and Editing Factual Associations in GPT](https://mlsanity.com/paper/2202.05262/) (2022)
- [Sparks of Artificial General Intelligence: Early experiments with GPT-4](https://mlsanity.com/paper/2303.12712/) (2023)
- [Reformer: The Efficient Transformer](https://mlsanity.com/paper/2001.04451/) (2020)
- [Show, Attend and Tell: Neural Image Caption Generation with Visual Attention](https://mlsanity.com/paper/1502.03044/) (2015)
- [Is Your Code Generated by ChatGPT Really Correct? Rigorous Evaluation of Large Language Models for Code Generation](https://mlsanity.com/paper/2305.01210/) (2023)
- [Effective Approaches to Attention-based Neural Machine Translation](https://mlsanity.com/paper/1508.04025/) (2015)
- [A Multitask, Multilingual, Multimodal Evaluation of ChatGPT on Reasoning, Hallucination, and Interactivity](https://mlsanity.com/paper/2302.04023/) (2023)
- [A Convergence Theory for Deep Learning via Over-Parameterization](https://mlsanity.com/paper/1811.03962/) (2018)
- [Discovering Latent Knowledge in Language Models Without Supervision](https://mlsanity.com/paper/2212.03827/) (2022)
- [Gradient Descent Provably Optimizes Over-parameterized Neural Networks](https://mlsanity.com/paper/1810.02054/) (2018)
- [The Implicit Bias of Gradient Descent on Separable Data](https://mlsanity.com/paper/1710.10345/) (2017)
- [Knowledge Neurons in Pretrained Transformers](https://mlsanity.com/paper/2104.08696/) (2021)
- [On Exact Computation with an Infinitely Wide Neural Net](https://mlsanity.com/paper/1904.11955/) (2019)
- [Fine-Grained Analysis of Optimization and Generalization for Overparameterized Two-Layer Neural Networks](https://mlsanity.com/paper/1901.08584/) (2019)
- [Is ChatGPT a General-Purpose Natural Language Processing Task Solver?](https://mlsanity.com/paper/2302.06476/) (2023)
- [Fine-Tuning Language Models with Just Forward Passes](https://mlsanity.com/paper/2305.17333/) (2023)
- [Kernel and Rich Regimes in Overparametrized Models](https://mlsanity.com/paper/2002.09277/) (2020)
- [MEGA: Multilingual Evaluation of Generative AI](https://mlsanity.com/paper/2303.12528/) (2023)
- [On Evaluating Adversarial Robustness of Large Vision-Language Models](https://mlsanity.com/paper/2305.16934/) (2023)
- [Sentiment Analysis in the Era of Large Language Models: A Reality Check](https://mlsanity.com/paper/2305.15005/) (2023)

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

- [How to Capture Higher-order Correlations? Generalizing Matrix Softmax Attention to Kronecker Computation](https://mlsanity.com/paper/2310.04064/) (2023)
- [On Statistical Rates and Provably Efficient Criteria of Latent Diffusion Transformers (DiTs)](https://mlsanity.com/paper/2407.01079/) (2024)
- [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)
- [Conv-Basis: A New Paradigm for Efficient Attention Inference and Gradient Computation in Transformers](https://mlsanity.com/paper/2405.05219/) (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)
- [The Computational Limits of State-Space Models and Mamba via the Lens of Circuit Complexity](https://mlsanity.com/paper/2412.06148/) (2024)
- [A Tighter Complexity Analysis of SparseGPT](https://mlsanity.com/paper/2408.12151/) (2024)
- [HSR-Enhanced Sparse Attention Acceleration](https://mlsanity.com/paper/2410.10165/) (2024)
- [Why Softmax Attention Outperforms Linear Attention](https://mlsanity.com/paper/2310.11685/) (2023)
- [Exploring the Frontiers of Softmax: Provable Optimization, Applications in Diffusion Model, and Beyond](https://mlsanity.com/paper/2405.03251/) (2024)
- [High-Order Matching for One-Step Shortcut Diffusion Models](https://mlsanity.com/paper/2502.00688/) (2025)
- [A Unified Scheme of ResNet and Softmax](https://mlsanity.com/paper/2309.13482/) (2023)
- [Video Latent Flow Matching: Optimal Polynomial Projections for Video Interpolation and Extrapolation](https://mlsanity.com/paper/2502.00500/) (2025)
- [Theoretical Guarantees for High Order Trajectory Refinement in Generative Flows](https://mlsanity.com/paper/2503.09069/) (2025)
- [An Automatic Learning Rate Schedule Algorithm for Achieving Faster Convergence and Steeper Descent](https://mlsanity.com/paper/2310.11291/) (2023)
- [Local Convergence of Approximate Newton Method for Two Layer Nonlinear Regression](https://mlsanity.com/paper/2311.15390/) (2023)
- [Fast John Ellipsoid Computation with Differential Privacy Optimization](https://mlsanity.com/paper/2408.06395/) (2024)
- [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)
- [How to Inverting the Leverage Score Distribution?](https://mlsanity.com/paper/2404.13785/) (2024)
- [Subquadratic Algorithms and Hardness for Attention with Any Temperature](https://mlsanity.com/paper/2505.14840/) (2025)
- [Scaling Law Phenomena Across Regression Paradigms: Multiple and Kernel Approaches](https://mlsanity.com/paper/2503.01314/) (2025)
- [Inverting the Leverage Score Gradient: An Efficient Approximate Newton Method](https://mlsanity.com/paper/2408.11267/) (2024)
- [LevAttention: Time, Space, and Streaming Efficient Algorithm for Heavy Attentions](https://mlsanity.com/paper/2410.05462/) (2024)
- [Time and Memory Trade-off of KV-Cache Compression in Tensor Transformer Decoding](https://mlsanity.com/paper/2503.11108/) (2025)
- [Accept More, Reject Less: Reducing up to 19% Unnecessary Desk-Rejections over 11 Years of ICLR Data](https://mlsanity.com/paper/2506.20141/) (2025)
- [Attention at the Theoretical Minimum: A Mathematics of Arrays Framework for Memory-Optimal Transformer Kernels](https://mlsanity.com/paper/2606.07713/) (2026)
- [Fast Heavy Inner Product Identification Between Weights and Inputs in Neural Network Training](https://mlsanity.com/paper/2311.11429/) (2023)

## Abstract (arXiv)

Large language models (LLMs) have played a pivotal role in revolutionizing various facets of our daily existence. Solving attention regression is a fundamental task in optimizing LLMs. In this work, we focus on giving a provable guarantee for the one-layer attention network objective function L(X,Y) = sumj0 = 1n sumi0 = 1d ( langle langle exp( mathsfAj0 x ) , bf 1n rangle-1 exp( mathsfAj0 x ), A3 Y*,i0 rangle - bj0,i0 )2. Here mathsfA ∈ ℝn2 × d2 is Kronecker product between A1 ∈ ℝn × d and A2 ∈ ℝn × d. A3 is a matrix in ℝn × d, mathsfAj0 ∈ ℝn × d2 is the j0-th block of mathsfA. The X, Y ∈ ℝd × d are variables we want to learn. B ∈ ℝn × d and bj0,i0 ∈ ℝ is one entry at j0-th row and i0-th column of B, Y*,i0 ∈ ℝd is the i0-column vector of Y, and x ∈ ℝd2 is the vectorization of X. In a multi-layer LLM network, the matrix B ∈ ℝn × d can be viewed as the output of a layer, and A1= A2 = A3 ∈ ℝn × d can be viewed as the input of a layer. The matrix version of x can be viewed as QK^top and Y can be viewed as V. We provide an iterative greedy algorithm to train loss function L(X,Y) up ε that runs in widetildeO( (cal Tmat(n,n,d) + cal Tmat(n,d,d) + d2ω) log(1/ε) ) time. Here cal Tmat(a,b,c) denotes the time of multiplying a × b matrix another b × c matrix, and ω≈ 2.37 denotes the exponent of matrix multiplication.