betaFeedback

WorksComputer Science

How Finite-Rank Bottlenecks Shape the Low-Rank Adaptation Landscape

Abstract

Low-rank adaptation (LoRA) has become the standard method for parameter-efficient fine-tuning of large pretrained models, yet theoretical explanations for why low-rank updates suffice remain incomplete. Most existing analyses rely on the Neural Tangent Kernel (NTK) regime, which linearizes the network around the pretrained weights. In this work, we take a different approach that requires no linearization: our key observation is that, once the backbone is frozen, the loss sees each adapted weight matrix only through a finite-rank linear map induced by the frozen activations. Trace-norm regularization then forces the optimizer to pick a low-rank matrix among all matrices that produce the same observed output. This yields global minimizers whose ranks are controlled by the rank of this map, which we call the bottleneck rank, rather than the sample size. For multi-head attention, we obtain tighter rank upper bounds by exploiting two additional invariances: row-wise softmax is insensitive to additive row constants in the score matrix, and value updates are observable only after attention weighting and frozen output projection. For the factorized LoRA objective with weight decay, we prove a complementary result on the nonconvex side: after an arbitrarily small generic positive semidefinite perturbation, every first-order stationary point is rank-deficient once the LoRA rank exceeds a threshold determined by the bottleneck rank. Finally, we show that global minimizers of the perturbed objective are near-optimal for the original trace-norm problem, and we provide uniform generalization bounds governed by the spectral structure of the frozen features.

Introduction

Fine-tuning large pretrained models on downstream tasks is effective but expensive: updating all parameters of a billion-scale model requires substantial memory and compute. Parameter-efficient fine-tuning (PEFT) solves this problem by adapting a large pretrained model while updating only a small subset of parameters. Some of the representative approaches include adapter modules Houlsby et al. [4], prefix tuning Li and Liang (2021), prompt tuning, and low-rank adaptation (LoRA, Hu et al. 2022). Among these, LoRA stands out as an attractive option because it keeps the pretrained backbone frozen and modifies selected linear maps by adding trainable low-rank updates. More formally, for a weight matrix W0∈Rm×nW_0 \in\mathbb{R}^{m \times n}, LoRA parameterizes the adapted weight as

W=W0+T,T=UVT,U∈Rm×r,V∈Rn×r,W = W_0 + T,\qquad T = UV^{\mathsf{T}},\qquad U \in\mathbb{R}^{m \times r}, V \in\mathbb{R}^{n \times r},

The rank rr is typically chosen by the practitioner as a hyperparameter rather than something derived from the fine-tuning objective itself (Hu et al. 2022; Schulman and Lab [18]). A fundamental theoretical question is therefore: When does the regularized fine-tuning objective itself admit a low-rank global minimizer, and what controls the rank?

Most existing theory addresses nearby questions through linearization or simplified training dynamics. In the NTK regime, Jang et al. [8] shows that full fine-tuning admits a low-rank solution and that sufficiently overparameterized LoRA eliminates spurious local minima. Afzal et al. [1] analyze fine-tuning through linearization under an explicit ℓ2\ell_2 bias toward the pretrained model. Beyond classical linearization, Kim et al. [9] study LoRA dynamics and prove a dichotomy between convergence to a low-rank global minimizer and convergence to a qualitatively different high-rank solution. These works are complementary to ours, but they do not answer a more structural question: what property of the objective function makes low-rank optima available in the first place?

Contributions. Our answer starts with a simple observation: once the backbone is frozen, the loss does not observe an adapted matrix TT directly, but only through a finite-rank linear map determined by the frozen activations. Concretely, if H=[h1,…,hN]H = [h_1,\ldots,h_N] is the matrix of frozen input features across the NN training samples, the empirical loss depends on TT only through the product THTH. We call rank⁡(Φ)\operatorname{rank}(\Phi), where Φ(T)=TH\Phi(T)=TH, the bottleneck rank of the adapted block. The same principle applies blockwise to multiple adapted stages and attention heads. Trace-norm regularization then selects a low-rank representative among all matrices that induce the same observed output. This yields exact low-rank existence results without linearizing the network around the pretrained weights. For multi-head attention (Vaswani et al. [19]), the same principle becomes sharper because attention introduces additional invariances: row-wise softmax is unchanged by additive row constants in the score matrix, and value updates are observable only after attention weighting and the frozen output projection.

