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

2024/06/05 by Jerry Yao-Chieh Hu, Maojiang Su, Hu, Jerry Yao-Chieh +7 · 7 citations
Computer Science · Engineering · Materials Science · #Artificial Intelligence (cs.AI) #Computational Complexity (cs.CC) #Energy Load and Power Forecasting #FOS: Computer and information sciences #Image and Signal Denoising Methods #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Magnetic Properties and Applications

paper · pdf · doi:10.48550/arxiv.2406.03136

openalex publication_date 2024/06/05 · openalex created_date 2024/06/08 · openalex updated_date 2026/07/28

Abstract

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^⋆, 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 W_V and W_Q) and full adaptations (e.g., W_Q, W_V, and W_K) of weights in attention heads.

Cited by

• Fundamental Limits of Crystalline Equivariant Graph Neural Networks: A Circuit Complexity Perspective
• Your Vision-Language Model Can't Even Count to 20: Exposing the Failures of VLMs in Compositional Counting
• RHYTHM: Reasoning with Hierarchical Temporal Tokenization for Human Mobility
• Tight Sample Complexity for Low-Rank Adaptation: Matching Bounds and Rank Selection
• Efficient Temporal Tokenization for Mobility Prediction with Large Language Models
• Singular Value Decomposition on Kronecker Adaptation for Large Language Model
• Two Heads Are Better than One: Simulating Large Transformers with Small Ones

Related

• RandLoRA: Full-rank parameter-efficient fine-tuning of large models
• The Expressive Power of Low-Rank Adaptation
• LoRA+: Efficient Low Rank Adaptation of Large Models
• Norm-Bounded Low-Rank Adaptation
• A Single Linear Layer Yields Task-Adapted Low-Rank Matrices