Research map / Architectures and efficiency / Pruning and efficient tuning
Computational Limits of Low-Rank Adaptation (LoRA) Fine-Tuning for Transformer Models
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Uses fine-grained complexity (SETH) to show a norm-based sub-quadratic efficiency threshold for LoRA gradient computation on attention heads, and gives almost-linear approximate LoRA gradient algorithms via chained low-rank approximations, with a small OPT speech fine-tuning timing check.
Problem
Whether LoRA fine-tuning of transformer attention heads, whose backward pass is quadratic in sequence length, can be approximated in sub-quadratic or almost-linear time, and under what norm conditions.
Approach
Exploits the low-rank structure of LoRA gradients for attention heads: writes the loss term-by-term via tensor trick and approximates each factor with low-rank decompositions, giving L^{1+o(1)} algorithms under norm bounds, and proves via SETH reduction that subquadratic algorithms need norms below a threshold.
Key results
- Outlier-free transformer trains 5.5% faster for OPT-125M, 13.1% faster for OPT-350M, and 33.3% faster for OPT-1.3B.
- Theory: no O(L^{2-delta}) algorithm for ALoRAGC under SETH unless norms bounded by Gamma = O(sqrt(log L) kappa(L)).
- Theory: L^{1+o(1)} approximate LoRA gradient algorithms exist when norms are o(sqrt(log L)).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| control attention-weight norms using an outlier-free transformer | OPT-125M LoRA fine-tuning · LibriLight speech fine-tuning | training speed: 5.5% faster | Helped |
| control attention-weight norms using an outlier-free transformer | OPT-350M LoRA fine-tuning · LibriLight speech fine-tuning | training speed: 13.1% faster | Helped |
| control attention-weight norms using an outlier-free transformer | OPT-1.3B LoRA fine-tuning · LibriLight speech fine-tuning | training speed: 33.3% faster | Helped |
Limitations
- Identifies necessary, not sufficient, conditions; no direct implementation.
- Experiments are minimal proof-of-concept timing comparisons on speech fine-tuning.
- Analysis restricted to single data point and attention heads with simplifications (beta=1, fixed W_V).
Experimental setup
Datasets: LibriLight
Metrics: training time per epoch relative speedup
Baselines: standard OPT transformer
Builds on: LoRA Alman and Song low-rank attention approximation SETH
Closest papers by meaning
- The Expressive Power of Low-Rank Adaptation (ICLR 2024 · similarity 0.92)
- RandLoRA: Full rank parameter-efficient fine-tuning of large models (ICLR 2025 · similarity 0.91)
- WeGeFT: Weight‑Generative Fine‑Tuning for Multi‑Faceted Efficient Adaptation of Large Models (ICML 2025 · similarity 0.89)
- LoRA-Pro: Are Low-Rank Adapters Properly Optimized? (ICLR 2025 · similarity 0.89)
- Flat-LoRA: Low-Rank Adaptation over a Flat Loss Landscape (ICML 2025 · similarity 0.88)
- Asymmetry in Low-Rank Adapters of Foundation Models (ICML 2024 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.