# Computational Limits of Low-Rank Adaptation (LoRA) Fine-Tuning for Transformer Models

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

## Key facts

- Cited by 31 papers in the map (data through 14 Oct 2026).
- Builds on 62 of its 89 references that are in the map.
- First posted on arXiv 5 Jun 2024.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [LoRA: Low-Rank Adaptation of Large Language Models](https://mlsanity.com/paper/2106.09685/) (2021)
- [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)
- [On the Opportunities and Risks of Foundation Models](https://mlsanity.com/paper/2108.07258/) (2021)
- [OPT: Open Pre-trained Transformer Language Models](https://mlsanity.com/paper/2205.01068/) (2022)
- [QLoRA: Efficient Finetuning of Quantized LLMs](https://mlsanity.com/paper/2305.14314/) (2023)
- [Large Language Models Encode Clinical Knowledge](https://mlsanity.com/paper/2212.13138/) (2022)
- [LlamaFactory: Unified Efficient Fine-Tuning of 100+ Language Models](https://mlsanity.com/paper/2403.13372/) (2024)
- [BloombergGPT: A Large Language Model for Finance](https://mlsanity.com/paper/2303.17564/) (2023)
- [On Layer Normalization in the Transformer Architecture](https://mlsanity.com/paper/2002.04745/) (2020)
- [DoRA: Weight-Decomposed Low-Rank Adaptation](https://mlsanity.com/paper/2402.09353/) (2024)
- [Libri-Light: A Benchmark for ASR with Limited or No Supervision](https://mlsanity.com/paper/1912.07875/) (2019)
- [LoRA+: Efficient Low Rank Adaptation of Large Models](https://mlsanity.com/paper/2402.12354/) (2024)
- [LoraHub: Efficient Cross-Task Generalization via Dynamic LoRA Composition](https://mlsanity.com/paper/2307.13269/) (2023)
- [Learning Deep Transformer Models for Machine Translation](https://mlsanity.com/paper/1906.01787/) (2019)
- [Massive Activations in Large Language Models](https://mlsanity.com/paper/2402.17762/) (2024)
- [FinGPT: Open-Source Financial Large Language Models](https://mlsanity.com/paper/2306.06031/) (2023)
- [LoftQ: LoRA-Fine-Tuning-Aware Quantization for Large Language Models](https://mlsanity.com/paper/2310.08659/) (2023)
- [HyenaDNA: Long-Range Genomic Sequence Modeling at Single Nucleotide Resolution](https://mlsanity.com/paper/2306.15794/) (2023)
- [Delta Tuning: A Comprehensive Study of Parameter Efficient Methods for Pre-trained Language Models](https://mlsanity.com/paper/2203.06904/) (2022)
- [QA-LoRA: Quantization-Aware Low-Rank Adaptation of Large Language Models](https://mlsanity.com/paper/2309.14717/) (2023)
- [Quantizable Transformers: Removing Outliers by Helping Attention Heads Do Nothing](https://mlsanity.com/paper/2306.12929/) (2023)
- [DNABERT-2: Efficient Foundation Model and Benchmark For Multi-Species Genome](https://mlsanity.com/paper/2306.15006/) (2023)
- [Fast Attention Requires Bounded Entries](https://mlsanity.com/paper/2302.13214/) (2023)
- [The Expressive Power of Low-Rank Adaptation](https://mlsanity.com/paper/2310.17513/) (2023)
- [Sparse Low-rank Adaptation of Pre-trained Language Models](https://mlsanity.com/paper/2311.11696/) (2023)
- [LQ-LoRA: Low-rank Plus Quantized Matrix Decomposition for Efficient Language Model Finetuning](https://mlsanity.com/paper/2311.12023/) (2023)

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

- [On Statistical Rates and Provably Efficient Criteria of Latent Diffusion Transformers (DiTs)](https://mlsanity.com/paper/2407.01079/) (2024)
- [Do Large Language Models Have Compositional Ability? An Investigation into Limitations and Scalability](https://mlsanity.com/paper/2407.15720/) (2024)
- [Multi-Layer Transformers Gradient Can be Approximated in Almost Linear Time](https://mlsanity.com/paper/2408.13233/) (2024)
- [The Computational Limits of State-Space Models and Mamba via the Lens of Circuit Complexity](https://mlsanity.com/paper/2412.06148/) (2024)
- [Looped ReLU MLPs May Be All You Need as Practical Programmable Computers](https://mlsanity.com/paper/2410.09375/) (2024)
- [Your Vision-Language Model Can't Even Count to 20: Exposing the Failures of VLMs in Compositional Counting](https://mlsanity.com/paper/2510.04401/) (2025)
- [Theoretical Constraints on the Expressive Power of mathsfRoPE-based Tensor Attention Transformers](https://mlsanity.com/paper/2412.18040/) (2024)
- [Towards Infinite-Long Prefix in Transformer](https://mlsanity.com/paper/2406.14036/) (2024)
- [Circuit Complexity Bounds for Visual Autoregressive Model](https://mlsanity.com/paper/2501.04299/) (2025)
- [On Computational Limits of FlowAR Models: Expressivity and Efficiency](https://mlsanity.com/paper/2502.16490/) (2025)
- [T2VTextBench: A Human Evaluation Benchmark for Textual Control in Video Generation Models](https://mlsanity.com/paper/2505.04946/) (2025)
- [Fundamental Limitations on Subquadratic Alternatives to Transformers](https://mlsanity.com/paper/2410.04271/) (2024)
- [Fast RoPE Attention: Combining the Polynomial Method and Fast Fourier Transform](https://mlsanity.com/paper/2505.11892/) (2025)
- [Bayesian-LoRA: LoRA based Parameter Efficient Fine-Tuning using Optimal Quantization levels and Rank Values trough Differentiable Bayesian Gates](https://mlsanity.com/paper/2406.13046/) (2024)
- [Fast and Low-Cost Genomic Foundation Models via Outlier Removal](https://mlsanity.com/paper/2505.00598/) (2025)
- [Only Large Weights (And Not Skip Connections) Can Prevent the Perils of Rank Collapse](https://mlsanity.com/paper/2505.16284/) (2025)
- [Investigating Low-Rank Training in Transformer Language Models: Efficiency and Scaling Analysis](https://mlsanity.com/paper/2407.09835/) (2024)
- [Scaling Law Phenomena Across Regression Paradigms: Multiple and Kernel Approaches](https://mlsanity.com/paper/2503.01314/) (2025)
- [Minimalist Softmax Attention Provably Learns Constrained Boolean Functions](https://mlsanity.com/paper/2505.19531/) (2025)
- [Differentially Private Kernel Density Estimation](https://mlsanity.com/paper/2409.01688/) (2024)
- [When Can We Solve the Weighted Low Rank Approximation Problem in Truly Subquadratic Time?](https://mlsanity.com/paper/2502.16912/) (2025)
- [Time and Memory Trade-off of KV-Cache Compression in Tensor Transformer Decoding](https://mlsanity.com/paper/2503.11108/) (2025)
- [Theoretical Foundation of Flow-Based Time Series Generation: Provable Approximation, Generalization, and Efficiency](https://mlsanity.com/paper/2503.14076/) (2025)
- [Two Heads Are Better than One: Simulating Large Transformers with Small Ones](https://mlsanity.com/paper/2506.12220/) (2025)
- [Tight Sample Complexity for Low-Rank Adaptation: Matching Bounds and Rank Selection](https://mlsanity.com/paper/2607.27680/) (2026)
- [Singular Value Decomposition on Kronecker Adaptation for Large Language Model](https://mlsanity.com/paper/2506.15251/) (2025)
- [Norm-Bounded Low-Rank Adaptation](https://mlsanity.com/paper/2501.19050/) (2025)
- [Efficient Temporal Tokenization for Mobility Prediction with Large Language Models](https://mlsanity.com/paper/2507.14017/) (2025)
- [Fundamental Limits of Crystalline Equivariant Graph Neural Networks: A Circuit Complexity Perspective](https://mlsanity.com/paper/2510.05494/) (2025)
- [Few-Shot Continual Learning for 3D Brain MRI with Frozen Foundation Models](https://mlsanity.com/paper/2602.23533/) (2026)

## Abstract (arXiv)

We study the computational limits of Low-Rank Adaptation (LoRA) for finetuning transformer-based models using fine-grained complexity theory. Our key observation is that the existence of low-rank decompositions within the gradient computation of LoRA adaptation leads to possible algorithmic speedup. This allows us to (i) identify a phase transition behavior of efficiency assuming the Strong Exponential Time Hypothesis (SETH), and (ii) prove the existence of almost linear algorithms by controlling the LoRA update computation term by term. For the former, we identify a sharp transition in the efficiency of all possible rank-r LoRA update algorithms for transformers, based on specific norms resulting from the multiplications of the input sequence X, pretrained weights W^star, and adapter matrices α B A/r. Specifically, we derive a shared upper bound threshold for such norms, and show that efficient (sub-quadratic) approximation algorithms of LoRA exist only below this threshold. For the latter, we prove the existence of almost linear approximation algorithms for LoRA adaptation by utilizing the hierarchical low-rank structures of LoRA gradients and approximating the gradients with a series of chained low-rank approximations. To showcase our theory, we consider two practical scenarios: partial (e.g., only WV and WQ) and full adaptations (e.g., WQ, WV, and WK) of weights in attention heads.