This workJang et al. [8]Kim et al. [9]
Requires NTK linearizationNoYesNo
Multilayer multi-head attention boundYes (Thm. 4.4)NoNo
Spurious local minima excludedNo (Prop. 4.9)Yes (NTK)Partial
Additional loss assumptionsDifferentiability and stagewise C1C^1 regularityNTK-regime conditionsRestricted strong convexity and smoothness
Generalization boundsYesYesNo

Table 1. Comparison with the closest related theoretical analyses of LoRA.

Our contribution is summarized as follows.

  • Low-rank representer theorem for trace-norm fine-tuning. For a frozen network in which an adapted block TT is observed only through a finite-rank linear map Φ(T)\Phi(T) of bottleneck rank dΦd_{\Phi}, we prove that the trace-norm-regularized problem has a global minimizer whose rank is controlled by dΦd_{\Phi}; see Theorem 4.1. The multi-stage extension is Theorem 4.3.

  • Rank bounds from attention invariances. For multi-head attention, query and key updates are observable only through centered score subspaces because row-wise softmax is invariant to row-wise additive constants. Value updates are observable only after attention weighting and frozen output projection. Combining these invariances with projector compression gives the optimizer-dependent subspace rank bounds in Theorem 4.4.

  • Generic first-order rank deficiency for factorized LoRA. For the weight-decayed LoRA factorization, we prove that after a generic positive semidefinite perturbation, full-column-rank first-order stationary points are excluded whenever the Pataki–Barvinok rank threshold exceeds the dimension of the associated family of symmetric KKT matrices; see Theorem 4.7. The multistage and attention consequences are Theorem C.9 and Corollary 4.8. This is a first-order exclusion theorem, not a no-spurious-local-minima theorem; Proposition 4.9 gives an explicit limitation.

  • Perturbation transfer and generalization. We show that global minimizers of the perturbed factorized objective are near-optimal for the original trace-norm-regularized problem when the perturbation is small; see Theorem 4.10.

Linearized and kernel views of fine-tuning. The closest prior work to ours is Jang et al. [8], which studies LoRA in the NTK regime. Using KoutK_{\mathrm{out}} for the number of output coordinates in the linearized training predictions, their low-rank existence theorem gives a solution satisfying r(r+1)2≤KoutN\frac{r(r+1)}{2} \le K_{\mathrm{out}}N. Thus the rank scale in that analysis is r=⌊8KoutN+1−12⌋r = \left\lfloor\frac{\sqrt{8K_{\mathrm{out}}N+1}-1}{2} \right\rfloor, or r=O(KoutN)r = O(\sqrt{K_{\mathrm{out}}N}) in the scalar-output convention. Our results improve this comparison in two ways. First, our bottleneck reduction is exact for frozen upstream computation and does not linearize the network around the pretrained weights. Second, the optimizer’s rank scale is r≤min⁡{Kout,N}r \le\min\{K_{\mathrm{out}},N\} in Attention, and this is better than Jang et al. [8]’s bound. Afzal et al. [1] also analyzed fine-tuning through linearization under an explicit ℓ2\ell_2 bias toward the pretrained model and quantified when nonlinear fine-tuning stays close to the linearized problem. In contrast, our reduction is exact once upstream computation is frozen; no approximation-by-linearization argument is needed.

Optimization theory beyond linearization. Recent works also study LoRA outside the lazy regime. Kim et al. [9] analyzes the LoRA loss landscape and proves that training converges either to a low-rank global minimizer or to a qualitatively different high-rank solution. Xu et al. (2025) study gradient flow for LoRA in matrix factorization and show how initialization and singular-space alignment shape the final error. Liu et al. [13] compares the landscapes of LoRA, GaLore, and full-rank adaptation through Polyak–Łojasiewicz-type regions and spurious local minima. Zhang and Pilanci [25] analyzes a Riemannian preconditioner for LoRA in the infinite-width setting. These works ask how LoRA training behaves. Our question comes earlier: before one analyzes dynamics, when does the frozen regularized objective itself admit low-rank optima, and when must first-order stationary points of the factored problem be rank-deficient?

