REVIEW 5 cited by
Computational Limits of Low-Rank Adaptation (LoRA) Fine-Tuning for Transformer Models
Not yet reviewed by Pith; the record is open.
This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.
SPECIMEN: schema-true, not a live event
T0 review · schema-true
One-sentence machine reading of the paper's core claim.
pith:XXXXXXXX · record.json · timestamp
Signed reviews
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^\star}$, and adapter matrices $\alpha 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.
Forward citations
Cited by 5 Pith papers
-
Curse of Attention: A Kernel-Based Perspective for Why Transformers Fail to Generalize on Time Series Forecasting and Beyond
A theoretical analysis claims attention networks fail to learn residual features when time series steps have opposite signs, giving a possible explanation for the known advantage of linear residual models.
-
Fast RoPE Attention: Combining the Polynomial Method and Fast Fourier Transform
A new algorithm computes RoPE attention in n^{1+o(1)} time under bounded entries by decomposing the attention matrix into a small sum of rescaled Toeplitz matrices, then using FFT.
-
Only Large Weights (And Not Skip Connections) Can Prevent the Perils of Rank Collapse
A residual self-attention network with all weight entries bounded by a small η can be approximated by one layer to error O(η)‖X‖∞, so skip connections do not prevent layer collapse.
-
Universal Approximation of Visual Autoregressive Transformers
The paper's headline claim that VAR transformers universally approximate all Lipschitz image maps is not supported, because the theorem restricts the target class and its key lemma has an invalid linearity step.
-
Circuit Complexity Bounds for Visual Autoregressive Model
The authors show that a simplified formalization of the VAR image generation model lies in DLOGTIME-uniform TC0, meaning it can be simulated by constant-depth threshold circuits with polynomial size and precision.
Discussion (0). Continue with ORCID to comment.