Computational Limits of Low-Rank Adaptation (LoRA) Fine-Tuning for Transformer Models
Authors: Jerry Yao-Chieh Hu
Maojiang Su
En-jui kuo
Zhao Song
Han Liu
Venue: ICLR 2025 Poster (2025)
Keywords: Parameter Efficient Finetuning
Low-Rank Adaptation
LoRA
Transformer
Foundation Models
Large Language Models
Fine-Grained Complexity
Strong Exponential Time Hypothesis
Primary area: foundation or frontier models, including LLMs
TL;DR: We explore computational hardness of LoRA for transformers, showing a adaptor-weight-norm-based phase transitions in efficiency and the existence of nearly linear algorithms under strong exponential time hypothesis.

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 \blue{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.

Published as a conference paper at ICLR 2025
COMPUTATIONAL LIMITS OF LOW-RANK ADAPTATION (LORA)
FOR TRANSFORMER MODELS"
Jerry Yao-Chieh Hul
Maojiang Su
En-Jui Kuo"
Zhao Song
Han Liu'
Northwestern University University of Science and Technology of China
National Yang Ming Chiao Tung University SSioons Institute, UC Berkeley
jhuěu. wwwuu.nortwweeeeeeeeo www.wwwstern.nnnom edu, sumaojiangemaill wstcc.utc..... edu. on, eioenjui@nycu edu. tw, magic. linuxkde@gmail com, henliu@horthwesterm.co
ABSTRACT
We study the computational limits of Low-Rank Adaptation (LoRA) for fine- tuning transformer-basee 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 al- most linear algorithms by controlling the LoRA update computation term by term. For the former, we identify 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 a B A/rr. Specifically, we derive shared upper bound threshold for such norms, and show that efficient subb-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 practical scenarios: partial (e.g.. only Wv and Wo) and full adaptations (e.g., Wo. Wy, and Wk) ) of weights in attention heads.
INTRODUCTION
We investigate the computational limits of finetuning large hansformer-basee pretrained model with Low-Rank Adaptation (LoRA). This analysis is of practical importance in the era of Large Foundation Models (Bommasani et al., 2021). Large foundation models are gigantic transformer- based architectures, pretrained on vast datasets, are pivotal across multiple fields, including natural language processing (Achiam et al., 2023; Touvron et al., 2023b;a; Brown et al., 2020; Floridi and Chiriatti, 2020), finance (Yang et al., 2023; Wu et al., 2023), genomics (Nguyen et al., 2024; Zhou et al., 2025; 2024; 2023; Ji et al., 2021), medical science (Thirunavukarasu et al., 2023; Singhal et al., 2023; Moor et al., 2023) and more. They are powerful but very expensive to pretrain. Therefore, most practitioners rely on finetuing methods adapt these models for their specific needs (Zheng et al., 2024; Ding et al., 2022). LoRA (Mao et al., 2025; Hu et al., 2021) is the most prevalent fine-tuning method due to its parameter efficiency due to the low-rank adaptation of model weights. However, even with LoRA, updating the partial weights of pretrained transformer- based models using gradient methods remains costly. Notably, the naive backward pass in transformer architectures retains the same quadratic-in-sequee -euueeeeeeeeeee computational time complexity its forward pass (see Appendix for discussions and a proof). This work provides a timely theoretical analysis LoRA's computational limits, aiming advance efficient finetuning of large foundation models.
The hardness of LoRA finetuning transformer-base based foundation model ties to both forward and backward passes. To analyze, it suffices to focus on just transformer attention heads due to their dominating quadratic time complexity in both passes. We first make the following observation:
"Code available OpenReview; full version and future updates are on arXiv.

---