Attention and Transformer expressivity. Since transformers are built around attention (Vaswani et al. [19]), we instantiate our framework for Q/K/VQ/K/V projections in attention modules. Orthogonally, a rich literature studies the expressive power and limitations of self-attention and transformers [23, 12, 3, 26]. Complementary work studies what functions low-rank adaptation can represent; Zeng and Lee [24] characterized the expressive power of low-rank adaptation in several settings. For Transformer architectures, Hu et al. (2025) studied computational limitations of LoRA fine-tuning.

Problem setup

We study fine-tuning of a pretrained network in which all weights are frozen except for a specified collection of linear maps. The full notation tables are collected in Appendix § 8; here we introduce only what is needed to state the main results.

Single adapted block. For a frozen weight matrix W0∈Rm×nW_0 \in\mathbb{R}^{m \times n}, we write the adapted weight as W=W0+TW = W_0 + T with update T∈Rm×nT \in\mathbb{R}^{m \times n}. Given training data Sdata={(xi,yi)}i=1NS_{\mathrm{data}} = \{(x_i,y_i)\}_{i=1}^{N}, let hi∈Rnh_i \in\mathbb{R}^{n} denote the frozen input activation at this layer for sample xix_i, and define the frozen feature matrix

H:=[h1,…,hN]∈Rn×N.H := [h_1,\ldots,h_N] \in\mathbb{R}^{n \times N}.

When the input hih_i is independent of the update TT and all other parameters are fixed, the network output on sample xix_i depends on TT only through ThiTh_i (Lemma B.1).

Stacking across samples, the empirical loss depends on TT only through Φ(T):=TH∈Rm×N\Phi(T) := TH \in\mathbb{R}^{m \times N}. The map Φ\Phi is linear, and its range has dimension exactly mrank⁡(H)≤mmin⁡{n,N}m \operatorname{rank}(H) \le m\min\{n,N\}.

Definition 3.1 (Bottleneck rank). For a linear map Φ:Rm×n→E\Phi: \mathbb{R}^{m \times n} \to\mathcal{E} through which the loss observes an adapted block TT, the bottleneck rank is

dΦ:=rank⁡(Φ)=dim⁡R(Φ).d_{\Phi} := \operatorname{rank}(\Phi) = \dim\mathcal{R}(\Phi).

When Φ(T)=TH\Phi(T) = TH as above, we have dΦ=mrank⁡(H)d_{\Phi} = m\operatorname{rank}(H). The bottleneck rank quantifies how much information the frozen network extracts from the update TT: any two updates T,T′T,T' with TH=T′HTH = T'H produce identical training predictions.

Trace-norm regularization and the LoRA factorization. We consider the nuclear-norm-regularized (trace-norm-regularized) objective

min⁡T∈Rm×nLvanilla(T)+λ∥T∥⋆,λ>0,(1)\min_{T\in\mathbb{R}^{m\times n}} \mathcal{L}^{\mathrm{vanilla}}(T) + \lambda\|T\|_{\star}, \qquad\lambda> 0, \tag*{(1)}

where Lvanilla(T)\mathcal{L}^{\mathrm{vanilla}}(T) is the empirical loss with update TT and ∥T∥⋆\|T\|_{\star} denotes the nuclear norm. The factorized LoRA objective with weight decay at rank rr is

Lλlora(U,V):=Lvanilla(UVT)+λ2(∥U∥F2+∥V∥F2),U∈Rm×r, V∈Rn×r.\mathcal{L}_{\lambda}^{\mathrm{lora}}(U,V) := \mathcal{L}^{\mathrm{vanilla}}(UV^{\mathsf{T}}) + \frac{\lambda}{2}\left(\|U\|_{\mathrm{F}}^{2}+\|V\|_{\mathrm{F}}^{2}\right), \qquad U\in\mathbb{R}^{m\times r},\ V\in\mathbb{R}^{n\times r}.

By the standard equivalence between nuclear-norm regularization and balanced weight decay [17], the factorized problem has the same global minimum as (1) restricted to rank ≤r\le r:

