# Solving Tensor Low Cycle Rank Approximation

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 45 of its 94 references that are in the map.
- First posted on arXiv 13 Apr 2023.

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

- [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)
- [PaLM: Scaling Language Modeling with Pathways](https://mlsanity.com/paper/2204.02311/) (2022)
- [OPT: Open Pre-trained Transformer Language Models](https://mlsanity.com/paper/2205.01068/) (2022)
- [Pre-train, Prompt, and Predict: A Systematic Survey of Prompting Methods in Natural Language Processing](https://mlsanity.com/paper/2107.13586/) (2021)
- [HuggingFace's Transformers: State-of-the-art Natural Language Processing](https://mlsanity.com/paper/1910.03771/) (2019)
- [Multilingual Denoising Pre-training for Neural Machine Translation](https://mlsanity.com/paper/2001.08210/) (2020)
- [Transformers learn in-context by gradient descent](https://mlsanity.com/paper/2212.07677/) (2022)
- [A Watermark for Large Language Models](https://mlsanity.com/paper/2301.10226/) (2023)
- [What Can Transformers Learn In-Context? A Case Study of Simple Function Classes](https://mlsanity.com/paper/2208.01066/) (2022)
- [What learning algorithm is in-context learning? Investigations with linear models](https://mlsanity.com/paper/2211.15661/) (2022)
- [Beyond English-Centric Multilingual Machine Translation](https://mlsanity.com/paper/2010.11125/) (2020)
- [Pre-trained Models for Natural Language Processing: A Survey](https://mlsanity.com/paper/2003.08271/) (2020)
- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [Fast Attention Requires Bounded Entries](https://mlsanity.com/paper/2302.13214/) (2023)
- [Solving Linear Programs in the Current Matrix Multiplication Time](https://mlsanity.com/paper/1810.07896/) (2018)
- [Neural Machine Translation: A Review and Survey](https://mlsanity.com/paper/1912.02047/) (2019)
- [How Do Transformers Learn Topic Structure: Towards a Mechanistic Understanding](https://mlsanity.com/paper/2303.04245/) (2023)
- [Training Multi-Layer Over-Parametrized Neural Network in Subquadratic Time](https://mlsanity.com/paper/2112.07628/) (2021)
- [Training (Overparametrized) Neural Networks in Near-Linear Time](https://mlsanity.com/paper/2006.11648/) (2020)
- [KDEformer: Accelerating Transformers via Kernel Density Estimation](https://mlsanity.com/paper/2302.02451/) (2023)
- [An Improved Cutting Plane Method for Convex Optimization, Convex-Concave Games and its Applications](https://mlsanity.com/paper/2004.04250/) (2020)
- [Do Transformers Parse while Predicting the Masked Word?](https://mlsanity.com/paper/2303.08117/) (2023)
- [Relative Error Tensor Low Rank Approximation](https://mlsanity.com/paper/1704.08246/) (2017)
- [An Over-parameterized Exponential Regression](https://mlsanity.com/paper/2303.16504/) (2023)
- [Solving Regularized Exp, Cosh and Sinh Regression Problems](https://mlsanity.com/paper/2303.15725/) (2023)
- [A Deterministic Linear Program Solver in Current Matrix Multiplication Time](https://mlsanity.com/paper/1910.11957/) (2019)
- [Approximating How Single Head Attention Learns](https://mlsanity.com/paper/2103.07601/) (2021)
- [Randomized and Deterministic Attention Sparsification Algorithms for Over-parameterized Feature Dimension](https://mlsanity.com/paper/2304.04397/) (2023)

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

- [The Closeness of In-Context Learning and Weight Shifting for Softmax Regression](https://mlsanity.com/paper/2304.13276/) (2023)
- [The Fine-Grained Complexity of Gradient Computation for Training Large Language Models](https://mlsanity.com/paper/2402.04497/) (2024)
- [Why Softmax Attention Outperforms Linear Attention](https://mlsanity.com/paper/2310.11685/) (2023)
- [Faster Robust Tensor Power Method for Arbitrary Order](https://mlsanity.com/paper/2306.00406/) (2023)
- [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 Sampling Data Structures for Tensor Products in Turnstile Streams](https://mlsanity.com/paper/2510.03678/) (2025)
- [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 have become ubiquitous in modern life, finding applications in various domains such as natural language processing, language translation, and speech recognition. Recently, a breakthrough work [Zhao, Panigrahi, Ge, and Arora Arxiv 2023] explains the attention model from probabilistic context-free grammar (PCFG). One of the central computation task for computing probability in PCFG is formulating a particular tensor low rank approximation problem, we can call it tensor cycle rank. Given an n × n × n third order tensor A, we say that A has cycle rank-k if there exists three n × k2 size matrices U , V, and W such that for each entry in each beginalign* Aa,b,c = sumi=1k sumj=1k suml=1k Ua,i+k(j-1) otimes Vb, j + k(l-1) otimes Wc, l + k(i-1)  endalign* for all a ∈ [n], b ∈ [n], c ∈ [n]. For the tensor classical rank, tucker rank and train rank, it has been well studied in [Song, Woodruff, Zhong SODA 2019]. In this paper, we generalize the previous ``rotation and sketch'' technique in page 186 of [Song, Woodruff, Zhong SODA 2019] and show an input sparsity time algorithm for cycle rank.