Published as a conference paper at ICLR 2025
The hardness of LoRA's forward pass is trivially characterized by (Alman and Song, 2023).
To this, let X RLxd be input with length I, and WK, Wo, Wy E Raxd be attention weights, The Attention Mechanism is
and Q XWy E R Lxd K XWK Rixd V = XV R gld
= Softmax (QK V e X))
(1.1)
with the inverse temperature 3 > 0 and D == diag (exp(X X 1)). Here, exp(.) is entry-wise exponential function, diag (-) converts a vector into a diagonal matrix with the entries of the vector, and ,, is the length-L all ones vector. LoRA finetuning is given
Definition 1.1 (LoRA (Hu et al., 2021)). Let W E R be any weight matrix a pretrained model F, LoRA fine-tunes F through updating W with low-rank decomposition W = W + BA. Here, W* is the frozen pretrained weight. Only B E gaxrr and A grxa are learnable (being update via gradient descent) with rank r < min (a, b) and tunable hyperparameter a E R.
Under the Strong Exponential Time Hypothesis (Hypothesis 1), Alman and Song (2023) state:
Lemma 1.1 (Informal, (Alman and Song, 2023)). Fast (sub-quadratic) forward pass of transformer only exist when entries of K, Q, V are bounded by a constant B = (v L).
It is easy to see that Lemma 1.1 is transferable LoRA inference according to Definition 1.1. However, we still need the hardness of backward pass to fully characterize LoRA for transformers. The analysis of the backpropagation (backward pass) is less straightforward. involves managing the computation of numerous gradients for attention scores, with the number of chain-rule terms scaling quadratically I. and the numbers of LoRA weights. While is tempting to design algorithms to circumvent this ((L²) computation time, to the best of our knowledge, there are no formal results to support and characterize such algorithms. To address this gap, we pose the following questions and provide fundamental theory to fully characterize the complexity of LoRA for transformer models:
Question 1. Is it possible to improve the S?T.2) time with bounded approximation error?
Question More aggressively, is possible to do such gradient computations in almost linear time?
To address these questions, explore approximate LoRA gradient computations with precision guarantees. We first layout the objective of finetuning transformer-based pretrained models.
Definition 1.2 (LoRA Loss for Adapting WK. Wq. Wy of an Attention Head). Let D = (X,, M be a dataset of size N with X, R2xe being the input and Y; E IR 4xd being the label. Fine-tuning a (self- fattenintt with LoRA with & loss on dataset D is formulated as
<W>- W + at
a BBAKK We W + BBAAQ, Wr - W7 BvAAv
min By BvERtt AveRo.
BR.
1
Σ |D -Y
(1.2)
2N
Here D = diag (exp(XW,wXxxT))) LLL
We study the following approximation problem. Let Z = vec(Z) E Rab for any matrix Z e Raxb
Problem (Approximate LoRA Gradient Computation (ALoRAGC(L, d, e))). Assume all numeri- cal values in log(L) bits encoding. Let follow Definition 1.2. The problem of approximating gradi-
ent computation of optimizing (1.2) is to find six surrogate gradient matrices R
(ā(A) E Bddr (B)
J== @g such that max {{ ( ac
((A)
) E, for some JA
ac
JB
e <> 0, where || = max,, Zzyl-
Remark 1.1. Any method algorithm that aims to compute LoRA gradients beyond vanilla computation of (1.2) falls within the scope of this problem. Examples include using sampling strategies to avoid full LoRA gradient computation (Pan al., 2024) or employing model quantization
2

---

Published as a conference paper at ICLR 2025
for efficiency via low- low-precision gradient computation (Li et al., 2024; Dettmers et al., 2024). Common among these approaches is the need to compute surrogate LoRA gradients with reduced computational cost. We abstract this key subroutine and consider the fundamental algorithmic Problem I.
In this work, we aim to investigate the computational limits of all possible efficient algorithms of ALoRAGC(L, d, c) under realistic setting 1/poly(L).
Contributions. Our contributions are 2-fold:
Norm-Based Phase Transition of Efficiency (Theorem 4.1). We answer Question by identifying phase transition behavior on the norm of input, pretrained and adaptor weights, assuming the Strong Exponential Time Hypothesis (SETH). Specifically, we identify an inefficiency threshold for these norms such that, only below which, adapting transformer-bet based models with LoRA A in 22-o(1) (sub-quadratic) time is possible.
Theorem 1.1 (Informal Version of Theorem 4.1). Without appropriately normalized inputs X, pretrained attention weights : W Wý, and LoRA matrices {a.A, B,,/r,m= K.Q.V there is algorithm running in subquadratic time (LL2-6) for any constant 6 > to solve ALoRAGC.
Existence of Almost Linear Time LoRA Algorithms. We answer Question by proving that precision-guaranteen approximation to Problem is achievable almost linear time via hierarchical low-rank decomposition of LoRA gradients. To showcase our theory, analyze two practical scenarios highlighted in (Hu et al., 2021) ():1): partial adaptations (e.g. only Wy and Wq in Section 3), and full adaptations (e.g., WK. Wo. Wv in Appendix A) of weights in attention heads.
Theorem 1.2 (Informal Version of Theorems 3.1 and A.I), Given appropriately normalized inputs X, pretrained attention weights Wi. W Wy, and LoRA matrices Aa B,/rr) /t//rr//=k u.K.QVV there exists an algorithm that solves ALoRAGC in almost linear time OLL
On the theoretical front, we characterize the computational feasibility of LoRA by showing the existence of rrecision-guaranteed, efficient (subquadratic or almost linear time) LoRA methods and identifying their necessary conditions. On the practical front, these conditions serve as valuable guidelines for implementations (please see Remark 5.2 for discussions and Appendix G for numerical justifications). Importantly, our theory only requires one ussumption on numerical value encoding (e.g., in log L bits with L being the sequence length). Such assumption minimal and realistic. No assumptions are made about the data or model, making our results widely applicable.
Organization. Section 2 includes preliminaries and problem setup. Section 3 presents analysis of LoRA adaptation only Wo, WK. Appendix A presents analysis of LoRA adaptation on all Wo, WK, Wv. Section 4 characterizes computational limits of all possible efficient algorithms for LoRA. Section 5 includes concluding remarks. We defer discussions of related works to Appendix B.
Notations. We denote (column) vectors by lower case letters, and matrices by upper case letters. Let 1 denote the length-L all ones vector. We write (a, b) a b as the inner product for vectors a, Let ali] denotes the i-th component of vector a. Let Ali, j] and Ai denotes the (i, j-th entry of matrix A. For any matrix A, let Afi, and Al. ji be the i-th row and j-th column of A, respectively. For u, 2. E Rd, we denote their Hadamard product as u @ v == (uru1..... U2Va) T The index set {1. ........ . is denoted by [T]. where I N.. For any 2 Rd, denote exp(2) Rd whose i-th entry is exp(z;). Let || All == maxi,j [Aill for any matrix A. Let ||-I|r- denote the squared Frobenius norm, i.c., ||] p == (Ers 1
PRELIMINARIES AND PROBLEM SETUP
This section presents the ideas we build on.
Tensor Trick for Computing Gradients. The tensor trick (Diao et al., 2019; 2018) is instrument to compute complicated gradients in a clean and tractable fashion. As we shall see below, the purpose of the tensor trick is to convert matrix multiplication into vector form, making the gradient w.r.t. the matrix more tractable. For this, we introduce vectorization and its inverse operation, matrixization.
3

---

Published as a conference paper at ICLR 2025
Definition 2.1 (Vectorization). For any matrix X E Rlxdd define X vee (X) RLd such that Xij = ((i-1)d+} for all i E [4] and E [d].
Definition 2.2 (Matrixization). For any vector X RLd, we define mal(X) = such that X1, mat mat(X)) (X) = X (1-1)4+5 for all i [L] and [d], namely mat(.) vec (-).
Next, we introduce necessary tensor terminologies.
Definition 2.3 (Kronecker Product). Let A E RLexd, and B E RLaxd, We define the Kronecker product of A and B as A @ B E IR RaLasdddd such that (A @ (1)i-1)Lattsslll (aan--aaa--idt 1is+ is equal to Aia.ja 5o with ia E [La], Ja E [da], ås E [b E [d&]-
Definition 2.4 Suu--lock of Tensor). For any A E Rlaxd, and B E RLsxd, let A = A c B E R. dd For any j E [Lo], we define A, E Laxadh be the j-th La d.db sub-block of A.
Definition 2.3 creates large matrix from two smaller matrices, preserving the structure and properties of the original matrices, Definition 2.4 provides refined identification of specific entry-wise multiplications between the two Kronecker-Po proneccer-rroducted producted matrices. Together, they makes the gradient w.r.t the matrix more tractable: for instance, the gradient of below vectorized LoRA loss (2.1).
Lemma 2.1 (Tensor Trick (Diao al., 2019; 2018)). For any E R. E R B. Xd, and X E R&dx ",, it holds vec (AXB") = (A & B)X R
To showcase the tensor trick for LoRA, let's consider (single data point) simplified (1.2)
Co = D (XWXX
X
Wy
Y ERExd
P
with W WoWk e Rddd
ERLXL
ERLxZ
ERLxd
dxd
By Definition 2.3 and Definition 2.4, we identify Dj.j = (expl (00(A,A W 11 R for all j e (Z]
with A X R xdd xd and W Rdd Therefore, for each j E [L] and i E [d]. holds
L
d
C
D-11 exp A ex)(A) XWvl: Yjs)
(2.1)
Gao et al. (2023a;b) show that (2.1) provides term-by-tenn tractability for gradient computation of Co- Specifically, it allow us to convert the attention score D- exp (XWXT) into its vectorized form (D @ Ib)= exp(A W) E R and split the vectorized form into L terms of size L. This provides systematic way to manage the chain-rule terms in the gradient computation of losses like Lo, and opens the door more general analytical feasibility for deep transformer-basee models.
Problem Setup: Which Attention Weights in Transformer Should We Apply LoRA to? Following (Hu et al., 2021), we consider only adapting the attention weights for downstream tasks. This consideration is sufficient to justify our techniques as the attention head dominates the time complexity of transformer-basee foundation models. Namely, consider updating (as in Definition 1.2)
We = W + BQ WK = W BK Wr = Wi + r Bv.
Furthermore, for completeness, we consider two de facto scenarios as in (Hu et al., 2021, Sec. 7.1):
(C1) Special Case. Adapting only Wa and Wy for best performance under fixed parameter budge.
(C2) General Case. Adapting K, Wo, Wy for best performance.
We analyze (C1) Special Case in Section and (C2) General Case Appendix
To consider the problem of adapting attention head, we first generalize Definition 1.2 to the following generic attention with triplet input sequences. For reasons, this allows our results to be applicable. Moreover, this helps us to focus on parts dominating the efficiency of gradient computation.
4

---

Published as a conference paper at ICLR 2025
Definition 2.5 (Learning Generic Attention). Let D = {(x! .x!") )x Yihi be dataset of
size N with the triplet x(K), x xx E L being the imput and Y; R being the label. The problem of learning generic attention with & loss from dataset D is formulated as
1
min Wi., Wi, Wo ERdaa
Σ c (WK. Wº, Wv)
N
N
Σ
D D- exp x x (I!(r)) x) Y,
min Wx. Wy. ERuxd
2N
Here D = diag
eep
x
O X
WoWT (x!(k) T
3 8)1m1)
E RLXL
Remark 2.1. Definition 2.5 is generic. If x (K) = x * x! E LRddd Definition 2.5 reduces to cross-attention. If X x!!)
x(V) ggxd Definition 2.5 reduces to self-
SPECIAL CASE: LORA ADAPTATION ON ONLY We AND Wv
Formally, we formulate the partial adaptation (CI) of an attention head as the following LoRA loss.
Definition 3.1
(Adapting Wo. Wy of Generic Attention with LoRA), Let D (x (K) (xx(),x(() x!1) Y.) be dataset of size N with the triplet X (K) x!O) x R
being the input and Y; RLxdd being the label. The problem of fine-tuning We. Wv a generic attention with LoRA with Eg loss from dataset 'D is formulated as
L (W Wº = W + BQ Wy = WV + a BvAA))
min Bq: By gRexe Aq: xd
(3.1)
r
N
D Exp x Wo(W?) (x((0) B x ( Wv -Yi
Bv Aq.AvER"xa
2N
1=1
(IT)
(1)
Here D diag eepp (o(W)) (x(11) 8 {
e RLXL
In this work, we are interested in the efficiency of optimizing (3.1) with gradient descent. For simplicity our analysis, we employ the following four simplifications:
(SI) Since (II) (V multiplication) is linear in weight while (I) (K-Q multiplication) is exponential in weights, we only need focus on the gradient of K-Q multiplication. Therefore, for efficiency analysis of gradient, it is equivalent to analyze reduced problem with fixed Wy.
(S2) To further simplify, we introduce C(2), ((2)) c..3) E gLxd via
(=wa + BoA (WR)T (X(())* = C (c.2)) x!" c(.0) c(3)
eRixd
= =(c(3)) ERAXE
(3.2)
Notably, c c. c(a)) are constants with respect to adapting (3.1) with gradient updates.
(S3) Trivial Reduction. To prove the hardness of Problem 1 for both full gradient descent and stochastic mini-batch gradient descent, it suffices to consider adapting on a single data point.
(S4) We set 3 = 1 without loss of generality, Note that 3 and a/r do not impact the running time of gradient computation since they just rescaling factors.
5

---

Published as a conference paper at ICLR 2025
Thus, deduce Definition 3.1 to
D exp ((2)) ( (W + BoAD) (cte)) 7 (t0) ( Y
min BOER AqeR*xa
AQ)= min
BOERU AQERrx
2
(3.3)
We BoAa) (C(21) ( R where W3 = rW and D diag (exp c(u) (
We introduce the next problem to characterize all possible (efficient or not) gradient computation of optimizing (3.3). Let [i, and V|. j) be the i-th row and j-th column of Y, respectively.
Problem 2 (Approximate LoRA Gradient Computation ALoRAGC(L,,, c( Y, E Rxxxd Let > 0. Assume all numerical values are in log Lb)-itts encoding. Let follows (3.3). The problem of approximating gradient computation of optimizing (3.3) is to find two matrices G(4) E RRd and (()) <R" such that
Given
(B)
dL
(() OC G
max (IÇA
1000
1100) S. AAQ
The explicit gradient of LoRA loss (3.3) is too complicated to characterize Problem 2. To combat this, we employ the tensor trick. Let W W + BQ E gddd such that vee (W) W. gd
Definition 3.2 (Vectorized Attention Score). Let C = (()) @ (()) such that Cj R.xd for all i E [Z.]. For every j E [Z],, we define u w(W),
Red" R. as: u (W), exp C,W, TR.
Definition 3.2 decomposes the complicated matrix exp (CO) (W; + Bq ( in loss (3.3)
into I. vectors. Importantly, since the weight W is vectorized into W, such vectorized representation allows more tractable gradient computation by its term-by-ters identifiability.
Definition 3.3 (Attention Score Normalization). Let C (a)) @ (2(2) such that C2 E Lxx for all j E [Z]. For every E [M], we define a<xx) R24 R as: a (W) = exp C2 1 E R.
Similarly, Definitions 3.2 and 3.3 provide analytical tractability of the matrix in loss (3.3).
Definition 3.4 (Vectorized, Normalized Attention Score). For a fixed j E [L], we define f(W),
Rdd + L as: f(W), = aW)) "(W)) such that f(W) e IR Lx denotes the matrix whose j-th row (T(W)))
Definition
decomposes the complicated D- exp ( (C))) (W3 + (C12)) in loss (3.3) into L terms. Note that the gradi- ents w.r.t. W are still tractable due to simple chain rule (by design of a(-) and u())).
3.4
matrix multiplication
Definition 3.5 (Vectorized LoRA Loss (3.3)), For every E [d], let [()) follow (S2). For every i E [L] and i [d], we define o(x) d x ddd as: c(W) 1.a (f()), (33 [, Yg
Here Y,, Y i] is the (j, i)-th entry of Y E Lxxd for [4], E [d].
From above definitions, we read out c(W) C(W) Y such that (3.3) becomes
1
((W) = C(W)
c(
(3.4)
(3.4) presents a decomposition of the LoRA loss (3.3) into L d terms, each simple enough for tracking gradient computation. Now, are ready to compute the gradient of the LoRA loss.

---

Published as a conference paper at ICLR 2025
Lemma 3.1 (Low-Rank Decomposition of LoRA Gradient). Let matrix BQ: Aq and loss function L. follow (3.3), W = W + Aq and C = C @ C It holds
(1n)
W
7
d
C
diag (S(W),) S S
[[8]
(3.5)
dW
j=
Proof. See Appendix C.I for detailed proof.
Remark 3.1 (Benefit from Tensor Trick: Fast Approximation). As we shall show subsequent sections, Lemma 3.1 also enables the construction of fast approximation algorithms for (3.5) with precision guarantees due to its analytical feasibility. Surprisingly, it is even possible to compute (3.5) in almost linear time. To proceed, we further decompose (3.5) into its fundamental building blocks according to the chain-rule in the next lemma, and then conduct the approximation term-by-trmm.
Remark 3.2 (LoRA Gradient Computation Takes Quadratic Time). Lemma 3.1 implies that LoRA's gradient computation takes quadratic time, similar to inference hardness result (Alman and Song, 2023). This is non-trivial yet not the main focus of this work. Please Appendix F for details.
Lemma 3.2 (Vectorized
BC BC ). Let q(W) = (19) (c(W)) E RLLL For every index j E [4] DAO'
we define p(W] E RL as p(W) = (diag (IWW)) - [W,, / (WW)) ((W). Then holds
OC 0Aq
= vec Be (c()) p(W))()
Oc
vec ((ow)) p(W) ((W))
(3.6)
Proof. See Appendix C.2 for detailed proof.
Lemma 3.2 states that the chain rule terms for characterizing Problem 2 are tied to p(-). Therefore, to characterize G(A), G(B) (i.e., the approximations of G(A), G(1)), we need to approximate the functions f(-). q()), c(+), and hence p(.) with precision guarantees. To do so, convenient to consider the following decomposition of p(-).
Definition 3.6 (Decomposition of p(-)). For every j E [L], we define p1 (W) Pe(W), E R as
Pi (W) diag (5 (W), ((W), and P2(W), = (W), f (W), (W))
such that p(W) Pi (W) (2W).
Overview of Our Proof Strategy. Definition 3.6 motivates the following strategy: term-by-term approximation for
almost linear time algorithms to compute (3.6) (Problem 2).
Step 1. Prove the existence of almost linear approximation algorithms for f()), g(),)(()))))) via low-rank approximation: Lemma 3.3, Lemma 3.5 and Lemma 3.4.
Step 2. Prove the existence of almost linear approximation algorithms for p (2). and hence p(.) via the low-rank- preseeving property of the multiplication between f(.) and g(-): Lemma 3.6 and Lemma 3.7.
Step 3. Prove existence of almost linear approximation algorithms for the LoRA adapter gradients and 8C in (3.6)) with results from Step & 2: Theorem 3.1.
(i.e., BAg
BBQ
Step We start with low-rank approximations for f(-, c()),
Lemma 3.3 (Approximate f(-), Modified from (Alman and Song, 2023)), Let = olvlog and k ()(1, Let C()), ((2) e Lxd, W gaxd and f(W) D-1 exp (COW (C(2)) with D = diag (exp (CW) (C(2)) 1) 1r,) follows Definitions 3.2 to 3.5. max moax(l|c// (I(C()) S
7

---

Published as a conference paper at ICLR 2025
I.||c(211 - I, then there exist matrices U1, V1 E L2 such that [ f(W)l S e/poly(J) (L) In addition, takes L (+{( time to construct U1 and V1.
Proof. This lemma is an application of (Alman and Song, 2023, Theorem 3.8).
Lemma 3.4 (Approximate c(-)). Assume all numerical values are in (log L) bits. Let d = ( L) and (W) e Rxddd follows Definition 3.5. There exist two matrices U1, V1 IR Lxkk such that
|uiv c
ct W
S <e/polyLL).
Proof. See Appendix C.3 for detailed proof.
Lemma 3.5 (Approximate q())). Let k2 L)(1) c(W) Rxd follows Definition 3.5 and let
(WW = C(3) (c(W)) E R follows Lemma 3.2. There exist two matrices U2, V22 E Lxck such that [ - (W) S e/poly(L). In addition, it takes 1,1+0(1) time to construct U2, V/2
Proof. See Appendix C.4 for detailed proof.
Step 2. Now, we use above lemmas to construct low-rank approximations for pı(-), (())))).
Lemma 3.6 (Approximate pi (-)). Let kn, k2 k3 T,O(1), Suppose U1, V1 E L approximates
f(W) E _2 such that |U1V] f(W) 2o I </poly(LL) and U2, V22 Lx approximates
the (W) RLXL such that 1 -g(WW (W) S e/poly(I.). Then there exist two matrices
U3, V/3 E 1x such that
UUVV (w) S e/poly(L).
In addition, it takes L [+))) time to construct U3, V3.
Proof Sketch. By tensor formulation, we construct Ug. V/3 as tensor products of U1, Vi and U2, V22 respectively, while preserving their low-rank structure. Then, we show the low-rank approximation of (i()) with bounded error by Lemma 3.3 and Lemma 3.5. See Appendix C.5 for detailed proof. O
Lemma 3.7 (Approximate P2(.)). Let K1, k2, [o[)) Let (W) E RLLL follow Definition 3.6 such that its j-th column is p2 = f(W),f(W) [ (W), for each j [L]. Suppose U1, Vi
RLxk: approximates the ((X) such that [U - S(W) I e/poly(L), and U2, V/2 BL
approximates the g(W) L such that |U2V - g(W) llae I e/poly(L). Then there exist matrices U4, V4 E 4xka such that
|UVV P2(W) S c/poly(LL)
In addition, it takes L [+0(()) time to construct U4, Va.
Proof Sketch. By considering the following decomposition through tensor formulation
(1)
p2(W) = (W), f (W)) (W),
we approximate the Pz(-) part by part. Specifically, for (I), we show its low-rank approximation property of the multiplication between f(-) and q(-) (from Lemma 3.3 and Lemma 3.5). For (II), we show its low-rank approximation by the low-rank structure of f()) and (I). See Appendix C.6 for detailed proof.
by observing the low-rank-preserv
8

---

Published as a conference paper at ICLR 2025
Step 3. Combining above, we arrive our main result: almost linear algorithm for Problem 2.
Theorem 3.1 (Main Result: Existence of Almost Linear Time ALoRAGC), Suppose all numer- ical values are in O(log L)-bits encoding. Recall that W = W + Bq E Raxd with Wo = rWa/as a. Let Ca) x(0) g, C(2) W follows (3.2). If ||C S T and |
0 1 r, where r = o( oog L). then there exists a L I++(() time algorithm to solve ALoRAGC (L, d O(log r) Io(1) 1/poly(L)) (i.e., Problem 2). In particular, this algo-
rithm outputs gradient matrices G(A) E Rdxr, G(B) R such that
ac 0AQ
2 1100 s 1/poly(L), and 0BQ
dc (B))
CQ
1lo0 S 1/poly(L).
Prooffketch Sketch. By Lemma 3.2, we have 0c/8A, = () (PW))C(2) and 0c/aBa = vec((C(())] ((CCC))T(((W))).) ((W))AC(1)) By Lemma 3.2 and Definition 3.6, we have p(W) Pi(W P2()). Firstly, we notice that the exact computation of (C(()) and AQC(2) takes only 1,1+0(1) time, by Aq E Rexdd BQ E Rdxr, C(), C E Rexd, Thus, to show the ex- istence of [)+o(1) time algorithms for Problem 2, we prove fast low-rank approximations for ( (W)CC) and (C(D) (P (Q)A) by Lemma 3.6. The fast low-rank approxima- tions for -B3 (B2())) and -CC()) (Cx())CTpT()WWeeeeee AQ follow trivially. See Appendix C.7 for a detailed proof.
General Case: Full LoRA Adaptation on WK. Wo, Wv. We defer the analysis of full LoRA on transformer ((C2) General Case: adapting both WK. Wo, Wv) to Appendix A due page limit. Importantly, we also prove the existence of an almost linear-time LoRA (Theorem A. In addition, we derive the norm bound conditions required for it to hold.
4 NORM-BASED PHASE TRANSITION IN EFFICIENCY
In this section, we characterize the computational limits of all possible efficient algorithms of ALoRAGC, via fine-grained reduction under the Strong Exponential Time Hypothesis (SETH).
Strong Exponential Time Hypothesis (SETH), Impagliazzo and Paturi (2001) introduce the Strong Exponential Time Hypothesis (SETH) as a stronger form of the o NP conjecture. It suggests that our current best SAT algorithms are optimal and is popular conjecture for proving fine-graines lower bounds for a wide variety of algorithmic problems (Williams, 201 8b; 2013; Cygan al., 2016).
Hypothesis 1 (SETH), For every e > 0, there is a positive integer l: 2 3 such that k-SAT on formulas with n variables cannot be solved ((2(1-e)n) time, even by a randomized algorithm.
Our primary technique involves casting the ALoRAGC problem (Problem 1) as a fine-grained reduc- tion under SETH, from the hardness result of fast attention approximation algorithm (Alman and Song, 2023). For simplicity of analysis, we consider the special case (CI).
Theorem 4.1 (Inefficient Threshold). Let k N + N by any function with <(I.) = w1)) and x(L) olog L). Let (Vlog L x (L)). Assuming Hypothesis I, there is no algorithm running in time (L22-)) for any constant å > for ALORAGC(L, d = O(log L), < d, i.c., Problem 2,
subject to (3.3), even in the case where the input and weight matrices satisfy [ W S T. [|axx() Aq/ ST, and = O(log -4).
Proof Sketch. Firstly, we recall the hardness of sub-quadratic Attention Gradient Computation approximation, i.e., At from (Alman and Song, 2024a) (defined in Definition E. This serves as a reference point for the complexity we anticipate for ALORAGC defined in Problem 2. We then proceed with reduction from problem AttLGC to problem ALORAGC. Essentially, by showing that AttLGC at least as hard as ALoRAGC, and then showing how to solve At using a solution to ALoRAGC, establish the hardness of ALORAGC. See for Appendix E for detailed proof. [T

---

Published as a conference paper at ICLR 2025
Remark 4.1. Theorem 4.1 suggests an efficiency threshold for r. Only below this threshold are efficient algorithms for ALoRAGC possible. This is r'based phase transition behavior in efficiency.
Remark 4.2. In Theorem 4.1, show that even the simplest single-data-pon case with Y 0 is hard. Hence, our result also applies to the special case (C1) (i.c., Problem 2) and general case (C2) (i.e., Problem 3). Specifically, it is evident that computing the gradient for multiple data points (whether the full gradient or stochastic mini-batch gradient) is at least as hard as for a single data point. The hardness follows trivially.
DISCUSSION AND CONCLUDING REMARKS
We study the computational limits of the Low-Rank Adaptation (LoRA) for transformer- based model finetuning using fine- fine-grained complexity theory (i.e., under Hypothesis 1). Our main contribution is the proof of the existence of almost linear approximation algorithms for LoRA adaptation on transformer-bascl models. We accomplish this by utilizing the hierarchical low-rank structures of LoRA gradients (Lemmas 3.3 to 3.5) and approximating the gradients with a series of chained low-rank approximations (Lemmas 3.6 and 3.7). To showcase our theory, we establish such almost linear approximation for both partial (Theorem 3.1) and full LoRA adaptions (Theorem A. of attention weights. In addition, identify phase transition behavior in the efficiency of all possible variants of LoRA (Theorem 4. by adjusting the norm upper-bound T of input, pretrained, and adaptor weights. Specifically, we establish an "inefficiency threshold" for I, only below which adapting wansformer-basee models with LoRA in 2 (sub-quadratic) time is possible.
Remark 5.1 (General Case: Full LoRA Adaptation on WK. Wo. Wv). We defer the analysis of full LoRA on transformer (adapting both WK, Wo, Wr matrices) Appendix A due to page limit.
Necessary Conditions for Efficient and Robust LoRA). This work is about LoRA transformer models. Therefore, the computational bottleneck is by design O(L²) (see Appendix F for discussions and a proof.) In this regard, our work provides in-depth analysis to address this (L)) bottleneck and provides useful insights and guidance for designing efficient LoRA algorithms and methods with precision guarantees:
Remark 5.2 (Insights for Practitionars:
Theorem 4.1: Necessary Conditions for Subqudratic Time LoRA. Proper normalization of the composed norms, e.g., | S T and ||ax (2) BQAq/rlI S T with r O(VlogL.x(LL))
Theorems 3.1 and A.1: Necessary Conditions for Almost Linear Time LoRA. Proper normal- ization of the composed norms, c.g.,
For partial LoRA on Wo. Wy (Theorem 3.1): ||xx(9) S I and [ 1100 S I
with r = o( loo L).
For full LoRA WK. Wq, Wv (Theorem A.1): [x(2) (W + Aq Wx 1: S r, ||xx((||| r, 1 < I, and (xxx()) (W3 + +x < I' with I' = o(vlog L).
Suitable normalization of the composed norms can be implemented using pre-activation layer normal- ization (Xiong et al., 2020; Wang et al., 2019) to control ||] or outleer-rmooing attention activation functions (Hu et al., 2024a) to control [ A II. || Il
On one hand, our findings provide formal justifications for these methods. On the other hand, these necessary conditions also motivate the design of future efficient methods with minimal model and data assumptions.
Remark 5.3 (Self- and Cross-Attention). We emphasize that all these results hold for not only self- attention but also cross-attention due generic problem setting (Definition 2.5 and Remark 2.1).
Proof-of-Concept Experiments. We provide numerical results to justify our theory in Appendix G.
Limitations. We identify necessary conditions for fast LoRA methods, not sufficient conditions. Therefore, our results do not lead to direct implementations. This limitation is inherent to hardness results (Toolkit, 2013). However, discussed above, we expect our findings provide valuable insights for future efficient LoRA implementations in both forward and backward computations.
Impact Statement. This theoretical work aims elucidate the foundations of large transformer-bast foundation models and is not expected to have negative social impacts.
Related Works We defer the discussion of related works to Appendix B due page limit.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTIS
JH thanks Mimi Gallagher, Sara Sanchez, Dino Feng, and Andrew Chen for enlightening discussions; Yen-Ju Lu, Shang Wu, Robin Luo, and Jiahao Yu for collaborations on related topics; Shang Wu and authors of (Wu et al., 2024c) for assistance with numerical experiments; and the Red Maple Family for their support. The authors also thank the anonymous reviewers and program chairs for their constructive comments.
JH is partially supported by the Walter P. Murphy Fellowship. HI is partially supported by NIH R01LMM332201, AbbVie and Dolby. EJK thanks the National Center for Theoretical Sciences of Taiwan for funding
This research was supported in part through the computational resources and staff contributions provided for the Quest high performance computing facility at Northwestern University which is jointy supported by the Office of the Provost, the Office for Research, and Northwestern University Information Technology. The content is solely the responsibility of the authors and does not necessarily represent the official views of the funding agencies.
REFERENCES
Amir Abboud, Virginia Vassilevska Williams, and Oren Weimann. Consequences of faster alignment of sequences. In Automata, Languages, and Programming: 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I 41, pages 39-51. Springer, 2014.
Amir Abboud, Arturs Backurs, Thomas Ducholm Hansen, Virginia Vassilevska Williams, and Or Zamir. Subtree isomorphism revisited. ACM Transactions on Algorithms (TALG)), 14(3):1233, 2018.
Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, llge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et Gpt-4 technical report. arXiv preprint 20:::2333087774 2023.
Amol Aggarwal and Josh Alman Optimal-degue polynomial approximations for exponentials and gaussian kernel density estimation. In Proceedings of the 37th Computational Complexity Conference, CCC '22 Dagstuhl, DEU, 2022. Schloss Dagstubl-LeibbiizZZenrrrm fuer Informatik. ISBN 9783959772419. doi: 11442300.IIcss.cc..22222
Josh Alman and Zhao Song. Fast attention requires bounded entries. In Thirty-seventh Conference on Neural Information Processing Systems (NeurIPS), 2023.
Josh Alman and Zhao Song. The fine-grained complexity of gradient computation for training large language models. arXiv preprint arXiv:2402.044477, 2024a.
Josh Alman and Zhao Song. How to capture higher-order correlations? generalizing matrix softmax attention to kronecker computation. In ICLR. arXiv preprint arXiv:2310.04064, 2024b.
Josh Alman and Hantao Yu. Fundamental limitations subquadratic alternatives transformers. arXiv preprint arXiv:2410.04271 2024.
Josh Alman, Timothy Chu, Aaron Schild, and Zhao Song. Algorithms and hardness for linear algebra on geometric graphs. In 2020 IEEE 61 Annual Symposium on Foundations of Computer Science (FOCS), pages 541-552. IEEE, 2020.
Arturs Backurs and Piotr Indyk. Which regular expression patterns are hard match? In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 457-466. IEEE, 2016.
Arturs Backurs, Piotr Indyk, and Ludwig Schmidt. On the fine-grained complexity of empirical risk minimization: Kernel methods and neural networks. Advances in Neural Information Processing Systems, 30, 2017.
Rishi Bommasani, Drew A Hudson, Ehsan Adeli, Russ Altman, Simran Arora, Sydney Arx, Michael S Bernstein, Jeannette Bohg, Antoine Bosselut, Emma Brunskill, et al. On the opportuni- ties and risks of foundation models. arXiv preprint 108.::2208.07000 2021.
11

---

Published as a conference paper at ICLR 2025
Yelysei Bondarenko, Markus Nagel, and Tijmen Blankevoort. Quantizable transformers: Removing outliers by helping attention heads do nothing, Advances in Neural Information Processing Systems (NeurIPS), 36, 2023.
Karl Bringman and Marvin Künnemann, Multivariate fine-grate ine-grained complexity of longest common subsequence. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium Discrete Algorithms, pages 1216-1235. SIAM, 2018.
Karl Bringmann. Why walking the dog takes time: Frechet distance has no strongly subquadratic algorithms unless seth fails. In 2014 IEEE 55th Annual Symposium on Foundations Computer Science, pages 661-670. IEEE, 2014.
Karl Bringmann and Wolfgang Mulzer. Approximability of the discrete fréchet distance. Journal of Computational Geometry, (()):46776, 2016.
Karl Bringmann, Allan Grønlund, and Kasper Green Larsen. A dichotomy for regular expression membership testing. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS), pages 307-318. IEEE, 2017.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 33: 33:1877-1901, 2020.
Kevin Buchin, Maike Buchin, Maximilian Konzack, Wolfgang Mulzer, and André Schulz. Fine- grained analysis of problems on curves. EuroCG, Lugano, Switzerland, 3, 2016.
Chris Calabro, Russell Impagliazzo, and Ramamohan Paturi. The complexity of unique k-sat: An isolation lemma for k-cnfs. In International Workshop on Parameterized and Exact Computation, pages 47-56, Springer, 2009.
Timothy M Chan, Virginia Vassilevska Williams, and Yinzhan Xu. Hardness for triangle problems under more believable hypotheses: reductions from real apsp, real 3sum, and ov. In Proceed- ings of the 54th Anmual ACM SIGACT Symposium on Theory of Computing, pages 1501-1514, 2022.
Lijie Chen. On the hardness of approximate and exact (bichromatic) maximum inner product. In Proceedings of the 33rd Computational Complexity Conference, pages 1-45, 2018.
Lijie Chen and Ryan Williams. An equivalence class for orthogonal vectors. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 21-40. SIAM, 2019.
Marek Cygan, Holger Dell, Daniel Lokshtanov, Dániel Marx, Jesper Nederlof, Yoshio Okamoto, Ramamohan Paturi, Saket Saurabh, and Magnus Wahlström. On problems as hard as enf-sat. ACM Transactions Algorithms (TALG), 12(3):1-24, 2016.
Mina Dalirrooyfard, Ray Li, and Virginia Vassilevska Williams. Hardness of approximate diameter: Now for undirected graphs. In 202/ IEEE 62nd Anmual Symposium on Foundations of Computer Science (FOCS), pages 1021-1032. IEEE, 2022.
Tim Dettmers, Artidoro Pagnoni, Ari Holtzman, and Luke Zettlemoyer. Qlora: Efficient finetuning of quantized llms. Advances in Neural Information Processing Systems, 36, 2024.
Huaian Diao, Zhao Song, Wen Sun, and David Woodruff. Sketching for kronecker product regression and p-splines. In International Conference on Artificial Intelligence and Statistics, pages 1299- 1308. PMLR, 2018
Huaian Diao, Rajesh Jayaram, Zhao Song, Wen Sun, and David Woodruff. Optimal sketching for kronecker product regression and low rank approximation. Advances in neural information processing systems, 32, 2019.
Ning Ding, Yujia Qin, Guang Yang, Fuchao Wei, Zonghan Yang, Yusheng Su, Shengding Hu, Yulin Chen, Chi-Min Chan, Weize Chen, et al. Delta tuning: A comprehensive study of parameter efficient methods for pre-trained language models. arXiv preprint arXiv:2203.069M 2022.
12

---

Published as a conference paper at ICLR 2025
Ning Ding, Xingtai Lv, Qiaosen Wang. Yulin Chen, Bowen Zhou, Zhiyuan Liu, and Maosong Sun. Sparse low-rank, adaptation pre-trained language models. In The 2023 Conference on Empirical Methods in Natural Language Processing, 2023.
Luciano Floridi and Massimo Chiriatti. Gpt-3: Its nature, scope, limits, and consequences. Minds and Machines, 30:681-600 2020.
Jiawei Gao, Russell Impagliazzo, Antonina Kolokolova, and Ryan Williams. Completeness for first-order properties sparse structures with algorithmic applications. ACM Transactions on Algorithms (TALGG), 15(2):1-35, 2018.
Yeqi Gao, Zhao Song, Weixin Wang, and Junze Yin. A fast optimization view: Reformulating single layer attention Ilm based on tensor and svm trick, and solving it in matrix multiplication time. arXiv preprint arXh::3309.074:: 2023a.
Yeqi Gao, Zhao Song, and Shenghao Xie. In-context learning for attention scheme: from single soft- max regression to multiple softmax regression via tensor trick. arXiv preprint arXiv:2307.0244 02419, 2023b.
Jiuxiang Gu, Yingyu Liang, Heshan Liu, Zhenmei Shi, Zhao Song, and Junze Yin. Conv-basis: new paradigm for efficient attention inference and gradient computation in transformers. arXiv preprint arXiv:2405.0520 05519,, 2024a.
Jiuxiang Gu, Yingyu Liang, Zhenmei Shi, Zhao Song, and Yufa Zhou. Tensor attention training: Provably efficient learning of higher-order transformers. arXiv preprint arXiv:2405. 16411, 2024b.
Han Guo, Philip Greengard, Eric Xing, and Yoon Kim. LQ-IoRA: Low-rank plus quantized matrix decomposition for efficient language model finetuning. The Twelfth International Conference on Learning Representations, 2024.
Soufiane Hayou, Nikhil Ghosh, and Bin Yu. Lora+: Efficient low rank adaptation of large models. arXiv preprint ar0i::2402. 2024.
Edward J Hu, Yelong Shen, Phillip Wallis, Zeyuan Allen Yuanzhi Li, Shean Wang. Lu Wang, and Weizhu Chen. Lora: Low-rank adaptation of large language models. arXiv preprint arXiv:2/06.09688 09685, 2021.
Jerry Yao-Chieh Hu, Donglin Yang, Dennis Wu, Chenwei Xu, Bo-Yu Chen, and Han Liu, On sparse modern hopfield model. In Thirty-seventh Conference on Neural Information Processing Systems (NeurIPS), 2023.
Jerry Yao-Chieh Hu, Pei-Hsuan Chang, Robin Luo, Hong- Yu Chen, Weijian Li, Wei-Po Wang, and Han Liu. Outlier-efficient hopfield layers for large transformer-based models. In Forty-first International Conference on Machine Learning (ICML), 2024a.
Jerry Yao-Chieh Hu, Bo-Yu Chen, Dennis Wu, Feng Ruan, and Han Liu. Nonparametric modern hopfield models. arXiv preprint vrXiv:2404.03900 2024b.
Jerry Yao-Chieh Hu, Thomas Lin, Zhao Song, and Han Liu. On computational limits of modern hopfield models: fine-grained complexity analysis. Forty-first International Conference on Machine Learning (ICML), 2024c.
Jerry Yao-Chieh Hu, Dennis Wu, and Han Liu. Provably optimal memory capacity for modern hopfield models: Transformer Transformer-compatbble dense associative memories spherical codes. Advances in Neural Information Processing Systems, 37:70693-70729, 2025.
Chengsong Huang, Qian Liu, Bill Yuchen Lin. Tianyu Pang. Chao Du, and Min Lin. Lorahub: Efficient cross-task generalization via dynamic lora composition. arXiv preprint oxXiv:207.13266 2023.
Russell Impagliazzo and Ramamohan Paturi. On the complexity of k-sat. Journal of Computer and System Sciences, 62(2):367-375, 2001.
13

---

Published as a conference paper at ICLR 2025
Yanrong Ji, Zhihan Zhou, Han Liu, and Ramana V Davuluri. Dnabert: pre-trained bidirectional encoder representations from transformers model for ina-language in genome. Bioinformatics, 37 (15):2112-2120) 2021.
Jacob Kahn, Morgane Riviere, Weiyi Zheng, Evgeny Kharitonov, Qiantong Xu, Serre-Emmnuell Mazaré, Julien Karadayi, Vitaliy Liptchinsky, Ronan Collobert, Christian Fuegen. al. Ligri-light: A benchmark for asr with limited or supervision. In ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 7669-7673. IEEE, 2020.
CS Karthik and Pasin Manurangsi. On closest pair in euclidean metric: Monochromatic is as hard as bichromatic. Combinatorica, 40(4):539-573, 2020.
Robert Krauthgamer and Ohad Trabelsi. Conditional lower bounds for all-pairs max-flow. ACM Transactions on Algorithms (TALG), 14(4):1-15, 2018.
Yinghui Li, Jing Yang. and Jiliang Wang. Dylora: Towards energy efficient dynamic lora transmission control. In IEEE INFOCOM 2020-IEEE Conference Computer Communications, pages 2312- 2320. IEEE, 2020.
Yixiao Li, Yifan Yu, Chen Liang, Nikos Karampatziakis, Pengcheng He, Weizhu Chen, and Tuo Zhao. Loftq: SoRA-fiie-tuning-awar quantization for large language models. In The Twelfth International Conference on Learning Representations, 2024.
Shih-Yang Liu, Chien-Yr Yi Wang, Hongxu Yin, Pavlo Molchanov, Yu-Chiang Frank Wang, Kwang- Ting Cheng, and Min-Hung Chen. Dora: Weight-decomposed low-rank adaptation. arXiv preprint arXiv:2402.09353, 2024.
Soumi Maiti, Yifan Peng. Shukjae Choi, Jee-weon Jung, Xuankai Chang, and Shinji Watanabe. Voxtlm: Unified decoder-only models for consolidating speech recognition, synthesis and speech, text continuation tasks. In ICASSP 2024-2024 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 122300. IEEE, 2024.
Yuren Mao, Yuhang Ge, Yijiang Fan, Wenyi Xu, Yu Mi, Zhonghao Hu, and Yunjun Gao. A survey on lora of large language models. Frontiers of Computer Science, 19(7):197605, 2025.
Michael Moor, Oishi Banerjee, Zahra Shakeri Hossein Abad, Harlan M Krumholz, Jure Leskovec, Eric J Topol, and Pranav Rajpurkar. Foundation models for generalist medical artificial intelligence. Nature, 616(7956):55--265 2023.
Eric Nguyen, Michael Poli, Marjan Faizi, Armin Thomas, Michael Wornow, Callum Birch-Sykes, Stefano Massaroli, Aman Patel, Clayton Rabideau, Yoshua Bengio, et Hyenadna: Long-range genomic sequence modeling at single nucleotide resolution. Advances in neural information processing systems, 36, 2024.
Rui Pan, Xiang Liu, Shizhe Diao, Renjie Pi, Jipeng Zhang, Chi Han, and Tong Zhang. Lisa: Layerwise importance sampling for memory-efficient large language model fine-tuning, arXiv preprint arXiv:2403.17911 2024.
Liam Roditty and Virginia Vassilevska Williams. Fast approximation algorithms for the diameter and radius of sparse graphs. Proceedings of the forty-fifth annual ACM symposium on Theory of computing, pages 515-524, 2013.
Aviad Rubinstein. Hardness of approximate nearest neighbor search. In Proceedings of the 50th annual ACM SIGACT symposium on theory of computing (STOC), pages 1260-1268. 2018.
Karan Singhal, Shekoofeh Azizi, Tao Tu, S Sara Mahdavi, Jason Wei, Hyung Won Chung, Nathan Scales, Ajay Tanwani, Heather Cole-Lewis, Stephen Pfohl, et Large language models encode clinical knowledge. Nature, 620-7972) 2023.
Mingjic Sun, Xinlei Chen, J Zico Kolter, and Zhuang Liu. Massive activations in large language models. arXiv preprint arXiv:2402. 17762, 2024.
14

---

Published as a conference paper at ICLR 2025
Arun James Thirunavukarasu, Darren Shu Jeng Ting, Kabilan Elangovan, Laura Gutierrez, Ting Fang Tan, and Daniel Shu Wei Ting. Large language models in medicine. Nature medicine, 29(8): 1930-1940, 2023.
A Theorist's Toolkit. Lecture 24: Hardness assumptions. 2013.
Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al. Llama: Open and efficient foundation language models. arXiv preprint wrXiv:2302.13977 2023a.
Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaci, Nikolay Bashlykov, Soumya Batra, Prajiwal Bhargava, Shruti Bhosale, et al. Llama 2: Open foundation and fine-tuned chat models. arXiv preprint w:Xiv:2307.09288, 2023b.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017.
Qiang Wang, Bei Li, Tong Xiao, Jingbo Zhu, Changliang Li, Derek Wong, and Lidia $ Chao. Learning deep transformer models for machine translation. arXiv preprini 2019.
Ryan Williams. Finding paths of length k in o (2%) time. Information Processing Letters, 109(6): 315-318, 2013.
Ryan Williams. On the difference between closest, furthest, and orthogonal pairs: Nearly-linear vs barely-subquaaraatic complexity. In Proceedings of the Twenty-inth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1207-1215. SIAM, 2018a.
Virginia Vassilevska Williams. On some fine-grained questions in algorithms and complexity. In Proceedings of the international congress of mathematicians: Rio de janeiro 2018, pages 3447- 3487. World Scientific, 2018b.
Dennis Wu, Jerry Yao-Chich Hu, Teng- Yun Hsiao, and Han Liu. Uniform memory retrieval with larger capacity for modern hopfield models. In Forty-first International Conference Machine Learning (ICMI.), 2024a.
Dennis Wu, Jerry Yao-Chieh Hu, Weijian Li, Bo- Yu Chen, and Han Liu, STanhop: Sparse tan- dem hopfield model for memory-enhanced time series prediction. In The Twelfth International Conference on Learning Representations (ICLR), 2024b.
Shang Wu, Yen-Ju Lu, Haozheng Luo, Jerry Yao-Chieh Hu, Jiayi Wang, Najim Dehak, Jesus Villalba, and Han Liu. Fast adaptation and robust quantization of multi-modal foundation models from associative memory: A case study in speechlm. In Workshop on Efficient Systems for Foundation Models @@@ ICM1.2024, 2024c.
Shijie Wu, Ozan Irsoy, Steven Lu, Vadim Dabravolski, Mark Dredze, Sebastian Gehrmann, Prabhan- jan Kambadur, David Rosenberg, and Gideon Mann. Bloomberggpt: A large language model for finance. arXiv preprint arXiv:2303. 17564, 2023.
Ruibin Xiong, Yunchang Yang, Di He, Kai Zheng, Shuxin Zheng, Chen Xing, Huishuai Zhang, Yanyan Lan, Liwei Wang, and Tieyan Liu. On layer normalization in the transformer architecture. In International Conference on Machine Learning, pages
PMLR, 2020.
Chenwei Xu, Yu-Chao Huang, Jerry Yao-Chieh Hu, Weijian Li, Ammar Gilani, Hsi-Sheng Goan, and Han Liu. Bishop: Bi-directional cellular learning for tabular data with generalized sparse modern hopfield model. In Forty-first International Conference on Machine Learning (ICML), 2024a.
Yuhui Xu, Lingxi Xic, Xiaotao Gu, Xin Chen, Heng Chang, Hengheng Zhang, Zhengsu Chen, XIAOPENG ZHANG, and Qi Tian. QA-loRA: Quantization-awaaee low-rank adaptation of large language models. In The Twelfth International Conference on Learning Representations, 2024b.
Hongyang Yang, Xiao-Yang Liu, and Christina Dan Wang. Fingpt: Open-source financial large language models. arXiv preprint arXiv:2306.0603// 2023.
15

---

Published as a conference paper at ICLR 2025
Yuchen Zeng and Kangwook Lee. The expressive power of low-rank adaptation. In The Twelfth International Conference on Learning Representations. 2024.
Qingru Zhang, Minshuo Chen, Alexander Bukharin, Pengcheng He, Yu Cheng, Weizhu Chen, and Tuo Zhao. Adaptive budget allocation for parameter-efficien fine-tuning. In The Eleventh International Conference on Learning Representations, 2023.
Susan Zhang, Stephen Roller, Naman Goyal, Mikel Artetxe, Moya Chen, Shuohui Chen, Christopher Dewan, Mona Diab, Xian Li, Xi Victoria Lin, et al. Opt: Open pre-trained transformer language models. arXiv preprint arXiv:2205.0006 000000, 2022.
Yaowei Zheng, Richong Zhang, Junhao Zhang, Yanhan Ye, and Zheyan Luo. Llamafactory: Unified efficient fine-tuning of 100+ language models. arXiv preprint arXiv:2403.13372, 2024.
Zhihan Zhou, Yanrong Ji, Weijian Li, Pratik Dutta, Ramana Davuluri, and Han Liu. Dnabert-2: Effi- cient foundation model and benchmark for multi-species genome. arXiv preprint XIv::23066.1000 2023.
Zhihan Zhou, Winmin Wu, Harrison Ho, Jiayi Wang, Lizhen Shi, Ramana V Davuluri, Zhong Wang, and Han Liu. Dnabert-s: Learning species-aware dna embedding with genome foundation models. arXiv preprint 4rX1v:2402.08877, 2024.
Zhihan Zhou, Robert Riley, Satria Kautsar, Weimin Wu, Rob Egan, Steven Hofmeyr, Shira Goldhaber- Gordon, Mutian Yu, Harrison Ho, Fengchen Liu, et al. Genomeocean: An efficient genome foundation model trained large-scale metagenomic assemblies. bioRxiv, pages 2025-01, 2025.
16

---

Published as a conference paper at ICLR 2025
Appendix
A General Case: Full LoRA Adaptation on WK, Wq and Wy
18
Related Works
20
Proofs of Section 3
22
C.I Proof of Lemma 3.1
22
C.2 Proof of Lemma 3.2
C.3 Proof of Lemma 3,4
................................
24
C,4 Proof of Lemma 3,5
24
C.S Proof of Lemma 3.6
25
................................
C.6 Proof of Lemma 3.7
26
C.7 Proof of Theorem 3.1
27
D Proof of Theorem A.1
29
Proof of Theorem 4.1
37
Quadratic Time Complexity of Exact LoRA Gradient Computation
38
Proof-of-Concepe Experiments
40
17

---

Published as a conference paper at ICLR 2025
A GENERAL CASE: FULL LORA ADAPTATION ON WK, Wo AND Wy
Similarly, we formulate the full adaptation (C2) of an attention head as the following LoRA loss.
Definition A.1 (Adapting WK. Wq, Wv of Generic Attention with LoRA), Let D = _ be dataset of size N with the triplet x(k), X; x,() ,x!' 1g
{(x{*), X; x x;") Y.)
being the input and Y; E R fxd being the label. The problem of fine-tuning generic attention with LoRA with & loss from dataset D is formulated as
min Bx. Bg. ByeR Ak Av
L(WK- W + BKAK, We -W + =BBAQ. Wy =Wi + a
(B
7
Σ EIIp-tewm exp{ x x Wo ( 8) 2N
1
Y,
Here D = diag(expp X
B} In) BRLL
By simplifications (S1), (S3) and (S4), we fix Wv, set 3 = o/r and consider LoRA adaptation on a single data point. Akin to simplification (S2), we introduce ck c( c c(2)
Q C(3) E Lxd,
ch = c = x()), 0 ((K) (Wk BkAR), and ==)x=x(V)
x(9) x(9))
( +
r BBAa), c x(K),
(A.1)
Remark A.l. CK ck) (00 are constants with respect to adapting Bx. Ax with gradient updates. c c. C(3) are constants with respect to adapting Bq, Aq with gradient updates.
Therefore, the full LoRA adaptation loss in Definition A.1 becomes
D exp ((9) (Wo + BoAq) (W + BxAR) (XXRO) } xr - -Y
-Y
min CoR AgcAge
F
(A.2)
where D = diag ( (exp (C (Wk + BKAK) (CAR) = diag (exp (C (1) (W2
-
(C) ()) E RLXL
Similar to Section 3, we introduce the following problem characterize all possible gradient computation of (A.2), and arrive similar results as Section 3: almost linear algorithm for Problem 3.
Problem (Approximate LoRA Gradient Computation (ALoRAGC(L, d, r. c))). Assume all numeri- cal values be in log(L) ()) bits encoding. Let L follow (A.2), e 0, and || == max;, /Zzl The problem of approximating gradient computation of optimizing (A.2) is to find four surrogate gradient
matrices (G((A) R.drr G. IR"
rx) b== such that
(B) OC (A)
OC
max (1 (1
GIG,
DAQ 1lao p=
ABq
Theorem A.1 (Main Result: Existence of Almost Linear Time ALORAGC). Let ol olvlog L). Suppose all numerical values are in Olog - encoding. For μ Q, K. let Wp, = W + BB, for both μ Q, K, then there exists a +1+)(1) time
gaxd If [ w.l|| oo I and ((3)
0c
algorithm to solve ALORAGC(L, d = O(log L),r r = Lo(1), e = 1/poly (L)) (i.e., Problem 3) up to 1 (L) accuracy. In particular, this algorithm outputs gradient matrices (G(A) E Rdxr (B) gexd k== such that
max (1ll
0L T
(A)) |l,e
dc
-( 11 -= 1/poly(L).
JA
18

---

Published as a conference paper at ICLR 2025
Proof. See Appendix D for detailed proof.
19

---

Published as a conference paper at ICLR 2025
B RELATED WORKS
Fine-Grained Complexity. The Strong Exponential Time Hypothesis (SETH) is a conjecture in computational complexity theory that posits solving the Boolean satisfiability problem (SAT) for n variables requires time 2" in the worst case, up sub-exponential factors (Impagliazzo and Paturi, 2001). It extends the Exponential Time Hypothesis (ETH) by suggesting that no algorithm can solve k-SAT in ((2()=)))) time for any c > 0 (Calabro al., 2009). SETH has significant implications for the hardness of various computational problems, proving or disproving it would greatly enhance our understanding of computational limits (Williams, 2018b; 2013).
In essence, SETH is a stronger form of the P o NP conjecture, suggesting that our current best SAT algorithms are optimal. It states as follows:
Hypothesis 2 (SETH), For every c > 0, there is a positive integer k 2 3 such that S-SAT on formulas with n variables cannot be solved ((2(1=e)n) time, even by a randomized algorithm.
SETH is widely used for establishing fine-grained lower bounds for various algorithmic challenges, including k-Hitting Set and k-NAE-SAT (Williams, 2018b; Cygan et al., 2016). This conjecture is crucial in deriving conditional lower bounds for many sigmificant problems that otherwise have polynomial-time solutions in diverse fields such as pattern matching (Chen and Williams, 2019; Bringman and Künnemann, 2018; Bringmann et al., 2017; Bringmann and Mulzer, 2016; Backurs and Indyk, 2016; Bringmann, 2014; Abboud al., 2014), graph theory (Dalimooyyard al., 2022; Chan et al., 2022; Abboud et al., 2018; Gao et al., 2018; Krauthgamer and Trabelsi, 2018; Roditty and Vassilevska Williams, 2013), and computational geometry (Karthik and Manurangsi, 2020; Williams, 201 aa; Rubinstein, 2018; Chen, 2018; Buchin et al., 2016).
Based on this conjecture, our study employs fine- grainedine reductions under SETH to explore the computational limits of Low-Rank Adaptation (LoRA). Previous research in fine-graines reductions includes the work by Backurs et al. (2017). who examine the computational complexity of various Empirical Risk Minimization problems, such as kernel SVMs and kernel ridge. Alman et al. (2020) investigate the effectiveness of spectral graph theory on geometric graphs within the constraints of SETH. Aggarwal and Alman (2022) address the computational limitations of Batch Gaussian Kernel Density Estimation. Expanding on these studies, Gu et al. (2024a;b); Alman and Song (2024b; 2023) explore transformer attention and introduced tensor generalization. Alman and Yu (2024) establish the fundamental limitations on subquadratic alternatives to softmax transformers. Hu et al. (2024c) show that efficient dense associative memory a.k.a. modern Hopfield models and corresponding networks also need bounded query and key patterns for sub-quadratic time complexity. Compared to existing works, this work is, to the best of our knowledge, the first analysis of computational limits for parameter-efficient fine-tuning of large foundation models (Hu et al., 2021).
Low-Rank Adaptation (LoRA). In this paper, we focus on LoRA (Hu et al., 2021), method that leverages low-rank matrices to approximate updates to the weights of neural models. Various extensions of LoRA have been proposed to address different challenges in model training and deployment. For instance, DoRA (Liu et al., 2024) focus on enhanced parameter efficiency. QLoRA (Dettmers et al., 2024), LoftQ (Li et al., 2024), QA-LoRA (Xu et al., 2024b), and LQ-LoRA (Guo et al., 2024) focus on both memory and parameter efficiency in model compression and quantization. Additionally, DyLoRA (Li et al., 2020),, AdaLoRA (Zhang et al., 2023), and SoRA (Ding al., 2023) focus on dynamically determining the optimal rank r for LoRA implementations. LoRAHub (Huang et al., 2023) focus multi-task finetuning. LoRA+ (Hayou et al., 2024) focus efficient feature learning. Despite the methodological and empirical successes, the theoretical side is relatively underdevcloped. While Zeng and Lee (2024) explore the expressiveness of LoRA from universal- approximation perspective, and Hayou et al. (2024) investigate the optimal adapter learning rate with respect to large model width, the best of our knowledge, no existing analysis focuses on the computational limits of LoRA. Therefore, this work provides timely theoretical analysis of LoRA's computational limits, aiming to advance efficient finetuning of large foundation models terms of both parameter usage and computational time.
Outliers in Attention Heads. Our results indicate that outliers (e.g., large ||X]||| and |XW* aXBl/rl) in attention heads hamper LoRA efficiency and performance. This outlier effect is well-known in pretraining large foundation models for its negative impact models' quantization
20

---

Published as a conference paper at ICLR 2025
performance (Sun et al., 2024). For pretraining, prior works identify the existence of no-op tokens as the main source: tokens with small value vectors tend to receive significantly large attention weights (Hu et al., 2024a; Bondarenko et al., 2023). Specifically, Hu et al. (2024a) interpret this outlier effect as inefficient rare memory retrieval from the associative memory/modern Hopfield model perspective (Wu et al., 2024a;b; Xu et al., 2024a; Hu et al., 2025; 2024b;c; 2023) and propose the outlier-efficient Hopfield layer for transformer- based large models, demonstrating strong empirical performance and theoretical guarantees. The advantages of controlling outliers the attention heads of transformer-bas based large foundation models are also emphasized in various theoretical studies (Gu al., 2024a;b; Alman and Song, 2024a;b; 2023; Gao al., 2023a). Yet, the best of our knowledge, there is no existing work outliers in LoRA fine-tuning. This is the first work establishing that the LoRA adaptor weights might lead to performance and efficiency degradation due to their additive nature: ||W* + oxX B A/rll-
21

---

Published as a conference paper at ICLR 2025
C PROOFS OF SECTION 3
C.I PROOF OF LEMMA 3.1
Proof of Lemma 3.1. With LoRA loss (3.3), we have
dC(W)
1. d
(
1
dW
dw;
1=1
Note that for each j E [L] and i e [d].
d
(W))
(By (3.3)
dw,
(SWW) C(.) (000),((01(33
c(W),,
By Definition 3.5)
dW,
df(W);
(.1)
dw;
ar (W),u(W) (W))))
o(W)
(33) [
(y Definition 3.4)
dW,
du(W))
0: W -2 da (W))
aWW) i
u ((W), [+
dW,
dW,
(n)
(1T)
(By product rule and then chain rule)
Part (I). We have
du(W),
dexp C,W
By Definition 3.2)
dW.
dW.
dC,W
exp (C,W)
dW,
d(c,w) aw,
dC,w
= G,l. u(W)
(By
Cj aw.
Cj c = (C₂) (+i))
aw,
Part (II). We have
(u(W)), 11)
do W
By Definition 3.3)
dW,
dW,
(C O u(W)), 1t) (gls
B Definition 3.2)
(By element-wine wise product identity)
Combining (I) and (II), we get
d 1 (w)))
dW,
=o(W) (000 C - (, ( (c(()))) = =c(W),, CJ (diag (f(W)) - -f((ff/WWWW))))))) ((W) [..)
This completes the proof.
22

---

Published as a conference paper at ICLR 2025
C.2 PROOF OF LEMMA 3.2
First, we present helper lemma.
Lemma C.1. For any a E IR, let diaga(a) E IRddd be a x d diagonal matrix with all entries equal
to a. Let JB, JA IRd xrd be two matrices such that W = W2 + AB and W = W2 BQ via
BQ
diagd (Aq 1])
diaga (Aq rr 11)
BQ
diagd (Aq [,,
diaga (Aq rr 2))
JB
Ja
BQ
diago (Aql1, d])
diago (Aq(r, d))
The derivatives of loss function (3.3) w.r.t. AQ. BQQ are therefore
ac
L
d
J s
(dag (f(W):) - F(W)) [3,),
AAQ
1=1
0C
J (WW) 2. (iag (f(W)) f(W)) [,
0Bq
j=
i=1
Proof. The proof follows standard chain-rule and Lemma 3.1.
Then, we prove Lemma 3.2.
Proof of Lemma 3.2. From Lemma C.I, we have
2C =
Jo(W) diag (F(W)) f(W) [.
QAq
1=1 i=1
Σ
J 2
diag (I(W))) s(W))(W)) ((W2
1=1
(By (MM) (00) (c(W)) E (xX)
Σ
J r(W),
(By Definition 3.6)
1=1
[ (av1) (WW)))
= vec
Similarly,
OC
L
J Me(WW) [ (diag (I(W)) s(W))(())) [(
aBQ
j=1
==1
Σ 1=1
J C.
ddaag (f(W))) f(W) ((W))
(By (( (1)) (c(W)) T e R
(.C.P(W)
(By Definition 3.6)
= vec ((ow)) p(W) Aoc1o))
( and JACJ = =(wW) & AQc12)) )
(By
This completes the proof.
23

---

Published as a conference paper at ICLR 2025
C.3
PROOF OF LEMMA 3.4
Proof of Lemma 3.4. Our proof is built (Alman and Song, 2023, Lemma D.2). By definitions,
UVV Y - -UiVT -Y f(W) (0 +Y
(By = S(w) V)
= -VVVVV - f(W)) ((3)
I <//poly(L).
(By (Alman and Song. 2023, Lemma D.2))
This completes the proof.
C.4 PROOF OF LEMMA 3.5
Proof of Lemma 3.5. Our proof built on (Alman and Song, 2023, Lemma D.3).
Let (W) denote approximation qWW). By Lemma 3.4, U1V C(3) Y approximates c(W)
with controllable error.
Then, by setting
?(W) c(3) (1)
we turn ((W) into some low-rank representation
W = C3(3) (C(S))
VgU - C(3)yT
By k d = Io(1), it is obvious that computing ((3)
Vi U.
only takes L (+0(1)) time.
Lxcks KiXL
Then we can explicitly construct U2, V/2 Llxka in L [+0(1) time as follows:
U2 (C(3) -C(3) E Lxkg, V/ = (U,VT ( C(s)
E) l Lxbs
(x(++d)
Lx(d+d)
with 22 = 2d = ((1) by = O(log L). This leads to
W (C -c(a) ( YT
T nnot)= U2V2- -U2V2
Therefore, for controlling the approximation error, it holds
((3) (UiV (3))
C (03) -x) c(3)y
20
< d ( c
U1ViT -Y -c(W
s e/poly(L).
By Lemma 3.4)
Thus, we complete the proof.
24

---

Published as a conference paper at ICLR 2025
C.5 PROOF OF LEMMA 3.6
Proof of Lemma 3.6. We proceed the proof by constructing low-rank approximation of (-) with decomposing (-) into f(-) and g(-) through tensor formulation, and then approximating P1 part by part.
We denote @ for column-wise Kronecker product such that A A A|. k1] @ Bl. ki]] & for A E RL B 1x
B = [A[;1] @ B[,
Let ((W) = U, V and (W) = U2 denote matrix-mulliplication approximations to ((W) and (W), respectively.
Lxke
Lxci
Lxke
For the case of presentation, let U3
U 2 U2 and V3 = Vi
2 V22 It holds
|UgV3 Pı (W]ll
|UgV5 - -S( 3 (W))l
By p1 (W) = f(W) o (WW
[11 (2) (V2 2 122) f(W) o ((W)
[[(Uin]) @ (U2V3) ((W) q
(1 @ ((W) S(W) (WW) x
(l)(WW @ ((W) j(W)
W + (I) (W) ((W)
+ g (WW)
(By triangle inequality)
(t/poly(L).
(By Lemma 3.3 and Lemma 3.5)
Computationally, by ki, h2 Lo(1), computing U3 and Va takes [1+0(1) time.
This completes the proof.
25

---

Published as a conference paper at ICLR 2025
C.6 PROOF OF LEMMA 3.7
Proof of Lemma 3.7. By considering the following decomposition through tensor formul latin
(
Pa (2) = f (W), f (W) (
we approximate the P-(+) part by part. Specifically, for (I), we show its low-rank approximation by observing the low-rank-preservinn property of the multiplication between f() and q(-) (from Lemma 3.3 and Lemma 3.5). For (II), we show its low-rank approximation by the low-rank structure of f()) and (I).
Part (I), We define a function r(W) Rd + RR such that the j-th component r(W) =
(rW))) (W) for all [L]. Let F(W) denote the approximation of r(W) via decomposing into f(-) and g(-):
F(W);= = (F(W),.(()) - (UIV) 1 [(U2))) [2.11]
Vi V3 (U)li,,))
(C.1)
R1 L Lxke
for all j E [L]. This allows write P2 (w fW) diag(r(W)) with diag(F(W)) denoting diagonal matrix with diagonal entries being components of F(W).
Part (II). With r(-), we approximate p2(-) with io (W) = J(W) (iag(F(W)) as follows.
Since F(W) has low rank representation, and diag(F(()) is diagonal matrix, (5(() has low-rank representation by definition. Thus, we set (2(W = U4V1 / with U4 = U1 and V4 = diag(F(W)) Then, bound the approximation error
|UAVa
P2 (2
1172 P2 (l
[(W)) - ((W))r
max jc(+]
< max je(A] [[((W) ( F(W 1(W) + +[((W))F(W) ((Wrr (W)r)
(By triangle incquality)
Se/poly(L).
Computationally, computing V, V22 takes I. time by k h2 [o(1)
Once we have ViT 1/2 precomputed, (C.1) only takes k2k time for each E [Z]. Thus, the total time is O (Lkikz) = L +++(11) Since U1 and Vi takes ++(((1) time to construct and Va diag (F(W) V1 also takes (+0(() time, U2 and Va takes [+(((1) time to construct.
LXL
Lxki
This completes the proof.
26

---

Published as a conference paper at ICLR 2025
C.7 PROOF OF THEOREM 3.1
Proof of Theorem 3.1. By the definitions matrices p(W) (Lemma 3.2), Pr (W) and P2 (W) (Defi- nition 3.6), have p(W) Pi(W) P2(WW.
By Lemma 3.2, we have
0C AAq
= vec BB (CO)) p(W))(()
OC = vec ((ow) P(W)AQC(2)
(C.2)
BBq
Firstly, we note that the exact computation of Bi (C!D and AQC takes [ time, by Aq E RRxd BQ E Rdxrr, C(,, c(2) E RLddd Therefore, to show the existence of I,1+((1) al- gorithmms for Problem 2, we prove fast low-rank approximations for BQ (COI) T
P1 (W)CC) and (C(") T Ag (((2) as follows. The fast low-rank approximations for - -Bo (C(U) T P2 P2(W)C(()
and (C(1) p2 p2 trivially follow.
Fast Approximation for Bi (C(U) P1 (W)C()) Using (W), (W) as the approximations to pi (W), by Lemma 3.6, it takes L ++((( time to construct U3. V/3 E g4xks subject to
B3 (cw) (W)) = = (cw) U3V c())
dxL
rxd
Licks
1 Lxd
Then we compute B
(C())
Us
Vi
c(2). By r, d, ki, = L)()) this takes L [+((1) time.
rxks
laxd
Finally we compute
BJ
T (C())
U3
V33 ((2). By r, d, I,((), this takes 7, (11+)(1)
time. So, overall running time is still L (1((11)
Fast Approximation for (C(D) T Pi Ag Similarly, computing (CC) T pi (W))AOC(())
takes L (l+)(1) time.
Fast Approximation for (C.2). Notably, above results hold for both p2(x) and pi (x). Therefore, computing B3 (CO) P(W))())) (CaI) T
pg also takes L [+0(1) time.
Approximation Error. We have
0C
((A)
0AQ
vec B (CCU) M(T))1) vee (Bō BB (cwu) p())
(By Lemma 3.2)
( BB (BB (ccu) p(W))(e))
[B (oa)) (())
) (By definition,
||A|| maxiy A4yl for any matrix A)
< ( B (cw)) (W) (m)) ((2)
)|
[Bō ( B (cw)
(pz iz (W) (2)
(By Definition and triangle inequality)
< |B cc00
[())
(1()(()) 5. (W))l + (W) (l)) (By the sub-multiplicative property of cc-norm)
s </pool(LL).
(By Lemma 3.6 and Lemma 3.7)
27

---

Published as a conference paper at ICLR 2025
Similarly, it holds
dc ((B)
vec ((ow) T
vec BB (ow)) T ((W)e
P(W)ADCCC)
[(Cw)) A0 ((a11) ((W) (20)) )(
((cw) (pi(W) - (W)) Ao )|1 + ||(((rt)) (p2 (2()) Aocce))
00 ((a)
((0)
(l) (W) - (w + (l(2((W) -52 (W)
</poly(L).
Setting = 1 1/poly(L), we complete the proof.
28

---

Published as a conference paper at ICLR 2025
D PROOF OF THEOREM A.
We prepare the proof with the following definitions and lemmas.
Similar to Section 3, we introduce the u(-), ot.),, f(-),, notations. Notably, we introduce them for both and Q because there are two sets of adaptors: Bk: Ax and Aq.
Definition D.1 (u(-)). Let C = o & k and C = cº @ oc Recall that Cj C/ Rx
are sub-block matrices of CK2 CO, For every j E [T.]. we define two functions uk (W) j, U1q (
I 1d RR uk (W) = exp w e = and un [W); = exp C9 W.
Definition D.2 (a(-)). Let CK = c(l) k @ Ck and C = c² @ c@ Recall that C C e R.x are sub-block matrices of C cO. For every index [L]. we define two func-
tions aq (W) or (W) R& + R: (o = (exp C. W 1z) E IR and ox (W] = (exp ( W 11) E ER
Definition D.3 (f(-)). Let aq (w) ox
ax (W)₂ E R follow Definition D.2, and ux (W) ( E RR follow Definition D.1. For any 2 E [L], we define two functions fQ(W) fI (W), Rdd - R. as
fQ(W) = aq (Q) un (W),
fK fw(W),
or (W), ux (W),
Lx1
scalar
LX1
such that fq(W), (W) E LL denote the matrices whose j-th rows are fQ(W)) JK [-
Definition D.4 (c(-)). For every j E [7... let (Q() fx (W) 1: Rd RR follow Definition D.3.
For every i [d], let [. E R' follow (A.1). For each [L] and i E [d]. define two functions cq( [ (W)..
j.:. CK (W) مزر Rd x Rdd + R as
cQ (WW) = (W (.
CK ()) (Jk (W), | Y
Here 22 is the (j. i) coordinate/location of E Rxd for j E [A], i E [d].
These give
W
(Q(W)
(3)
and
CK W
JK W
(3)
Lxd
LXL
Lxd
LXd
Lxd
LXL
Lxd
Lxd
Definition D.5. For every j [L] and every i [d]. let Co(W) co(W)),, and Lx Cx(W) د1 Ck (W),,1/2
Let matrix Wq W/ BQ WK Wi + Bx Ax and loss function L. be (A.2). From above definitions, it holds L(AK, BK, Aq, BB) L(W Wx) and the adaptation gradients of L (A.2) become
ac (W o. (.,
L (
Σ
Σ
Co(We)
Σ
co
o)...
(D.I)
aW4
Ow Q
Oe Q
i
and
0L
(Wq. Wx)
θ
1 d
1
1
aW T
OW
CK
aW
2
Σ
ck
(
W
(D.2)
1
i=1
1
i=1
29

---

Published as a conference paper at ICLR 2025
(D.1) and (D.2) present decomposition of the gradients of LoRA loss L (A.2) aspect to We and WK into L terms, each simple enough for tracking gradient computation.
Now, we are ready to compute the gradients of the LoRA loss aspect to Wi and W as follows.
Lemma D.1 (Low-Rank Decomposition of LoRA Gradients). Let Cк C @ C Cq = C & C Let fine-tuning weights be Wq W BQAQ and WK Wk + BK and the loss function L follow Definition D.5. It holds
OC (W q. Wx)
L
(W))g, js (c2) T (ding (Je (Wa), fo (Wa), fo (W [.a)]
cQ
(W
OW,
1=1
OC (W WK)
Σ>
1.
CK (KK) 2.4 (ctT) ddag JKK (Wx)) (WK)), SK (WK)) ((
OW
1=1 1=1
Proof.
This lemma is generalization of Lemma 3.1.
L
Next, introduce the q()) and p(-) notations. Again, there two sets corresponding the two sets of adaptors.
Definition D.6. Let QK W == (3) (ex (W)) E LRL 90 (WL) == (3)3) (CQ(W)) E LxL
Definition D.7. For every index [7.], we define pQo (W) (W), E R. as
po (W) = diag (Se (W))) S0 10 (W) 92 (2)
PK (W)) = (iaa [fx (W),) fx (W), fK (W),) qK (W),.
Lemma D.1 presents the Low-Rank Decomposition of LoRA Gradients. Before using the chain rule to compute the gradients of the loss L (A.2) with respect to AQ, Ak, Bo, Bx, we need to define matrix T to handle the transpose term W K-
Lemma D.2 (Sparse Matrix T). For any matrix W Rmxx, there exists a matrix T(m, n) Rmm such that W T = T(m, (W). The matrix 7 7'mm, n) is sparse. Namely, for any i [mn], there exist < p S m and < k S such that i (p 1)n + k. Then, for any i, E [mn]].
[1,
if j = (k: 1)m + P.
T(m, m)(i, =
o, otherwise.
Proof. For any < p m and < k n. consider the position of W[p, k] in W and W
In W. W(p, k| = W[(k 1)m + pl.
In W W[p, k| [ - 1)n + k].
Thus.
W [
T(m, n) -
= T(m, n) [i. WG].
This completes the proof.
Now, are ready compute the gradients of the LoRA loss (A.2) with respect to Aq, Ax, Bo, Bx using the chain rule as follows.
30

---

Published as a conference paper at ICLR 2025
Lemma D.3. For any E IR, let diagala) Rddd be a x d diagonal matrix with all entries equal to a. Recall We = W + Ao and WK = W + Bx Ax. Let JBK: Jax Rd xrd be two matrices such that We W + J JB AQ and We W + JA via
BK
diaga (Ax [1, 11)
diaga (Ax [r. 11)
BK
diaga (Ax [1,2]
diags (Ax (r; (r,
JBK
Jaa
Bx
diaga (Ax [xx]1,d] d])
diaga (Ak [r, d])
Let JBK JAx be two matrices such that W = W - JBx AK and WK- = W + JAN Bx via
BQ
diaga (Aq 1I)
diaga (Aqlr (r. 1)) diaga (Aq (r. 2
BQ
diaga (Aq 21)
JBQ
JAa
Bq
diaga (Aq d])
diaga (Aqlr.)) d))
Then the derivatives of loss function L (A.2) respect to Ag. Bo, Bx
OC
ΣΣ
L d
(JBg) T ca (Wa)g, 21 (ct) (din (fa (W (Wa))) fo (Wa) fo (Wa) 3) (.0)
0Ag
[=1
Oc
L ΣΣ (Jدq) ca (Wa),, (C)) diag (fa (Wa),) fo (Wa), fo (Wa))) c(.0)
8Ba
OC
ΣΣ
(T (dd JBK) сK Wkk jo (c#) diag fK (W%) )) fx (Wic) fx ( [1
0Ak
il
Oc
ΣΣ 1=1
4
(T (d2, (d d²) JAK) ck [ (c#) (ding fx (WT) fx ( fx (W ;) [.0)
0Bx
Proof.
ac
and follow Lemma C.I directly.
0Ag
BB
For DAK
ac
and
8C
we have:
W =T(dP, (((P,d))W W =T(d d²) (WT + AK) =T(P,, d2) (W + JAN Bx)
Therefore,
ac O OC(W Q WK)
0Ak AAK
oW
Q Wx)
T(df, dt JBx
aw
Similarly,
ac T AL(W WK)
0B K
0Bk
OW
OC(W Q. W
Wx)
T(d2, JJJAK
OW Thus, we complete the proof by following the conclusions of Lemma D. Next, we simplify the derivatives with p(-) notation.
31

---

Published as a conference paper at ICLR 2025
Lemma D.4. Let qQ, 9K E RExL defined in Definition D.6. Let pQ. PQ.PK PK tion D.7. Then it holds
defined in Defini-
dc
BQ (2))) Po(Wa))0
vec
AAq
0C
((c))) T PQ (
veC
QBQ
0c T (d, (d)
BK (c T
Px [ c(22)
0AK
vec
0c
vec ((cH) PK [ Ax xx
T (d. dd)
0B
Proof.
For JAg
and
8C
we follow the proof of Theorem 3.1.
For
8C 0A
we have
Dc
OAk
L d
JBX) CK ( did (c*) (((
"ddiag diag fx (WT))) fK (WK)). fx (M²)), ") ((3)
(T (J))))
=
i=
(By Lemma D.3)
= Σ
( (d. dd) JBX) ((x))((()) (c/) diag fK (Wk),) fK (Wk) fx (
( k 1
9K
2=1
(By Definition D.6)
L
=T ( dd²
T
Σ JT (c/) PK W
(By Definition D.7)
i
2=1
=T (1. d3) vec B (xk)
Pk W ck
(By Lemma 2.1)
Similarly, for a8 holds
0B
ΣΣ (T(d, d)JAk) CK (WT), 2e (ck) diag fK (wk), )) fK (WK) fK (Wz),) ((3) [-,
j=1
T (d) ( diag SK (KK)) JK (WK) JK (W*) i ")
= Σ
ax Wk
2-1
(dP, T
JAK (ck)
7=1
=T T vec ((c2))
W Ax Ck2
pK
This completes the proof.
Similarly, Lemma D.4 states that the chain rule terms for characterizing Problem 3 are tied to po p.(+) ((A)
and px Q(-). Therefore, characterize Go G(B) 7(A) and ((B) (i.e., the approximations of
32

---

Published as a conference paper at ICLR 2025
Go 6 G(A) and G for μ Q, K, we need to approximate the functions (u(+), gx(-),
cx()), and thus p-(-) with precision guarantees. To do so, is convenient consider the following decomposition of P.(-) for = Q, K.
Definition D.8. For every index _ E [L], we define pl (W),, p5 (W2 RR as
pi (W) diag ( (W) 92 (
P2 [W) = Sq (W), 1Q [ 12 (W) fK (W) ; 9K (W),,
pf (W), diag
K (W), fK (W), fK (W), T 9k (W),
p2
such that pQ (Q(W) P1
Q (W] P2
Q (W) PQ (W) pi (W)
P2 O (W).
Overview of Our Proof Strategy. Similar to Section 3, we adopt the following strategy: term- by-term approximation for precision-guarantedd almost linear time algorithms to compute LoRA gradients in Problem 3. For all Q, K, we do the following.
Step 1. Prove the existence of almost linear approximation algorithms for fa(-), (x(+), and (x(+) via low-rank approximation (Lemma D.5, Lemma D.7, and Lemma D.6).
Step 2. Prove the existence of almost linear approximation algorithms for z4 p2(()), and thus Pu(-) via the now-rank-presers preserving property of the multiplication between fu(() and (-)-) (Lemma D.8 and Lemma D.9).
Step 3. Prove the existence of almost linear approximation algorithms for the LoRA adapter gradients and af in Lemma D.4) using the results from Step and Step (i.e., 8A." 8Ax 32," DE (Theorem A.I).
Step We start with low-rank approximations for
Lemma D.5 (Approximate fQ(+), (.(()). Let r ol olooo L), for μ = Q, K. suppose c c( C (c(.2)
RLxdd W _axd and (W) D- exp
with D) following (A.2). There
exists h [o(1) such that if cd W|
and
T
and
c
r, then there exist four matrices
UP. v.. UK V.K R such that
(P(V)) (W)
<</poly(L.,
2
(V - (K( S <//poly(L).
In addition, it takes L (01) time to construct UP, vp, VKK
Proof. This follows the proof of Lemma 3.3
Lemma D.6 (Approximate cq(+), (+)). Assume all numerical values in Olog L) bits. Let d = Olog L) and cx(W), (W) I 4xd follows Definition D.4. Then there exist four matrices U v UK ViK L such that
|UP(VP) -Y - cQ(
s <e/poly(L),
(U -Y cx( </ppoly(L).
Proof. This follows the proof of Lemma 3.4
Lemma D.7 (Approximate q0(+) Let K2 I,(1), cQ(W), (x()x)()))))) RLxd follows Def-
inition D.4 and let qK (W) == C(3) (cx (W)) E Rixt (W) = C( (cQ(W)) E R
33

---

Published as a conference paper at ICLR 2025
(follows Definition D.6). Then there exist four matrices U/2 V2 U2 V/2h BLaks such that
(V 20 (W') S se/poly(L),
| (V22) qK (W))l S se/poly(L).
In addition, it takes L (+(( time to construct U.? V22 U. V₂2.
Proof. This follows the proof of Lemma 3.5
Step Now, we use above lemmas construct low-rank approximations for pt) P.().
Lemma D.8 (Approximate (.), pf (.)) Let ki, k2, ka = Lo(1), For μ K,Q, suppose Ufi, V/" Rixki approximate (W) E REXL such that (VU](VP)) - -wWlll S </poly(L). and Ug, : V/2" E 12 approximate the gu (W) E BLXL such that (VZ)) -qa(W)l S
e/poly (L). Then there exist two matrices U3, Vi" E Blxks such that
[V((( (w))l S e/poly(L), for K,Q. Ug VgK.
In addition, it takes L [+((1 time to construct
Proof. This follows the proof of Lemma 3.6
Lemma D.9 (Approximate p3 (-), p (-)). Let k1, h4 Lo1), Let 2o (W), p (W) E R such that its j-th column is p2 (W) = ((W), g(W) follow Definition D.8, for each i E [L]. For = K, Q. suppose U., V/ R Ri approximates the (W) such that (VP") (W)) 1100 </pooy(LL), and UY, VJ" Bllks approximates the ga (W) E RLXL such that [VZ)( - q. (W) S s//poly (I). Then there exist matrices U4, V E Lx such that
[V(' p W Is S c/poly(L), for μ K,
In addition, it takes [1+ time to construct U., vp. UK V.K.
Proof. This follows the proof of Lemma 3.7
Step 3. Combining above, we arrive our main result: almost linear algorithm for Problem 3.
Theorem D.1 (Main Result: Existence of almost Linear Time ALoRAGC), Let I of v Vog L) Suppose all numerical values are in Ollog -)-bits encoding. Then there exists -1++(1) time algorithm to solve ALoRAGC (I, O(log L), r I,( e 1/poly(L) (i.e Problem 3) up to 1 1/poly(L) accuracy. particular, this algorithm outputs gradient matrices (G(A)) e Rddxr G(1)) Rexd) J== such that
max (1
0C O
(n) p
0L OA
((.11
))
1/poly(L), for μ K,Q. 00
Proof of Theorem A.I. By the definitions of matrices pf (W), pi (W), p (W), (W) in Defini- tion D.8 and px (W), (W))) (W) in Definition D.7. It straightforward that
Pk (W)- pk (W)
p2 K (W). and (W( pi p (W) P2 (W).
34

---

Published as a conference paper at ICLR 2025
According to Lemma D.4, we have
0C
Bé (co)) pQ (Wa) ce)
vec
AAq
2C
((o!") pQ (W A
vec
agg
0C T (dl, de))
vec BK ( PK
W c
dAk
OC
((x)) T
0ВK
T (d?, (d)
vec
PK
W
Next, we compute the time complexity of approximating these gradients to 1/poly(L) precision. For ac and ac we follow the proof of Theorem 3.1. Specifically, takes L I+o(1) time to öAg äB," approximate these gradients to 1/poly (L) precision.
For OC and ac "Bx
is constant matrix. In addition, due to Theo- and vee ((cK) PK (WR) Ax Ax which are take L [++((I) time approximate to 1/poly(L) precision. and ac ane
first note that (T
84K
rem 3.1, vec
B (ck)
K
PK
W K
((2) K
ac similar Therefore, show the existence of L algorithms for Problem 3, we
8Ag
prove exact computation for df vec BB (c2) T
рk [W ck
(2)
and
T (d.d) T vec ((o)) PK (K)) Ax ck takes oLL (o()) time as follows.
Exact Computation for T (ed " vec B (c(K))
PK [
(2) c
Recall from
Lemma D.2 that T de)) is sparse matrix with only one non-zero entry in each row. Thus, for each row, the exact computation takes O(1) time. Therefore, the total time is (dd)) Given that d = o(log L), the overall time is still (1++(11)
Exact Computation for T (L, (P) vec ((++) pk [Wk) Ax
Axck2) (12
Siiiiarly,, computing
T (d,d) T vec ((cØ)) T
[ AxCR) takes Odd²) time. Therefore, the total time is (df)) Given that o(log L), the overall time is still L+0(1)
Approximation Error:
For Oc and ac DAq
we follow the proof of Theorem 3.1. For ac 8Ag
8Bg"
0c G(A))
0A
T (dl T vec
B (c())
K PK W
C - -T vec
B (ck)) T PK
(W
ck
< ( d2) 7
Bb (ck)
PK W
(2)
-(BR
[ (cH)
PK
W
(2)
(BB (c()
(
(WX)
(
{Bk (c(l)
K
(WT)
- (Wk)
c
2
< |Bx oo
c+
||
(I((f
(wX)
(wT)
+
(
- F (wT)
[
( (w
20
S (L)))((LL),
where the first step follows from Lemma D.3, the second step follows from the definition maxij Aiy for any matrix A, the third step follows from Definition D.8 and the triangle inequality,
|| =
35

---

Published as a conference paper at ICLR 2025
the fourth step follows from the sub- sub-muliiplicative property of the co-norm, and the last step follows from Lemma D.8 and Lemma D.9.
Similarly, for ac k
it holds
0C {(B)
-
0Bx G
T (dP, dP)
vec ((22) T
PK (Kk) AK
Ax (2) (dP,, T vve ((o
W K
Ax Ax (2)
)
PK
$ ((T (d,, (P),
((c2) pk
(WK) Ax (22)
- - T
[
AxC (2)
DK
< ((()))
( কス (Wk))
AxC
+
+[((<()) T
2
[ - T3 (WR)) Ax
z | oo
K
cx2
(1 (w
(wT)
+
(wk)
(
- P2 )
S c/poly(L).
Setting e = 1/)oly(L), we complete the proof.
36

---

Published as a conference paper at ICLR 2025
E PROOF OF THEOREM 4.
We recall our definition of ALoRAGC(L, d, e) for special case from Problem 2 subject to LoRA loss (3.3). We aim to make the reduction from AAttLG r,, (Alman and Song, 2024a, Definition 1.4) to our problem ALORAGC(L, d, r)).
Definition E.1 (Approximate Attention Loss Gradient Computation GA r, r.),, Defini tion 1.4 of (Alman and Song, 2024a)). Given four x r size matrices A RLxr, A _ RLxr, A3 E RLxr, E E Rexr and a square matrix X E Rrxr to be fixed matrices. Assume that || oc S B. A2llo & B. Assume all numerical values are in log (og(Lssbits encoding. Let ((X)= = 2 2 exp( A1XA /r) E which D = diag(exp(AA) A1 XAA /r) 11). Let
dc(x)
dX denote the gradient of loss function L. The goal is to output matrix R such that
dc(x) dx
1
11 S.
We recall the main hardness result of (Alman and Song, 2024a) which shows lower bound of AAt r) (Definition E. in the following particular case by assuming SETH.
Lemma E.1 (Theorem 5.5 of (Alman and Song, 2024a)). Let N + by any function with
<(L) (1) and (L) olog L). Assuming SETH, there is algorithm running in time ( for any constant >> 0 for Approximate Attention Loss Gradient Computation ACttL r,,,)). even in the case where r (log L) and the input matrices satisfy | //oloo/ || A1 S
O(Vlog L x(L)) = B, E = 0, X Xl, for some scalar À E [0, 1], and & = O ((1/(log)) L)
Finally, we are ready for our main proof of Theorem 4.1.
Proof. Considering Problem 2, we start with the following (11) reduction. Given the instance of AAttLG((L,r,e r,)) and A R2rr Ag Lxr Ag E RLxr, E = 0, B O(ylog L s(L)). then transfer this instance to the instance of ALORAGC(L, d, r)) by making the following substitution:
BQ (1) A2,
O Hr,,0())
= AA. 0 A,A0= 1 0 ,.= B.
Exr Lx(d-r)
Exr Lx(d-r)
rXr rx(d-r)
Then we have ||C(2)||oo, |[C(1) BB || S such that
((1) AQ (c1z))
A1 X XA/ c(1)
and hence
exp(A1 /r (oxp((C)) (C (c12)
This implies that the upper L x subblock exactly the same. (Here we can assume =
(D- e''eep(cc") BQAQ(( J(O) V)lexr (D- (ep(ArXAT//).A
Lxr.
This follows that the derivative with respect X of the RHS is the as the partial derivative with respect to Aq by embedding X into a subblock of Aq. Now, by letting G = 9 in the AAttLGCC(Z,r, c), which finishes the reduction. This completes the proof.
37

---

Published as a conference paper at ICLR 2025
F QUADRATIC TIME COMPLEXITY OF EXACT LORA GRADIENT COMPUTATION
Here, we make more comments on tensor-trick decomposed LoRA loss from Lemma 3.1:
(17)
(m)
dC(w) dw
j. C
diag (S(W),) (WW)/(W)
[,a]
(i.e., (3.5))
1=
Remark F.1 (Benefit from Tensor Trick: Speedup Seemingly Cubic Time Exact Computation). Lemma 3.1 highlights the benefits of the tensor trick and the potential for speeding up exact LoRA adaptation on transformer-base models. To be more specific, for any j E [L]. Part-(I) is an
L L matrix, thus requiring (L)2) time to compute. Moreover, with total of L terms, the overall computation time amounts to (
However, (3.5) decomposes Part-(T) into diagonal Part-(II) and low-rank Part-(III) (specifically, rank-1), 1). This decomposition allows us to reduce the computation time of Part-(I) to (L) for each j E [L]. and of the entire ac(W)/aW to O(L²). Our next theorem verifies this claim and shows such seemingly cubic time exact computation is fact quadratic.
Definition F.1. Let nı, ne,, ng denote any three positive integers. We use Tmat (n1, m2, na) to denote the time of multiplying n1 n2 matrix with another n22 n2..
Theorem F.1 (Exact LoRA Gradient Computation Takes Quadratic Time). Suppose the following objects are given and if following conditions hold,
Let C()), C(2), ((3) IR Lxd be in (3.2). Let Bi _ "exx,,, .A E RRrd W idddd be in (3.3).
Let f(),, c( P1)))P.(.))) (-), Pa(-) follow from their definitions in Section 3.
Let G(A) = ac G(
ac (Where L is defined in (3.3) ).
Then
make exact computation of G6 G in O (d, L) + Tmar (d, d, L)
Tmae (d, d, r)) time.
Proof. Due to Lemma 3.2, it holds
OC 0Aq
= vec [ (Cw) ((N)C(2))
OC
vec ((ow)) pQ
8B.
Recall that the decomposition of p(W) Pi (W) P2 (W) And according Definition 3.6, for every index j E [L].
Pi W diag (1 (W), (W), Pa (W) = f (W), (W), (W))
In addition, due Lemma 3.2, g (W) defined as
(W) = (3) (c(W)) E 4XL
Therefore, we compute f(W),
, c W PI W Pa order as follows. Then we combine them together to get total running time.
Step 1. We compute (WW).
Note that
Lxd dxL (()) W (C(2))T)
f(W) D-1 exp
where
D diag(exp (C()) (ex(exppp"") (((2)) I2). (2))
38

---

Published as a conference paper at ICLR 2025
We firstly compute (xp(C")((C)) which takes time of Taa (d, Tmaa (d, L, L)
Then, compute D which takes O(L2) time.
Then, we can compute ((W) which takes ((L2) time.
Thus, the overall time is
Maat (d, d, L) + Tmat (d, L, + = O(Tmat (d, (d,d, L) Tmae (d, L, L)).
Therefore, the proof is completed.
Step 2. We compute (W) Based on the Definition 3.5, which is
Lxd c(W) f(W) C -Y.
Computing f(W)C(3) takes time of Tmat (d. L, L) and computing f(W)C(3) Y takes time of (Ld). Thus, the overall time Tmat (d, L, L) + O(Ld) ( L, L)).
Step 3. We compute (W). Recall that
Lxd dxL
q(W) c(W) (C(S))
Therefore, it takes time O(Tmat (d, I., L)).
Step 4. We compute p (W). Note that due to Definition 3.6, which is
Pi (W) = diag (W),) (W),, P2(W) = f (W), f (W), a(W),
such that pWV) = P1 (W) - (WW)
Since diag diag(f (fW)), ) diagonal matrix and ((W)) is rank-one matrix, we know that p(W) E RC can be computed in O(L)), for each j [T.]. Thus we can construct matrix pl (W) E RRLX in O(L) = O(L2) time in total.
Step 5. Using Lemma 3.2, know that
rxd dxL. LxL Lxd
dxL Lxb Lxd
ac
Oc
vec( B (CO)) p(W) C(2)),
vec (CC)) p(W) Aq C(21).
0.g
aBq
Suppose BQ E dR AQ E Rxxd ((1), ((2) C(3) E BLLxd are given, then each of the gradients can computed time (T (d, L, L) + Tmat (d, d, L) - Tiaa (d, d, d)r)..
Thus, the overall running time for gradients computation is
O (d, L, L) + Tmae (d, d, L) + Tmat (d, d, r)).
This completes the proof.
39

---

Published as a conference paper at ICLR 2025
G SHOOF-OF-CONCEP" EXPERIMENTS
Here provide minimally sufficient numerical re- sults to back our theory. For generality, we con- sider the full LoRA fine-tuning WK, Wo, Wv as analyzed in Appendix A.
Table 1: Training Time (Per Epoch) Compari- son between LoRA on "Standard vs. Outlier-Free" Transformers for 3 OPT Model Sizes. We perform full LoRA fine-tuning lion heads in Open Pretrained Transformers (OPTs) (Zhang et al., 2022). Our results show that, with norm- bound control, Outlier-Free Transformers (Hu et al., 2024a) are 5.5% faster for OPT- 1TT-2 13.1% faster for OPT-350M, and 33.3% faster for OPT-1.3B.
WK. We, Wv of the atten-
Objective: Control Norms of Attention Heads' Pretrained Weights to Achieve Speedup. We use the outler-removvng transformer architecture proposed by Hu et al. (2024a) to showcase the efficiency gains from controlling the norms of This type of ar-
{Ill || [B,lI) chitectures bounds these norms by preventing ex- treme weight values inherited from the pretraining process.
Model
Standard Transformer
Outlier-Free Transformer
OPT-125M
58 mins
mins (-5.2%)
OPT-350M
69 min
61 min (-11.6%)
Fine-Tuning Task. We perform cross-modality fine- tuning on sizes of the Open Pretrained Transformer (OPT) models (Zhang et al., 2022): OPT125M, OPT350M and OPT13B. Specifically, we adapt OPT language mod- els speech data, creating a SpeechLM (Speech Language Model) with both text and speech modalities, following (Maiti al., 2024; Wu al., 2024c).
LoRA Standard Transformer
LoRA on Outlier-Free Transformer
Minute
25
OPT-125m
OPT-350m
OPT-1.3b
Pretrianed Model Setup. We test our theory on three OPT model sizes: OPT125M, OPT350M, and OPT1.3B. Each model size has two versions: one with standard transformers (Vaswani et al., 2017) and another with outlier-removng (outlier-free free) transformers (Hu et al., 2024a). The training process for all OPT models follows (Hu et al., 2024a).
Figure
LoRA Setup. Following the original LoRA settings (Hu al., 2021), we fine-tune the models using a rank of 128 and an alpha value of 256.
Data. We use the LibriLight dataset (Kahn et al., 2020) for fine-tuning. LibriLight contains 60,000 hours of audiobook recordings from 7,000 speakers, totaling 12 million utterances.
Computational Resource. conduct all experiments using NVIDIA A100 GPU with 80GB of memory. Our code are based on standard PyTorch and the Hugging Face Transformer Library.
Efficiency Results: Training Time Comparison. To demonstrate the efficiency benefits of norm control suggested by Theorems 3.1, 4.1 and A. compare the training speed of the two architec- tures. Table and Figure 1, we report the training time per epoch for both architectures across three model sizes. Our results indicate that the Outlier-Free Transformer is 5.5% faster for OPT-125M. 13.1% faster for OPT-350M, and 33.3% faster for OPT-1.3B.
These numerical results align with theory: proper normalization of weights and inputs enhances LoRA training efficiency. Notably, we observe greater computational gains in larger models.
40


Reviews:
[{"review_id": "eZjvIjvULf", "reviewer": "Reviewer_Yw3J", "summary": "This paper studies how to make large Transformer models more computationally efficient during fine-tuning. The main contributions are:\n* Identifying a critical point of efficiency where models can be fine-tuned with less computation if they are below this threshold.\n* Proposing a new method that can complete model fine-tuning in almost linear time, which is much faster than traditional methods.", "questions": "* Can the authors discuss the potential impact of LoRA adaptation on model generalization? \n* How does the efficiency of the proposed methods scale with larger models and datasets？", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The paper introduces a novel theoretical analysis on Low-Rank Adaptation (LoRA) for Transformer models, marking an innovative contribution to the fields of natural language processing and machine learning. It approaches the problem of LoRA adaptation from a fresh perspective, focusing on computational limits and efficiency, which is particularly novel in the context of large foundation models. Additionally, the paper presents an innovative method by proposing an almost linear-time algorithm for LoRA adaptation, which is a significant advancement over existing methods that typically have quadratic complexity.", "weaknesses": "* The paper's primary focus seems to be on theoretical analysis. To strengthen the claims, experimental validation with real-world datasets would be beneficial. Specifically, demonstrating the practical efficiency of the proposed algorithms on standard benchmarks could provide actionable insights into their performance.\n* It would be valuable to see how the proposed methods compare to current state-of-the-art techniques in terms of both efficiency and accuracy. This comparison could highlight the advantages and potential limitations of the new algorithms.models and datasets?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "XEsALxdAg2", "reviewer": "Reviewer_FVCG", "summary": "This work investigates the computational limits of Low-Rank Adaptation (LoRA) for finetuning transformer models through fine-grained complexity analysis. The central insight is that the low-rank structure within LoRA's gradient computations can enable algorithmic speedup. Two main contributions are highlighted:\n\n1. **Efficiency Phase Transition**: The study identifies a sharp efficiency threshold for rank-\\(r\\) LoRA update algorithms based on norms derived from the interactions between input sequences, pretrained weights, and adapter matrices. Efficient (sub-quadratic) algorithms are possible only when these norms fall below a specified threshold.\n\n2. **Nearly Linear Algorithms**: By leveraging hierarchical low-rank structures in LoRA gradients, the authors construct nearly linear approximation algorithms for LoRA adaptations, assuming the Strong Exponential Time Hypothesis (SETH).\n\nTo validate the theoretical findings, the authors explore partial and full weight adaptation scenarios within transformer attention heads, focusing on weights like $W_V$, $W_Q$, and $W_K$.", "questions": "Could you please provide additional explanation of the theoretical results? \n\nAdditionally, would it be possible to include some toy or controlled experiments, or other illustrations to help clarify the findings?", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "This paper tackles a highly relevant and timely topic: Low-Rank Adaptation (LoRA). LoRA has gained widespread popularity in practice for its effectiveness in fine-tuning large models efficiently. Despite its practical success, there has been a notable gap in the theoretical understanding of LoRA, making this study’s contributions especially valuable to the field. Developing a rigorous theoretical foundation for LoRA will not only solidify its current applications but also open doors for future research and refinement of the technique.\n\nThe abstract and introduction are clear, engaging, and well-crafted. They effectively set the stage for the paper, with a strong motivation that highlights both the practical importance of LoRA and the need for a deeper theoretical exploration. The authors have done a commendable job in outlining the primary contributions, making it easy for readers to understand the key takeaways from the study. The literature review is thorough and provides an excellent context for where this work fits within the broader landscape of model adaptation techniques.\n\nThe inclusion of a paragraph on paper organization is appreciated, as it offers a helpful roadmap for readers. It ensures that the structure of the paper is transparent from the outset, allowing readers to follow the flow of ideas with ease.\n\nThe authors have also set a high standard for notation and technical formalism. The clarity and consistency of notation enhance readability.\n\nWhile the technical results appear sound, I should note that, as someone not fully specialized in this type of analysis, I may not have caught every nuance. However, the reasoning seems robust, and the proofs are presented in a way that suggests a careful, thorough approach.\n\nFinally, the conclusion is well-done and reinforces the main points. It synthesizes the findings effectively and reflects on their implications, offering insights into how these results might shape future research in model adaptation. Overall, this paper makes a significant contribution to bridging the gap between LoRA’s practical success and its theoretical understanding, providing a strong foundation for ongoing exploration in the field.", "weaknesses": "This paper currently feels dense and challenging to navigate, as it primarily consists of a series of definitions, lemmas, and theorems, often presented without sufficient explanation, clarification, or intuitive context. For readers who are not already experts in this area, this can make it difficult to grasp the key concepts and results. \n\nThere are several opportunities to improve accessibility and readability. Some of the definitions would be more appropriately placed in an appendix, as the main text is quite heavy with formal definitions, lemmas, and theorems. Moving certain definitions to an appendix could help streamline the main text, allowing readers to focus on the core arguments without getting overwhelmed by technical details.\n\nIn addition, a few of the lemmas lack clear statements, which can lead to confusion. For instance, in Lemma 1.1, the term \\(L\\) is introduced without any accompanying explanation. It would be helpful to review the formulations to ensure clarity, even if the technical details are correct. Improving the precision in how terms are introduced will aid readers in following the logical flow more naturally, without having to reread sections to understand each step.\n\nGiven the extensive number of definitions, it would be beneficial to assign descriptive names to them. Naming each definition provides a quick reference, helping readers keep track of terms and concepts as they reappear later in the paper. Otherwise, it’s easy to lose track of which definition corresponds to which concept, especially in a highly technical document.\n\nSections 3 and 4, which seem intended to present the main results, read more like collections of lemmas, theorems, and technical details without adequate discussion or contextualization. This is a significant area for improvement. The results would be far more impactful if they were accompanied by clear explanations and discussions. Theoretical contributions are valuable only if they can be understood and appreciated, and in their current form, the key insights may be difficult for readers to discern.\n\nFinally, the paper would benefit from including plots, diagrams, or simple illustrations that clarify the results. While extensive experimental results may not be expected in a theoretical paper, even a few toy examples or visual aids could significantly enhance reader comprehension and provide concrete illustrations of the theoretical findings.\n\nOverall, with some adjustments to the structure, added explanations, and a few visual aids, this paper could become far more accessible and impactful, allowing a broader audience to appreciate the significance of the work.\n\nWhile the technical content appears sound, I am unable to recommend the paper for acceptance in its current form due to significant organizational issues outlined above. Addressing these concerns would greatly improve the paper’s clarity and accessibility.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "dIEOFRtz5f", "reviewer": "Reviewer_wZk2", "summary": "This paper examines the computational constraints inherent in current LoRA algorithms, focusing particularly on the O(L^2) computational complexity encountered when updating attention blocks. The authors aim to establish a unified upper-bound threshold for these norms, demonstrating that efficient approximation algorithms for LoRA can indeed operate below this threshold. Consequently, they provide proof of the existence of a nearly linear approximation algorithm, advancing the understanding of computational efficiency within the LoRA framework.", "questions": "See the questions in \"weakness\".", "limitations": "", "rating": 3, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "1. Exploring the computational limits of parameter-efficient fine-tuning (PEFT) algorithms is a timely and relevant area of study.\n2. By utilizing the tensor vectorization tricks, the authors prove the existence of nearly linear approximation algorithms for LoRA adaptation.\nNotably, the authors also establish necessary conditions that could inspire the development of more efficient adaptation methods.These conditions are critical for future research aimed at accelerating the approximation process.", "weaknesses": "1.\tCould the authors clarify why Equation 1.2 holds? The expression on the right-hand side appears to minimize the discrepancy between the attention output and the labels Y. Do we only consider 1-layer attention here?\n2.\tThe Strong Exponential Time Hypothesis currently seems to serve only as a counterexample in the context of gradient approximation. Its relevance to the subsequent analysis is unclear in its present form. The reviewer suggests incorporating a more precise and directly relevant statement to clarify its role in the argument.\n3.\tWhile purely theoretical contributions may not always necessitate empirical validation, this paper's objective—improving the efficiency of optimizing large language models (LLMs) with LoRA—suggests that experimental results are essential for substantiating its claims. Specifically, an empirical evaluation could verify whether the bounded gradient approximation indeed holds in practice, as this is critical for the practical applicability of the proposed methods.\n4.\tThe authors assert that 'the existence of low-rank decompositions leads to potential algorithmic speedup.' Could full parameter updating also yield similar benefits? Additionally, how the speedup is related to the rank r?\n5.\tAn alternative approach might involve updating the feed-forward network (FFN) layer rather than the attention block, for example [1][2]. Could this adjustment also avoid/alleviate the O(L^2) computational complexity issue in the paper?\n6.\tThe current title may not fully align with the paper’s objectives, as it does not primarily address computational drawbacks but rather focuses on **solving**  these computational limitations.\n\n[1] AdaptFormer: Adapting Vision Transformers for Scalable Visual Recognition. \n[2] Parameter-Efficient Fine-Tuning with Controls.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "mlBmOynjhT", "reviewer": "Reviewer_D3KJ", "summary": "This work shows the existence of almost linear approximation algorithms for LoRA on transformer-based models. This paper also proves a phase transition behavior in the efficiency of LoRA. A detailed proof sketch is provided in the paper to support the results.", "questions": "1 In lemmas 3.3, 3.4, and 3.5, the amount of time needed to construct the matrices is included. What is the algorithm used for construction here? Why is discussing the required amount of time meaningful since in practice these parameters are learned by gradient methods instead of any construction?\n2 Why do you put the analysis of full LoRA in the appendix instead of in the main body? \n3 What are SAT algorithms in line 142?\n4 Is it $\\frac{\\partial L}{\\partial A_\\mu}$ rather than $\\frac{\\partial L}{\\partial A_Q}$ in line 97?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. As a theoretical work, this work is well-written and not difficult to follow.\n2. The proof idea makes sense and is solid.", "weaknesses": "1 There are two notations that may not be necessary. I suggest considering whether it is possible to remove or simplify some definitions to derive all the lemmas and theorems in the main body.\n2 The practical insights of this paper are not very clear. It is better to highlight the practical significance of the theoretical analysis in the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)