min⁡U,VLλlora(U,V)=min⁡T∈Rm×nrank⁡(T)≤r{Lvanilla(T)+λ∥T∥⋆}.\min_{U,V}\mathcal{L}_{\lambda}^{\mathrm{lora}}(U,V)=\min_{\substack{T\in\mathbb{R}^{m\times n}\\ \operatorname{rank}(T)\le r}}\left\{\mathcal{L}^{\mathrm{vanilla}}(T)+\lambda\|T\|_{\star}\right\}.

Thus, whenever the unrestricted trace-norm problem (1) admits a global minimizer of rank ≤r\le r, the rank-rr LoRA factorization incurs no loss of optimality.

Attention mechanism. For multi-head attention with head set A\mathcal{A}, head a∈Aa\in\mathcal{A} produces adapted queries, keys, and values on sample ii:

Q~i(a)=(WQ,0(a)+TQ(a))HQ,i,K~i(a)=(WK,0(a)+TK(a))HK,i,V~i(a)=(WV,0(a)+TV(a))HV,i.\widetilde{Q}_{i}^{(a)}=(W_{Q,0}^{(a)}+T_{Q}^{(a)})H_{Q,i},\qquad\widetilde{K}_{i}^{(a)}=(W_{K,0}^{(a)}+T_{K}^{(a)})H_{K,i},\qquad\widetilde{V}_{i}^{(a)}=(W_{V,0}^{(a)}+T_{V}^{(a)})H_{V,i}.

where HS,iH_{S,i} is the frozen token matrix entering projection S∈{Q,K,V}S\in\{Q,K,V\} for sample ii. Queries and keys share output dimension dkd_k; values have output dimension dvd_v. The attention matrix and block output are

Ai(a)=softmax⁡row((Q~i(a))TK~i(a)dk+CiM),Oi=∑a∈AWO(a)V~i(a)(Ai(a))T.A_{i}^{(a)}=\operatorname{softmax}_{\mathrm{row}}\left(\frac{(\widetilde{Q}_{i}^{(a)})^{\mathsf{T}}\widetilde{K}_{i}^{(a)}}{\sqrt{d_k}}+C_{i}^{M}\right),\qquad O_i=\sum_{a\in\mathcal{A}}W_{O}^{(a)}\widetilde{V}_{i}^{(a)}(A_{i}^{(a)})^{\mathsf{T}}.

where CiMC_i^M is an attention mask and WO(a)W_O^{(a)} is the frozen output-projection block for head aa. We write HS:=[HS,1,…,HS,N]H_S:=[H_{S,1},\ldots,H_{S,N}] for the sample-stacked feature matrices. For sample ii, let ϱQ,i\varrho_{Q,i} and ϱK,i\varrho_{K,i} denote the numbers of query and key token positions, respectively, so that Ai(a)∈RϱQ,i×ϱK,iA_i^{(a)}\in\mathbb{R}^{\varrho_{Q,i}\times\varrho_{K,i}}. In the stage-indexed notation used below, at stage tt, these quantities are written as ϱt,Q,i\varrho_{t,Q,i} and ϱt,K,i\varrho_{t,K,i}.

Multiple adapted layers. When LL consecutive attention modules are adapted (indexed so that larger tt denotes a more upstream stage), the frozen features at stage tt may depend on the updates at stages τ>t\tau>t. This creates a stagewise bottleneck structure, formalized as follows.

