ICLR 2025
Computational Limits of Low-Rank Adaptation (LoRA) Fine-Tuning for Transformer Models
When can low-rank fine-tuning be computed efficiently, and where are its limits?
Abstract
We study the computational limits of Low-Rank Adaptation (LoRA) update 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 and (ii) prove the existence of nearly linear algorithms by controlling the LoRA update computation term by term, assuming the Strong Exponential Time Hypothesis (SETH).
Key results
A computational phase transition
Identify a norm-dependent boundary between efficient approximation and conditional hardness under the Strong Exponential Time Hypothesis.
Almost-linear algorithms
Exploit hierarchical low-rank structure to approximate the gradients involved in LoRA fine-tuning.
Partial and full adaptation
Analyze different choices of trainable attention projections within the same computational framework.
BibTeX
Official BibTeX from ICLR Proceedings.
@inproceedings{ICLR2025_12143893,
author = {Hu, Jerry Yao-Chieh and Su, Maojiang and Kuo, En-Jui and Song, Zhao and Liu, Han},
booktitle = {International Conference on Learning Representations},
editor = {Y. Yue and A. Garg and N. Peng and F. Sha and R. Yu},
pages = {6167--6206},
title = {Computational Limits of Low-Rank Adaptation (LoRA) Fine-Tuning for Transformer Models},
url = {https://proceedings.iclr.cc/paper_files/paper/2025/file/12143893d9d37c3569dda800b95cabd9-Paper-Conference.pdf},
volume = {2025},
year = {2025}
}