References

  1. [1]Afzal, Z. R., Esmaeilbeig, T., Soltanianian, M., and Ohannessian, M. I. (2025). Linearization explains fine-tuning in large language models. In The Thirty-ninth Annual Conference on Neural Information Processing Systems.
  2. [2]Barvinok, A. (2001). A remark on the rank of positive semidefinite matrices subject to affine constraints. Discrete & Computational Geometry, 25(1):23–31.DOI
  3. [3]Hahn, M. (2020). Theoretical limitations of self-attention in neural sequence models. Transactions of the Association for Computational Linguistics, 8:156–171.DOI
  4. [4]Houlsby, N., Giurgiu, A., Jastrzebski, S., Morrone, B., De Laroussilhe, Q., Gesmundo, A., Attarian, M., and Gelly, S. (2019). Parameter-efficient transfer learning for nlp. In International conference on machine learning, pages 2790–2799. PMLR.arxiv.org/abs/1902.00751
  5. [7]Jacot, A., Gabriel, F., and Hongler, C. (2018). Neural tangent kernel: Convergence and generalization in neural networks. Advances in neural information processing systems, 31.arxiv.org/abs/1806.07572
  6. [8]Jang, U., Lee, J. D., and Ryu, E. K. (2024). Lora training in the ntk regime has no spurious local minima. In Proceedings of the 41st International Conference on Machine Learning, pages 21306–21328.arxiv.org/abs/2402.11867
  7. [9]Kim, J., Kim, J., and Ryu, E. K. (2025). Lora training provably converges to a low-rank global minimum or it fails loudly (but it probably won’t fail). In Forty-second International Conference on Machine Learning.arxiv.org/abs/2502.09376
  8. [10]Lee, J., Xiao, L., Schoenholz, S., Bahri, Y., Novak, R., Sohl-Dickstein, J., and Pennington, J. (2019). Wide neural networks often adapt evolve as linear models under gradient descent. Advances in neural information processing systems, 32.DOI
  9. [12]Likhosherstov, V., Choromanski, K., and Weller, A. (2021). On the expressive power of self-attention matrices. arXiv preprint arXiv:2106.03764.arxiv.org/abs/2106.03764
  10. [13]Liu, X.-H., Du, Y., Wang, J., and Yu, Y. (2025). On the optimization landscape of low rank adaptation methods for large language models. In International Conference on Learning Representations. Poster.
  11. [14]Maurer, A. (2016). A vector-contraction inequality for rademacher complexities. In International Conference on Algorithmic Learning Theory, pages 3–17. Springer.arxiv.org/abs/1605.00251
  12. [16]Pataki, G. (1998). On the rank of extreme matrices in semidefinite programs and the multiplicity of optimal eigenvalues. Mathematics of operations research, 23(2):339–358.DOI
  13. [17]Recht, B., Fazel, M., and Parrilo, P. A. (2010). Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM review, 52(3):471–501.
  14. [18]Schulman, J. and Lab, T. M. (2025). Lora without regret. Thinking Machines Lab: Connectionism. https://thinkingmachines.ai/blog/lora/.DOI
  15. [19]Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, Ł., and Polosukhin, I. (2017). Attention is all you need. Advances in neural information processing systems, 30.arxiv.org/abs/1706.03762
  16. [20]Wang, A., Singh, A., Michael, J., Hill, F., Levy, O., and Bowman, S. (2018). Glue: A multi-task benchmark and analysis platform for natural language understanding. In Proceedings of the 2018 EMNLP workshop BlackboxNLP: Analyzing and interpreting neural networks for NLP, pages 353–355.
  17. [22]Yang, A., Li, A., Yang, B., Zhang, B., Hui, B., Zheng, B., Yu, B., Gao, C., Huang, C., Lv, C., et al. (2025). Qwen3 technical report. arXiv preprint arXiv:2505.09388.arxiv.org/abs/2505.09388
  18. [23]Yun, C., Bhojanapalli, S., Rawat, A. S., Reddi, S. J., and Kumar, S. (2020). Are transformers universal approximators of sequence-to-sequence functions? In 8th International Conference on Learning Representations, ICLR 2020.arxiv.org/abs/1912.10077
  19. [24]Zeng, Y. and Lee, K. (2024). The expressive power of low-rank adaptation. In The Twelfth International Conference on Learning Representations.arxiv.org/abs/2310.17513
  20. [25]Zhang, F. and Pilanci, M. (2024). Riemannian preconditioned LoRA for fine-tuning foundation models. In Proceedings of the 41st International Conference on Machine Learning, volume 235 of Proceedings of Machine Learning Research, pages 59641–59669.arxiv.org/abs/2402.02347
  21. [26]Zhou, H., Bradley, A., Littwin, E., Razin, N., Saremi, O., Susskind, J. M., Bengio, S., and Nakkiran, P. (2024). What algorithms can transformers learn? a study in length generalization. In The Twelfth International Conference on Learning Representations.arxiv.org/abs/2310.16028

Paper details

vlnc:W_7svmpdsw
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents