Structured Unrestricted-Rank Matrices for Parameter Efficient Finetuning

Authors: arijit  sehanobish
avinava  dubey
krzysztof  choromanski
somnath  basu
roy  chowdhury
deepali  jain
vikas  sindhwani
snigdha  chaturvedi
google  research
google  deepmind
lowrank  kronecker
circulant  toeplitz
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 01:33:38

Abstract: Recent efforts to scale Transformer models have demonstrated rapid progress across a wide range of tasks (Wei at. al 2022). However, fine-tuning these models for downstream tasks is quite expensive due to their large parameter counts. Parameter-efficient fine-tuning (PEFT) approaches have emerged as a viable alternative, allowing us to fine-tune models by updating only a small number of parameters.
 In this work, we propose a general framework for parameter efficient fine-tuning (PEFT), based on *structured unrestricted-rank matrices* (SURM)  which can serve as a drop-in replacement for popular approaches such as Adapters and LoRA. Unlike other methods like LoRA, SURMs give us more flexibility in finding the right balance between compactness and expressiveness. This is achieved by using *low displacement rank matrices* (LDRMs), which hasn't been used in this context before. SURMs remain competitive with baselines, often providing significant quality improvements while using a smaller parameter budget. SURMs achieve: **5**-**7**% accuracy gains on various image classification tasks while replacing low-rank matrices in LoRA and: up to **12x** reduction of the number of parameters in adapters (with virtually no loss in quality) on the GLUE benchmark.

Main paper: 
 introduction: 
 In recent years, large-scale Transformer models have demonstrated impressive performance across a wide range of domains, including natural language processing (NLP) [20, 8] , vision [36] , robotics [7] , and even multi-modal settings [81] . For many applications, a single large pre-trained model is adapted for several downstream problems. Fine-tuning, where all the model parameters are updated, is a popular way to adapt a pre-trained model to a new task or domain. However, fine-tuning large models on specific downstream tasks requires significant computational resources and involves a massive memory footprint, as each task necessitates storing its own set of parameters.Parameter-efficient fine-tuning (PEFT) methods have emerged as the preferred methodology to adapt pre-trained Transformers to different downstream tasks. PEFT methods often achieve performance on par with full fine-tuning while training only a small number of parameters [80, 45] . PEFT techniques involve either training a small subset of the model's parameters [84, 42] or integrating small modular layers while freezing the base model's weights [26, 25] . There are two popular classes of methods to inject additional parameters: (a) using small modular layers inside Transformers called adapter layers [59] , and (b) constraining the updates as low-rank matrices (LoRA) [26] .Although adapters and LoRA (including their variants) differ architecturally and conceptually, they share a common reliance on low-rank matrices. The success of these methods has been attributed to the low intrinsic dimensionality of the hidden representations in the pre-trained Transformer Figure 1 : Left: Approximating a PSD matrix using a low rank matrix, Kronecker product of matrices, circulant matrix, and Toeplitz matrix. We repeat our experiment 10 times and for each trial, we observe that low rank matrix is the worst approximator followed by Kronecker product, circulant, and Toeplitz. Right: The tradeoff between accuracy and parameter numbers of various PEFT methods. Results are measured across 5 image datasets using CLIP-ViT. Our methods appear in the top right corner (in blue) and achieve the best performance among various strong baseline methods.models [1, 70] . These low-rank methods primarily aim to approximate updates, which, in general, are not low rank. Hence, there's no justification for imposing low-rank constraints on them. Motivated by this insight, we explore alternative classes of matrices-ones that aren't necessarily low rank but are characterized by a linear number of parameters while exhibiting impressive approximations across various matrix classes. We present Fig. 1 as a preview of the motivating results. In Fig. 1 (left), we show that structured matrices (SURM) can approximate any random matrix better than low rank matrices. In Fig. 1 (right), we show that when SURMs are used for parameter efficient fine-tuning it outperforms existing PEFT methods (see more details in Sec. 4 ).We propose a novel paradigm of parameter efficient fine-tuning that leverages Structured Unrestricted-Rank matrices (or SURMs). SURMs provide similar efficiency gains as previous works in efficient fine-tuning, but their more expressive structure paves the way for quality improvements. In this work, we propose to perform parameter-efficient fine-tuning by parameterizing learnable weights as structured matrices. We focus on the two sub-classes of SURMs: (1) Kronecker product of matrices [3] and (2) low displacement rank matrices (LDRMs) [66, 6, 58, 54, 73] . To summarize, our primary contributions are:• We propose the class of Structured Unrestricted-Rank matrices (SURMs) (Section 3), for parameter efficient fine-tuning of Transformers. SURMs include low-rank matrices used in LoRA, as special cases. To the best of our knowledge, we are the first to apply LDRMs in this context. • We demonstrate strong matrix approximation capabilities inherent in Low Displacement Rank Matrices, with a specific focus on circulant and Toeplitz matrices (Section 4). • We introduce a new class of adapter-layers using SURMs, achieving a 12x reduction in parameters compared to adapters, with virtually no loss in quality on the GLUE benchmark (Section 6). • We achieve 5-7% accuracy gains over LoRA on a wide variety of image datasets as well as in low resource setting (VTAB-1k benchmark). In some cases SURMs outperform full fine-tuning, while using only 55k training parameters (as shown in Fig. 1 (right)).Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?Answer: [Yes] Justification: We provide extensive empirical evidence in Section 6 as well additional motivating experiments in Figure 4 Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in the paper. • The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers. • The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper. 
related work: 
 With the introduction of BERT [20] and GPT-2 [8] , Transformer models trained on general text corpora have revolutionized the field of machine learning (ML). Since then, these models have continued to increase in size, with open-source variants adopting various architectures. Examples include encoder-decoder models such as T5 [64] with up to 20B parameters [67] , and a range of auto-regressive decoder models like Llama [69] , Pythia [4] , Mistral [28] , among others, varying in size from a few million to 180B parameters [2] . These models can be easily adapted to downstream tasks by fine-tuning on task-specific data, resulting in state-of-the-art performance across a broad spectrum of downstream tasks. Due to the computational infeasibility of fine-tuning all the parameters of these models, in-context learning [8] and prompt engineering [11, 22] have emerged as attractive alternatives to adapt models to downstream tasks. However, such adaptation results depend heavily on the design of the input prompt and tend to vary greatly with small perturbations of the prompts [48] .Consequently, many works have proposed various PEFT techniques. One of the earliest methods involves inserting the so-called adapter layers between existing layers in a neural network [25, 59 ]. An adapter is typically an MLP with input, output, and a smaller middle layer, encoded by two low-rank matrices, making it compact in terms of parameters. An extension of the adapter is Compacter [51] , which uses Tucker decomposition to parameterize the adapter layers and weight-sharing to reduce the number of trainable parameters. Various modifications and extensions of the above methods have been proposed [53, 24, 32, 52, 65] . Another popular PEFT technique is differentiable prompt-tuning (DPT), which can be thought of as optimizing special tokens in the prompt [88] . However, these methods are limited by the sequence length of the underlying models. Even though DPT was originally developed for NLP, several works have extended it for computer vision tasks as well [83, 12, 27, 24] .One of the most popular PEFT methods is Low-Rank Adaptation (LoRA) [26] , which imposes a low-rank constraint on the weight updates. The main difference between adapters and LoRA is that the learned LoRA weights can be merged with the frozen model weights during inference without adding any latency. Given the popularity of LoRA, there have been many works on extending it to different contexts like long-range modeling [13] , multi-tasking [10] or improving its efficiency [19, 71, 46, 37, 31] among many others.In general, low-rank matrices are studied extensively in various ML applications [57, 87, 44, 61] . The research on low displacement rank matrices (LDRMs) for ML is more narrow [89, 68, 41, 66, 15, 35, 62] . Although Kronecker matrices (a class of LDRMs) have been explored in the context of LDRMs [21, 24, 51] , the constituent matrices in the Kronecker product have low rank even in these work. In this work, we use a fixed parameter budget but do not impose any rank-based condition.To the best of our knowledge, we are the first to systematically explore the effectiveness of different structured matrices and introduce LDRMs for parameter-efficient fine-tuning.The rest of the paper is organized as follows: (a) We introduce the notion of Structured Unrestricted-Rank Matrices (SURM) that are used in this work (Section 3), (b) We motivate the usage of SURM by empirically showing the approximation qualities of these matrices (Section 4), (c) We use SURM as drop-in replacement for popular approaches such as Adapters and LoRA (Section 5), (d) We validate our approach across a wide range of vision and NLP tasks (Section 6).3 Structured Unrestricted-Rank Matrices (SURM)In this section, we will define the matrices that are used for parameter efficient fine-tuning. First, we define the concept of a structured matrix, which is a generic term for a matrix A ∈ R m×n that can be represented by fewer than mn parameters. These matrices are useful because they reduce both space and time complexity when performing matrix multiplications.A simple example of a structured matrix is a low rank matrix of the form W = AB ⊤ ∈ R m×n , where A ∈ R m×r , B ∈ R n×r with r ≪ min(m, n). In this work, our main focus is on those classes of structured matrices that are not restricted to be low-rank, which we refer to as Structured Unrestricted-Rank Matrices (SURM). Next, we present two classes of SURM matrices that we use for parameter efficient fine-tuning.Low Displacement Rank Matrices. Our first class of SURMs is low displacement rank matrices (LDRMs). A matrix W ∈ C m×n is said to have (A, B)-displacement structure if:EQUATIONwhere A ∈ C m×m , B ∈ C n×n , F ∈ C m×n and F has low rank r (as compared to min(m, n)). We call ∇ A,B the displacement rank operator, parameterized by A and B.For a given W, there can exist several pairs of (A, B) matrices satisfying Eq. 1 that produce a lowrank matrix, F. Some examples of such (A, B) pairs include:(Z, Z), (Z, Z ⊤ ), (D x , Z ⊤ ), (D x , D y ) (for x ̸ = y).Here Z is a circulant-shift matrix and D z is a diagonal matrix with nonzero entries equal to z. Low displacement rank matrices (W in Eq. 1) enable fast (sub-quadratic) matrix-vector multiplication and enhance the efficiency of other matrix operations, such as inversion. By selecting more complex (A, B) pairs, such as those involving general Jordan form matrices, it is possible to consider more unstructured W that still have compact representations and support efficient matrix operations [56, 66] . In this paper, we focus on classic low displacement rank matrices: circulant and toeplitz matrices, which are described below. c 0 c n-1 … c 2 c 1 c 1 c 0 c n-1 … c 2 ⋮ c 1 c 0 ⋱ ⋮ c m-2 ⋮ ⋱ ⋱ ⋮ c m-1 c m-2 … … c m a 0 a -1 … … a -(n-1) a 1 a 0 a -1 … ⋮ a 2 a 1 a 0 ⋱ ⋮ ⋮ ⋮ ⋱ ⋱ a -1 a m-1 … … a 1 a 0 a 11 B … a 1n B ⋮ ⋱ ⋮ a m1 B … a mn B (a) Circulant (b) Toeplitz (c) KroneckerQuestion: Does the paper discuss the limitations of the work performed by the authors?Answer: [Yes] Justification: The limitations of our work is detailed in Appendix C.Guidelines:• The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper. • The authors are encouraged to create a separate "Limitations" section in their paper.• The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
theory assumptions and proofs: 
 Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?Answer: [NA] Justification: The paper does not contain any new theoretical results but builds on the main theorem in [66] .Guidelines:• The answer NA means that the paper does not include theoretical results.• All the theorems, formulas, and proofs in the paper should be numbered and crossreferenced. • All assumptions should be clearly stated or referenced in the statement of any theorems.• The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition. • Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material. • Theorems and Lemmas that the proof relies upon should be properly referenced. 
ldr-surms as general approximators: 
 In this section, we motivate the usage of structured unrestricted-rank matrices (SURMs) for parameterefficient fine-tuning. In general, the parameter updates ∆W can be arbitrary matrices, and an effective parameterization of ∆W should be sufficiently expressive to approximate them. Since we use structured update rank matrices (SURMs) to parameterize ∆W, we demonstrate that SURMs can approximate various classes of matrices. Without loss of generality, in this section, we assume that all our matrices have real entries and that weight matrices are square (n = m).First, we recall the result from [66] , which states that a broad class of low displacement rank matrices, as well as linear combinations of Toeplitz (or their inverses) products 2 , can be parameterized as:EQUATIONwhereEQUATION)When f = 1, Z f (v) is a circulant matrix and when f = -1, we refer to Z f (v) as a skew-circulant matrix. Moreover, F can be decomposed as follows:F = GH ⊤ for G = [g 1 , ..., g r ], H = [h 1 , ..., h r ] ∈ R n×r .One can think about rank r of F of controlling how "structured" W is.Figure 3 : A circulant matrix with the first column given by a vector (c 0 , c 1 , c 2 , c 3 , c 4 ) can be re-written as a linear combination of the orthogonal base circulant matrices (5 matrices with orange-entries corresponding to one and other to zero). Such a closed-form decomposition is in general not possible for matrices W(G, H) and thus optimal approximators are found by gradient-descent.From the above result, we see that W(G, H) is the most expressive parameterization among the ones discussed so far. To understand how they fare with SURMs in practice, we evaluate their approximation qualities in two settings: (a) comparing W(G, H) with circulant and Toeplitz matrices, and (b) comparing circulant and Toeplitz matrices with low-rank matrices.We test the approximation capabilities of matrices W(G, H) (Eq. 2) and compare it with popular classes of SURMs: circulant and Toeplitz matrices (Section 3). Specifically, we use these structured matrices to approximate three broad classes of matrices: (a) random, (b) near-low-rank, and (c) nearlow-intrinsic-rank. We denote the ground-truth matrix that we try to approximate as M ∈ R 100×100 and parameterized structured matrix as A (see more details about the setup in Appendix A.7). For all matrices, we obtain the parameters of A using gradient descent on the loss function: ∥A -M∥ Motivated by the results showing that LDRMs with low r can serve as effective approximators, we use circulant and Toeplitz matrices to approximate near-to-low-rank and low-intrinsic-rank matrices.In the three plots shown in Fig. 5 (right column), we observe that approximations using Toeplitz matrices (using twice as many parameters as circulant matrices) offer negligible gains and are only beneficial in the near-low-rank case. For the low-intrinsic case, circulant matrices outperform Toeplitz ones. Overall, circulant matrices with few parameters achieve strong performance in this setting.In this section, we focus on the difference in approximation qualities between low rank matrices and the circulant and Toeplitz matrices under a fixed parameter budget. We use the following settings: Approximating Symmetric Positive Definite Matrices. We use a PSD matrix M ∈ R 50×50 with L 2 -normalized rows in this experiment. We compare the errors to approximate M using circulant, (symmetric) Toeplitz, low-rank matrices, and Kronecker product of two matrices. We use a fixed parameter budget and repeat this experiment 10 times. We report the results in Figure 1 (left). For each of these 10 trials, we observe that the circulant and Toeplitz achieve the lowest error, therefore the best approximation quality (see more details in Appendix A.7).Fitting a Toy Dataset. We create a synthetic pinwheel dataset with 5 spokes as shown in Figure 9 (left). We fit this dataset using a simple neural network with one hidden layer with a matrix W ∈ R 64×64 . In this experiment, we replace W with a rank 1 LoRA, a circulant, a symmetric Toeplitz, and a Toeplitz matrix ( with all parameterizations having the same number of training parameters). In Fig 4) , we report the training loss curves of this experiment. We observe that the LoRA layer struggles to fit the data whereas the LDRMs show similar performance to full fine-tuning (Fig 4 ). These results show the impressive expressive power of these matrices. Therefore, we conclude that LDRMs with particularly low displacement rank serve as good approximators for various matrices. We perform additional experiments and provide more details in Appendix B.Table 1 : ViT-experiments : Baseline numbers are taken from [24] . The best numbers are highlighted in bold and the second-best numbers are underlined. Hyperparameter settings are followed from [24] . We find that SURM consistently outperform very strong baselines with 2-3x reduction in parameters. Motivated by the results from the previous section, we use SURMs as drop-in replacements for various PEFT methods. In this section, we present the integration of SURMs in two popular classes of PEFT methods: LoRA and Adapters.Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?Answer: [Yes] Justification: We provide the hyperparameters to replicate the experiments in Appendix B.1. 
integration of surms in lora: 
 LoRA [26] uses a low rank matrix to parameterize the weight matrix updates. Formally, given a pre-trained weight matrix W, then the updated matrix is W = W + α∆W, where ∆W = AB ⊤ and A ∈ R m×r , B ∈ R n×r for r ≪ min(m, n) and α is a fixed scaling parameter. For efficient training, ∆W needs to be initialized as a zero-matrix. LoRA performs this by choosing initializing A to be the zero matrix and B to be a random matrix. In this work, we propose to parameterize ∆W using structured unrestricted rank matrices. Next, we provide the details of parameterizing ∆W using different SURM matrices (assuming m = n for simplicity).Circulant Matrices. In this setting, we parameterize the updates as:W = C 1 ⊙ C 2 ,where C i ∈ R n×n are circulant matrices encoded using a n-dimensional vector, r i ∈ R n . We use Hadamard products (C 1 ⊙ C 2 ) instead of conventional matrix products as it can be computed efficiently. The construction of Hadamard products which is O(n) is quicker than the process involved in efficient multiplication (which is O(nlog(n)). To enable zero-initialization, we initialize C 1 as a zero-vector and C 2 as a random-vector. Additionally, this approach does not compromise the expressiveness of the network, as the result of the Hadamard product is also a circulant matrix.Toeplitz Matrices. Similar to the previous setting, we use two Toeplitz matrices to parameterize: ∆W = g(T 2 , g(T 1 , x)), where T 1 , T 2 ∈ are Toeplitz matrices, and g is the operator that allows efficient matrix-vector multiplication with Toeplitz matrices (see Appendix A.3 ). Each Toeplitz matrix T ∈ R n×n is parameterized using an n-dimensional vector r encoding its first row and an n-dimensional vector c encoding its first column (2n -1 total parameters). This formulation leads to the 4n -2 trainable parameters. To further reduce this number, we constrain the T 1 , T 2 to be symmetric, reducing the total number of trainable parameters to 2n. To enable zero-initialization, we initialize T 1 as a zero matrix and T 2 is randomly initialized.Kronecker Product of Matrices. In this setting, we parameterize:∆W = A ⊗ B, where A ∈ R r1×r2 , B ∈ R n r 1× n r 2 . The hyperparameters r 1 , r 2 allow us to control the trainable parameter count and the rank of ∆W. In contrast to low-rank matrix updates, we can create matrices ∆W of fairly large ranks while keeping the number of trainable parameters small (see Appendix A.2). To enable zero-initialization, we set A as a zero matrix and B as a random matrix.Table 2 : Results on the VTAB-1k benchmark. Baseline numbers are taken from [30] and [50] . Best numbers are highlighted in bold and the second-best numbers are underlined. We observe that SURM is one of the top-performing PEFT methods on almost all datasets. In all the above settings, it is possible to increase the number of training parameters by relaxing the structure of the matrix, ∆W. This can be performed by introducing more matrices in the product chains, utilizing asymmetric Toeplitz matrices, adjusting the sizes of factors in the Kronecker product, or employing sums of such matrices. Another way to enhance layer expressiveness is by experimenting with combinations of different LDRMs, such as mixing circulant and skew-circulant matrices. A broad class of matrices, including low-rank ones, can be represented as sums of these matrices (see Theorem A.2 and the subsequent discussion).Adapters [25] are small bottleneck networks into Transformer layers as shown below:EQUATION)where σ(•) is a non-linear activation function, X ∈ R b×s×n represents input to the layer (b: batch size, s: sequence length), A ∈ R r×n , B ∈ R n×r are low-rank matrices (r ≪ n) and Y is the output of the layer. For simplicity, layer norms and bias terms are not included in the equation. We use SURMs as a drop-in replacement for matrices A and B. Next, we will provide details of integrating SURMs within the adapter setting. Additional details are provided in Appendix A.5.Circulant Matrices. In this setting, we apply two circulant matrices C 1 , C 2 (encoded by r 1 , r 2 ), resulting in the adapter block:Y = X + σ(f (r 1 ⊙ r 2 , X)) + b,where f is an operator that efficiently computes the matrix multiplication between input X and the circulant matrix encoded by the vector r 1 • r 2 (Appendix A.3). To enable zero-initialization, the vector r 1 is initialized randomly while r 2 and b are initialized as zero vectors.Toeplitz Matrices. In this setting, we use two symmetric Toeplitz matrices T 1 , T 2 , where T 1 and b is initialized as a zero vector and T 2 is initialized randomly. We then define the adapter layer as: Y = X + σ(g(T 1 , g(T 2 , X))) + b, where g is an operator that efficiently computes the matrix multiplication between an input X and a Toeplitz matrix. Figure 7 : Left: Tradeoff between performance and parameter count for various PEFT methods. We report the average results across 5 image datasets using ViT-B (complete results in Table 1 ). Right: Average performance across GLUE benchmark (see complete results in Table 5 ). SURMs appear in the top right corner and perform best among various strong baseline methods in both settings.Kronecker Product of Matrices. In this case, we rewrite Equation 4as: Y = X+σ(X(B⊗A))+b, where B ⊗ A is the Kronecker product. In this case, B is initialized randomly and A and b are initialized by zeros. In all experiments using SURM-adapters, σ(•) is the GeLU non-linearity.• The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors). • It should be clear whether the error bar is the standard deviation or the standard error of the mean. Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 
experiments: 
 In this section, we show the effectiveness of our proposed methods in a wide range of vision and NLP tasks through extensive empirical studies.Image Classification Experiments. We evaluate SURM on several vision datasets: CIFAR10, CIFAR100 [39] , SUN397 [79] , DTD [16] and STL10 [17] . We experiment using ViT-B/16 [36] & Clip-ViT-B/16 [63] as base models and inject trainable parameters Q, K, V matrices in the LoRA setting. We report the results using ViT base are presented in Table 1 (left). We observe that SURM consistently outperforms 12 baseline methods (that use up to 10x parameters). On three out of the five tasks, SURMs emerge as the top performers, surpassing LoRA by a margin of up to 5-7% while achieving competitive performance on the remaining tasks. We report the results using Clip-ViT in Table 1 (right). In this setting, SURM is among the top two methods across all 5 tasks. SURM also uses fewer trainable parameters, reducing them by 3.65x compared to LoRA and 2.4x compared to LoRA-Fix.Low Data Regime. We evaluate SURM in low data regime using VTAB-1k datasets [85] and the ViT model. VTAB-1k is a diverse collection of vision datasets with only 1000 training examples. We focus on the NATURAL and SPECIALIZED subsets of VTAB. In Table 2 , we observe that SURMs are among the top 2 methods on 10 datasets while being competitive on the remaining tasks.We evaluate different variants of SURM and train it on a varying fraction of data on 5 datasets using Clip-ViT model. We report the results in Figure 6 . We observe that the circulant SURM works best in low data regime. Furthermore, SURM achieves the performance of full fine-tuning trained on the entire dataset with only a small fraction of the data. For more challenging datasets like SUN397, we achieve comparable accuracy using approximately 20% of the training data, while for datasets such as CIFAR10 and STL10, only about 2% is needed.Large Data Regime. We perform experiments to show that SURM generalizes well in large data regimes. On ImageNet [18] and iNat2021 [72] , SURM achieves performance comparable to full fine-tuning while using only 0.06% of the training parameters (see detailed results in Appendix B.2).NLP Experiments. We extensively evaluate SURM models on the GLUE benchmark [74] using BERT base [20] . We compare with different adapter baselines and 11 other PEFT techniques. These include full-finetuning, Adapter (Houlsby) and Adapter (Pfeiffer) , among others (we report the corresponding results from [59] ). BiTFit results are taken from [84] (except QQP numbers which are obtained from [9] ) and the numbers for AA-adapters from [53] . Prefix, Serial, AdaMix, UniPELT, Parallel, MAM, and AutoPEFT numbers are taken from [90] . The results for the remaining baselines are replicated by us. More experimental details can be found in Appendix B.For brevity, we summarize the average performance across 8 tasks for SURM-adapters and compare it to 11 baselines, in Fig 7 (right) . We observe that SURM achieve much better performance while using a fraction of the parameters (the complete results are reported in Appendix Table 5 ). We also observe that SURM (integrated into LoRA) outperforms the baseline LoRA, under the same parameter budget. This shows the effectiveness of using structured matrices as a drop-in replacement for low rank matrices used in LoRA. We further analyze the representations learnt by SURMs and LoRAs (Appendix B.4). We find that LoRA learns weights that are very similar to the pre-trained weights whereas SURM is able to explore a larger parameter space (an observation similar to [91] ). Large-scale Experiments. In this setting, we integrate SURMs in LLMs. Specifically, we use matrices of the form W(G, H) (as described in Eqn 2) to increase the number of training parameters. We use the experimental setup introduced in [29] , where the LLM tries to fit a dataset of UUID pairs using the Llama-2-7B model [69] . This was shown to be a challenging task (UUID prediction is significantly different from the pre-training tasks) that requires higher rank values in LoRA. We report the results in Fig. 8 , demonstrating that SURMs is able to fit the data, whereas other methods struggle to do so (see more details in Appendix B.1).Image Segmentation. Next, we focus on the extremely challenging task of medical image segmentation using Synapse multi-organ segmentation dataset [82] . Segment-Anything-Model (SAM) [34] is used as the foundation model for this task. We follow [86] and adapt the Q, V in ViT base image encoder in SAM. Finally, in this low data regime, we use Circulant variant of SURM as it is the best performing variant (Fig. 6 ). We report the Dice similarity coefficient (DSC) metric for each of the 8 organ segmentations and their average (higher is better). For a fair comparison, we include LoRA with rank 1, matching the exact parameter count of Circulant. The results are presented in Table 3 . We report the baseline performance from [86] . SURMs compare favorably with specialized architectures developed for medical imaging like U-Net, Attention U-Net, Transformer-based U-Net, and the Swin U-Net even though they have significantly higher number of training parameters than our method (see details in Appendix B.1). 
conclusion: 
 We introduce structured unrestricted-rank matrices (SURMs) as an alternative to low-rank matrices for the parameter-efficient fine-tuning of large Transformer models. In this setting, structured matrices form the cornerstone of a comprehensive framework, offering a solid base for various parameter efficient fine-tuning methods, such as adapters and LoRA, with enhanced efficiency. SURMs improve the overall effectiveness of PEFT, contributing to its efficient integration into diverse models and domains. Based on extensive numerical experiments and theoretical insights, we conclude that the Circulant variant is our most performing variant (in terms of speed and accuracy). 
author contributions: 
 AS designed the integration of SURM in Adapters and LoRA and ran the GLUE experiments. AD helped in developing the integration and ran all image experiments. KC came up with the idea of using LDRMs in the context of PEFT. SBRC helped in running various large-scale experiments and writing the manuscript. All authors contributed to the writing of this manuscript. 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [Yes] Justification: The broader impacts of our work is detailed in Appendix C.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: We are not releasing any new data or models.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes]Justification: We have cited the authors who created the original data and algorithms that are used in this work.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL.• The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.• If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. • If this information is not available online, the authors are encouraged to reach out to the asset's creators. 13. New Assets Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets? Answer: [Yes] Justification: We release the main code detailing the creation of the SURM layers leveraging fast matrix-vector multiplication and their integration in pretrained Transformers. Guidelines:• The answer NA means that the paper does not release new assets.• Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc. • The paper should discuss whether and how consent was obtained from people whose asset is used. • At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file. 
crowdsourcing and research with human subjects: 
 Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)? Answer: [NA] Justification: The paper does not use any crowd sourcing and human subjects. The multiorgan segmentation downloaded from synapse and we adhere to the rules of the usage of this data. Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects. • Including this information in the supplemental material is fine, but if the main contribution of the paper involves human subjects, then as much detail as possible should be included in the main paper. • According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector. 
institutional review board (irb) approvals or equivalent for research with human subjects: 
 Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained? Answer: [NA] Justification: We do not IRB approval for the use of the multi-organ segmentation dataset. This can be freely downloaded from the internet once one signs up on synpase. We strictly adhere to the rules of the usage of data. Guidelines:• The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.• Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: In this section, we discuss the details of various algorithms and workflows within SURM. In this section, we introduce another type of structured matrix that is characterized by a linear number of parameters. Definition A.1 (Skew-Circulant). A matrix S = (s jk ) n-1 j,k=0 is said to be skew-circulant ifs jk = s j-k and s -l = -s n-l for 1 ≤ l ≤ n -1.This matrix can be represented visually as shown below:EQUATIONThis matrix is parameterized by a linear number of parameters and also enjoy sub-quadratic time complexity matrix-vector multiplications (see Appendix A.3).Let W be a d × d matrix that can be written asW = A ⊗ B, where A ∈ R m1×n1 , B ∈ R m2×n2 .We want to minimize the following objective:EQUATION)We can rewrite the above as : m 1 = d/m 2 and n 1 = d/n 2 . Plugging these back in Eq. 6, we get:EQUATION)The equality is obtained when . Thus, for our experiments with BERT and ViT models, we take A to be a matrix of size 32 × 24 and B to be of size 24 × 32. This choice of matrix shapes allows us to substantially reduce the computational complexity of matrix-vector multiplication (see Section A.3).√ m 2 n 2 = d/ √ m 2 n 2 ,One of our main advantages of using structured matrices is that they allow for sub-quadratic vectormatrix multiplications. Matrix vector multiplication by a circulant matrix can be efficiently done via FFT in O(n log n) time. This is done by the following steps : (a) take the FFT of the input vector v and the vector representation of the circulant matrix c, and call them V and C respectively. (b) Take the inverse Fourier transform of the Hadamard (element-wise) product of V and C.For the sake of convenience, let us define this efficient multiplication operator to be f . The key insight behind this approach is that the circular convolution in the time domain corresponds to element-wise multiplication in the frequency domain after FFT. By leveraging FFT, the time complexity of the multiplication is reduced from O(n 2 ) to O(n log n).The same ideas extend to the case of Toeplitz matrices, where one can embed the Toeplitz matrix into a circulant matrix and use FFT as before for efficient matrix-vector multiplication. For ease of reference, let us call the function g that embeds the Toeplitz matrix into a circulant matrix and use the function f as described above to compute the matrix-vector product.Next, we describe how vector multiplication by skew-circulant matrices can be efficiently performed in O(n log n) time. If the skew-circulant matrix S is parameterized by the vector v, then the multiplication is given byEQUATIONwhereη = [1, η, η 2 , • • • η n-1 ], and η = (-1)1 n = exp(iπ/n), the root of negative unity. For the case of a matrix W = AB, where W ∈ R m×n , A ∈ R m×r and B ∈ R r×n , then multiplication by v takes O(r(m + n)) and one gets computation gains when r ≪ min{m, n}. Finally, for a Hadamard product of matricesA ∈ R r1×r2 , B ∈ R k1×k2 , v ∈ R r2k2 , (A ⊗ B)v = vec(Br(v) ⊤ A ⊤ ), where vec(•) is the vectorization operator that takes a matrix M ∈ R m×n and converts it to R mn×1 column vector by stacking the columns of M on top of each other and r is the PyTorch style reshape operator that reshapes the vector v to a matrix of shape r 2 × k 2 . Choosing max{r i , k i } ≪ r i k i , for i = 1, 2, one can substantially reduce the computational complexity.In this section, we explain an elegant way to increase the number of training parameters. We use the sum of product of circulant and skew-circulant matrices of the formEQUATION)where A i and B i is a circulant and a skew-circulant matrix respectively. Each factor of M has 2n parameters thus M has 2nr parameters.The class of n × n matrices M which can be written via Equation 9 is rich and contains many important classes of matrices. Theorem A.2 (Expressivity). The set of matrices M which can be written as in Equation 9 contains:• All n × n Circulant and Skew-Circulant matrices for r ≥ 1• All n × n Toeplitz and Inverses of Toeplitz matrices for r ≥ 2.• All n × n matrices for r = n.• All linear combinations of the formp j=1 β i A (j) 1 • • • A (j)t where r ≥ 2tp, and A is either a Toeplitz or the inverse of a Toeplitz matrix. This is Theorem 3.1 in [66] . Efficient multiplication by matrices of this form can be done in sub-quadratic time by simply combining the results from Sec A.3.Moreover, we note that by choosing a slightly different parameterization of displacement operators, one can obtain low rank matrices and orthogonal polynomial transforms, including the Discrete Fourier and Cosine Transforms (see Proposition 2 in [68] ).Thus our framework encompasses many important classes of matrices including low rank matrices and thus generalizes LoRA.In this section, we provide additional details about SURMintegration in Adapters.For simplicity, we follow the Houlsby configuration [25] , but our work is also readily applicable in Pfeiffer configuration as well [59] . Recall the definition of Adapter layers:EQUATION)where σ(•) is a non-linear activation function applied point-wise, X ∈ R b×s×n represents input to the layer (b is the batch size and s is the sequence length), A ∈ R r×n , B ∈ R n×r are two low-rank matrices (r ≪ n) and Y is the output of the layer. Similar to LoRA, matrix B is initialized randomly, whereas A is initialized as a zero-matrix. For convenience, layer norms and bias terms are not included in the equation.SURMs can be used in place of low rank A and B. The integration and design choices of various LDRs in this setting mimic that of LoRA.Circulant Matrices. Similar to the LoRA setting, we apply two circulant matrices C 1 , C 2 , resulting in the following equation of the adapter block:EQUATIONwhere f is an operator multiplying input matrix X with the circulant matrix obtained by multiplying two circulant matrices encoded by r 1 and r 2 (Appendix A.3). The vector r 1 is initialized randomly while r 2 and b are initialized as zero vectors. Note that we apply the non-linearity after we multiply X with both the circulant matrices. This may hurt the expressiveness of the network but improves computational complexity. Moreover, we only need to save one vector defining the first row of a circulant matrix and not both: r 1 and r 2 . This results in lower storage costs and faster deployment. This design choice works well in practice as evidenced from the results on the GLUE benchmark (see Table 5 ).Toeplitz Matrices. Similar to the case of Toeplitz matrices within LoRA, we use two symmetric Toeplitz matrices T 1 , T 2 , where T 1 and b is initialized as a zero vector and T 2 is initialized randomly. We then define the adapter layer to be:EQUATION)The position of the non-linear mapping σ is chosen such that we can merge the two trained matrices resulting in smaller storage costs and fast deployment.Finally, note that the Toeplitz variant is slower than the circulant variant, as it requires two applications of the fast matrix-vector operator, whereas the circulant variant requires only one.In this section, we show how we can approximate any matrix D ∈ R n×n using Circulant, Toeplitz matrices, and symmetric Toeplitz matrices. We note that each class of structured matrices forms a vector space. Therefore, finding the closest point in the appropriate subspace becomes a convex optimization problem and is given by the orthogonal projection onto the basis vectors of the subspace. More explicitly, if {e 1 , • • • , e n } are a set of orthogonal vectors spanning a subspace W, then the closest vector to v in W is given byEQUATION)The space of circulant matrices has dim n, so spanned by the orthogonal set{(1, • • • , • • • 0), (0, • • • 1, • • • 0), (0, • • • , • • • 1)}.Using the above formula, one can write down a simplified expression of the circulant matrix asĈ := ( ĉ1 , • • • ĉn ) that approximates D ĉ1 = 1 n n j=1 d jj , ĉk = 1 n    k-1 j=1 d j(1+j+n-k) + n j=k d j(j-k+1)   , where k = {2, . . . , n}.Note that the same set as before spans the space of symmetric Toeplitz matrices. This yields a compact formula for the approximating Toeplitz matrix:T := 1 n n i=1 a i,i I n + 1 n -1 n-1 i=1 a i,i+1 M 2 + 1 n -2 n-2 i=1 a i,i+2 M 3 + • • • + a 1,n M n ,where M i is the symmetric Toeplitz matrix generated by the i-th element in the set above. Finally the set {((1, 0,• • • , 0), (0, • • • , 0)), • • • ((0, • • • , 1, • • • , 0), (0, • • • , 0)), ((0, • • • , 0), (0, • • • , 1, • • • , 0) } spans allToeplitz matrices where the first element in each tuple denotes the first row and the second element the first column. Note that since the a 1 1 entry is shared by both first row and column we treat the first vector as n-dimensional vector and the second as n -1 dimensional vector. Thus the dimension of the space is 2n -1. Using FFT and the projection formula, one can compute the approximation by a Toeplitz matrix.In this section, we present additional details on the various experiments on approximation by LDR matrices presented in Section 4.1.• Random: The first class, with entries taken independently at random from N (0, 1), represents a completely unstructured family.• Near-low rank: Each matrix from the second class was chosen from the distribution: GH ⊤ + ϵR, where G, H ∈ R n×r for r ≪ n, R ∈ R n×n , ϵ = 0.05, and the entries of G, H, R are taken independently at random from N (0, 1).• Near-low intrinsic rank: Matrices from the third class are constructed as follows. First we sample: t 0 , ..., t n-1 iid ∼ N (0, 1). The i-th row of the resulting matrix is of the form: (sin(1• t i ), sin(2 • t i ), ..., sin(n • t i )) + g i ,wheare either all g i are zero-vectors or they are taken independently at random from ϵ * N (0, I n ). Note that even though that matrix is not necessarily low-rank, it is taken from the vicinity of the n-dimensional manifold, since it is fully determined by the sampled tuple (t 0 , ..., t n-1 ). Matrices from all the classes are taken from R 100×100 .Optimizing Circulant and Toeplitz Matrices. In general, an optimal approximation (e.g. with respect to the Frobenius norm as a distance) of a given matrix by a matrix W(G, H) is not given by the closed-form expression. Thus we will thus construct good-quality approximators via gradientbased optimization (see: Sec. 4.1).Experiments in Section 4.2. Now we provide additional details on the experiments that explicitly compare LDRMs with low-rank matrices. For these experiments, we construct a PSD matrices M ∈ R 50×50 with L 2 normalized rows. We fix a parameter budget of n = 50. The low-rank approximation, in that case, becomes an outer product by a vector v. For the Kronecker product, we choose a factor A ∈ R 10×5 . To maintain the parameter budget, the other factor becomes A ⊤ . If M is the approximating matrix, then we define error = || M -M|| F , where || • || F is the Frobenius norm.We use the closed-form formula for the optimal circulant and symmetric Toeplitz matrices approximating M and use gradient descent to find the optimal low-rank matrix and Kronecker product of matrices. We use a learning rate of 0.1 while computing the optimal low-rank matrix and the Kronecker product of matrices.Inverses of Toeplitz matrices can be effectively found [40] . We recall the celebrated result of Gohberg and Semencul. Theorem A.3. Let A := (a p-q ) n p,q=1 be a Toeplitz matrix. If the following systems of equations n q=1 a p-q x q = δ p,1 , n q=1 a p-q y q = δ p,n , where p = {1, 2 . . . n} is solvable and x 1 ̸ = 0, then A is invertible. Results of fitting the pinwheel dataset using regular training, where all network parameters are trained. A network with a low-rank hidden layer matrix struggles to fit the data, while those with SURMmatrices achieve a successful fit.In our case, we consider only symmetric Toeplitz matrices. Thus the above equation really boils down to solving the first system of equations as the next system can be solved by using the first, i.e. by settingx n-i+1 = y i i = 1, 2, • • • n.The first system of equations can be efficiently solved by Gaussian elimination. For the SURM methods, we follow the same setting as applying the adaptation to only the attention layers. The number of factors of W(G, H) is chosen to be 4 (i.e. same number of parameters as a rank 4 matrix). This experiment also highlights that for effective transfer learning LoRA needs to be applied to all linear layers (which is well-known in the LLM community). In Fig. 8 , we observe that LoRA and MoRA struggles to fit the data whereas our method converges. ). We use the Segment-Anything-Model (SAM) [34] as the foundation model for this task. There has been a number of works in adapting various PEFT methods to fine tuning SAM. We follow the training details in [86] . More specifically, we adapt the Q, V in ViT-B image encoder in the SAM and normally finetune the small decoder head. Finally, in this small data regime, we use the Circulant variant as it is our most performant variant in this case (see Fig. 6 ). We report the Dice similarity coefficient (DSC) metric for each of the 8 organ segmentation as well as the average DSC score for all (higher is better). The SAMed model uses a LoRA rank 4 in Q, V. For a fair comparison, we include LoRA rank 1, matching the exact parameter count of Circulant. We use an A100 40GB GPU for this experiment.In this section, we provide additional experiments to showcase the efficacy of SURMs.Experiments on Large Scale Data Next, we conduct additional experiments on the ImageNet-1k dataset [18] . The goal is to show how our methods can scale up to extremely large datasets. We observe that SURM achieves comparable performance to other PEFT methods and even achieving comparable performance to the full fine-tuning results (see Table 6 ).We further evaluate the performance of SURM in a large-scale setting using the iNat2021 dataset [72] , which contains over 2.7 million training images, 100K validation images, and 500K test images, spanning 10, 000 species (classes). Fine-tuning a ViT model on this dataset achieves an accuracy of 69.98%, while SURM (circulant) achieves 69.01%. Notably, our method requires only 55K parameters, compared to 86M for full fine-tuning, demonstrating its efficiency in parameter usage while maintaining comparable accuracy.Ablation Experiments. Here, we show the effect of various design choices. Figure 10 illustrates the impact of incorporating the bias term in our adapters. Bias term provides a boost across all tasks and the adapters, the boost being smaller on the Kronecker adapter. Without the bias terms, the sizes of the adapters are around .04M, providing an even lightweight but still capable method. Therefore, if there are concerns regarding storage and latency, opting for adapters without bias is a viable option. Moreover, we show the effect on only adapting Q, V instead of Q, K, V as shown in the main paper. Table 7 shows that on GLUE tasks, there is a minimal effect for not adapting the K matrix.As mentioned earlier, adaptation using Kronecker product is not new and has been investigated in several works [51, 21, 24] . In both [51] and [24] , the authors use the Kronecker decomposition of the weight matrix (in the first case, the weight matrix belongs to an adapter layer and in the second case the weight matrix refers to updates as in the case of LoRA). Write W = n i=1 A i ⊗ B i . Furthermore, the authors assume that B i is low rank and can be written asB i := u ij v ⊤ ij .The weights A i can also be assumed to low weights or be shared among various layers leading to substantial efficiency gains. Our method is a simplified version of the above where n = 1. Other main difference between the above methods and ours are : the matrices considered in the above works are square matrices whereas they are almost never square unless the dimension of the transformer is a perfect square and is set up such that the number of parameters are reduced while the rank is as high as possible, contrary to the above. Similar considerations of low rank factors in tensor decomposition are also used in [30] . Our Kronecker adaptation is same as that of [21] in the LoRA setting. In the adapter setting, our implementation follows closely the Houlsby architecture and is a little different than that of [21] . Thus, we implement the Kronecker adaptation in both LoRA and adapter settings and showcase its versatility across both vision and language. Moreover, we present this approach as an example of a principled approach to tackle the problem of PEFT.In this section, we analyze the weights of various fine-tuned models. Even though prior works have found the updates of the weight matrices to have low intrinsic dimension [1] (ID), the updates themselves are of high rank. This is confirmed by looking at the fine-tuned BERT models on various GLUE tasks as well as ViT models fine-tuned on CIFAR10, CIFAR100, and ImageNet. Moreover, we simulate a high-rank LoRA setting on GLUE where we freeze all the weights excepts except for Q, K, V. In that scenario, we manage to replicate the full fine-tuning performance using fewer training epochs than that of LoRA. A quick analysis of the updates reveal that they have full rank.Many works have delved into intrinsic dimensionality for well-known image classification datasets [60] . These works show that the images have low intrinsic dimensionality compared to the pixel spaces but the dimensionality increases when augmentations like Gaussian noise is added. Recent work [49] studies the intrinsic dimensions of various self-supervised image models.Comparing their results with that of fully supervised ViT models, we observe that the self-supervised models exhibit slightly higher IDs. This is not surprising as the SSL encourages the representations to be spread over an unit hyper sphere. Thus, we believe that various low rank adaptations may fail in situations where the IDs might be high (in case of OOD data) [75] .Encouraged by this analysis, we next investigate the trained weights emerging from our methods. We observe that they have high rank across all vision and text tasks and various fine-tuning strategies. The largest possible rank of the Kronecker matrices considered in this work is 576 and all of our trained matrices are of rank 576. For rational circulant matrices C, the non-singularity of such matrices is related to divisibility by cyclotomic polynomials. More generally, if we denote by c = (c 0 , ..c n-1 ) the first column of C, then: and i 2 = -1 (for more details see [14] ). This fact allows us to efficiently test for the non-singularity of the circulant matrices. In all our cases, we found our matrices to be nonsingular. Regarding Toeplitz matrices, there is a large body of literature that discusses the inversion of such matrices (see Appendix A.8). Using the methods discussed above, we find that the Toeplitz adaptations are invertible, thus full-rank. Therefore, we hypothesize that the high rank compensates for the deficiency of training parameters.det(C) = n-1 j=0 c 0 + c 1 ω j + c 2 ω 2 j + • • • c n-1 ω n-1 j ,To further explore the differences between the parameters learned by LoRA vs. that learned by SURM methods we performed another set of experiments. We calculate the cosine similarity between the weights learned by the PEFT methods ( Ŵ = W + α∆W) and W (pre-trained weights). A smaller cosine similarity would tell us that SURMs help us in exploring parameters further away from the pre-trained weights (W).We test our hypothesis on the BERT model finetuned on the MRPC dataset by SURMas well as by LoRA. We report the (1-cosine similarity( Ŵ, W)) for both query and key across multiple layers (see Fig 11) . We see that LoRA-learnt weights are very similar to the pretrained weights whereas SURMs explore a larger space (as shown by higher dissimilarity). This observation is not too dissimilar to that of [91] .Analysis of trained weight matrices for Pinwheel data. We also want to answer the question: Q: How similar are the representations learned by networks with the SURM layers compared to the full finetuned networks?We evaluate the CKA similarity [38] between the full fine-tuned network and the network with the LDR layers. CKA is a widely used metric to compare representations coming from different neural networks. We observe that LDR networks have higher CKA similarity with fully finetuned networks than their LoRA counterparts.To translate our framework into actionable insights, we aim to highlight several key properties of the various classes of SURMs that help us in making the final recommendation. In all our experiments, we found that on average that circulant variant achieves the largest number of best performances across multiple datasets (Figure 1 , Table 1 , 2, 3). Moreover, in the low data regime, it is clear that the circulant is the most performant variant as well (Figure 6 ).The time complexity of LDR matrices is sub-quadratic, in particular, time complexity for both: the circulant and the Toeplitz variant is the same but the Toeplitz one is slower by a factor of 2. The gradients allow for a very simple formula, which is computed in sub-quadratic time (see eq 14 in [15] for the circulant matrix and Proposition 3.6 in [66] for the Toeplitz matrix). Therefore, our general recommendation to practitioners is to use the circulant variant of SURM. It is relatively fast and our most accurate variant.Fine-tuning large pre-trained Transformers for downstream tasks requires substantial computational resources. We hope that this work addresses this important problem by reducing the overall computational budget while maintaining high accuracy. We believe that SURMs will make Transformers accessible to researchers and academics world wide and also reduce the carbon footprint associated with training these models. While democratizing powerful Transformers' technologies with those methods, one must still be cautious of the potential harmful biases, inherent to models pre-trained on the internet-scale data. One of the main limitations is the absence of custom kernels for our methods. Despite their theoretical speed advantage, popular methods like LoRA have been extensively optimized by the machine learning community for efficient execution on hardware.• The answer NA means that the paper does not include experiments.• If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not. • If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable. • Depending on the contribution, reproducibility can be accomplished in various ways.For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. , with an open-source dataset or instructions for how to construct the dataset). (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.M1 • ... • Mt for r ≥ 2t and where each Mi is a Toeplitz matrix or its inverse.Please note that for circulant and Toeplitz matrices, it is also possible to obtain a closed-form solution for the matrix (seeFig 3 & Appendix A.6). 


Decision: The paper proposes a general framework for parameter-efficient fine-tuning, based on structured unrestricted-rank matrices (SURMs) to substitute LoRA or other parameter-efficient finetuning methods. 

Three variants of SURMs are included, named Kronecker, Toeplitz, and Circulant, based on the matrix type. The use of Circulant and Toeplitz structures in adaptors is novel.

The extensive experiments show that the SURM method generally achieves performance comparable with LoRA/adaptors with 50% or less parameters on vision datasets like CIFAR10, SUN397, and DTD. SURM can also be incorporated into adaptors.

The rebuttal includes results on larger LLM models such as LLaMa-2 7B, where existing methods such as LoRA struggle, while SURM does better, by allowing higher ranks without higher computational load.

The bibliography is poorly constructed and needs to be fixed. Many of the entries are missing information, such as journal or conference name, or even arxiv numbers.

The authors will have a challenge to fit in all the new material (e.g. the results on the LLaMa experiments) into the final version if accepted.

The low-rank adaptors and approximations space is becoming very crowded and hard for new methods to stand out as significant contributions. This is the case for this paper. While the contribution is clear, and makes a good addition to the current PEFT methods, it might not stand out as particularly exciting in comparison with other accepted papers. Hence it is suited more for a poster or spotlight than an oral talk.

Reviews: review: paper_summary: paper_summary: This paper explores structured unrestricted-rank matrices (SURM) for parameter-efficient fine-tuning (PEFT) of large-scale Transformer models. This method (SURM) was the first to apply low displacement rank matrices (LDRM) which could support fast matrix-vector multiplication and showed flexibility in finding a balance between compactness and expressiveness. What they used were Circulant, Toeplitz (LDRM), also Kronecker matrix (not LDRM). The authors demonstrated improved accuracy in various data sets while replacing low-rank matrices in LoRA and showed a reduction in the number of parameters in the adapter.
strength_weakness: strength_weakness: 1. Any reasons why the proposed version w/ the Kronecker product outperforms the previous works, such as Kadaptation?

2. Why is PSD approximation accuracy a good proxy task? is the weight delta during finetuning close to PSD by any chance?

3. As the author mentioned in the limitation section, there are many fancy accelerated implementations of LoRA. How slow is the proposed method compared to those LoRA implementations?
questions: questions: see the weakness section.
limitations: limitations: I do not see any serious societal impact of the paper.
paper_summary: paper_summary: The paper proposed a general framework for parameter-efficient fine-tuning, based on structured unrestricted-rank matrices (SURMs) to substitute LoRA or other parameter-efficient finetuning methods. Three variants of SURMs are included, named Kronecker, Toeplitz, and Circulant, based on the matrix type. The proposed SURM method generally achieves performance comparable with LoRA/adaptors with 50% or less parameters on vision datasets like CIFAR10, SUN397, and DTD. SURM can also be incorporated into adaptors.
strength_weakness: strength_weakness: 1. The tasks include GLUE benchmarks, but the improvements are not convincing. Most of the tasks are in trade-off with other methods. Why not increase the trainable parameter up to the same level as other methods, for example, 0.9, to examine the upper bound performance? This could be part of the ablation studies, showing the scaling relationship between the performance and trainable parameters.
2. Experiments conducted in NLP should contain new architectures, such as LLaMa.
questions: questions: Please see the weaknesses.
limitations: limitations: N/A
paper_summary: paper_summary: The paper introduces a new technique called SURMs which aim to use structured matrices for PEFT. The technique is tested against many different adapter variants in Vision Adaptation and Natural Language. The unique structure of the matrices allow for efficient computation of the products
strength_weakness: strength_weakness: The bar for a new variant of LoRA to be substantial contribution to me is fairly high, just due to how crowded the space is.

Structured matrices for low rank adaptation has previously, as noted in the paper Knoecker products have been in previous literature, while Circulant and Toeplitz structures are, to my knowledge, have not. Nevertheless, Structured matrix adaptation has been explored in several prior papers.

The change in structure of the matrix or rank alone to me is not sufficient unless there is substantial evidence it provides benefit, both empirically and intuitively/theoretically.

The intuition and/or theory as why we might expect this class of matrices to be a useful, in terms of improved adaptation, is lacking (beyond the FFT-based efficiency). As stated previously, the space is fairly crowded for this line of research and every new modification cannot be considered significant without substantial evidence and careful reasoning behind exploration.

The empirical evidence for this change also needs to be improved upon. 
PEFT experiments need to largely be conducted in regimes where full-finetuning represents a soft upper bound on the achievable performance. The most common use case for PEFT techniques is improving finetuning compute/memory efficiency, while retaining as much performance as possible. In contrast, for regimes where we don't have sufficient data for full fine-tuning to perform best, it seems that we mainly end up measuring the ability of the technique to reduce overfitting, rather than the techniques ability to retain the learning capacity of the original model at lower compute levels. This is still useful, of course, but there are many other techniques to do this outside of PEFT, and it misses evaluation for the primary use case of PEFT.

As a reference, I think the [MoRa](https://arxiv.org/pdf/2405.12130) paper does a decent job at this. The original LoRA paper doesn't do a great job with this and oversells, as the community knows from countless experiments with it. To effectively prove out which techniques hold up best its very important to conduct detailed evaluations at scale with models which can achieve SoTA on a particular dataset.

The following would make the paper much stronger:
- Stronger intuitive/theoretical justification for why we might expect this class of adaptations to perform better (with some small scale experiments or ablations proving the intuition)

- Experiments with models in NLP and Vision, where we full finetuning generally performs best (the UUID memorization from MoRa is a good example). Imagenet seems like a good candidate assuming techniques have not pertained on that data. Larger NLP datasets seem like another good candidate (extra AR pretraining, adaptation to larger downstream tasks).

From my perspective, if I actually wanted to train on the the many of the small vision datasets for example, there are many different alternate fine-tuning techniques or different models I can use to improve performance for data-starved cases, especially since those cited perform worse than other fine-tuning techniques on these datasets. (Cifar-100, DTD, SUN for example, even using the same model arches). 

The paper needs to do a more careful job of picking SoTA finetunings on larger datasets and using PEFT on those.

**Only PEFT can really target the case where I have large amount of fine-tuning data, but not necessarily the compute/memory to target it with a very large model well, so this regime should be emphasized in the experiments.**
questions: questions: What are the ranks of the other adapters used?

Why do you only test against rank 1 lora in Table 3?

What how does the techniques performance change with rank?

Why might we expect these structures to perform better than other structured matrices?
limitations: limitations: The paper should address limitations more directly
paper_summary: paper_summary: The paper explores the use of structured matrices instead of low-rank matrices for approximating the finetuning updates for Transformer models. The sturcture imposed on the approximation matrices determines the number of trainable parameters. The paper explores use of two structured matrices: Circulant and Toeplitz matrices, and Kronecker product of Matrices for finetuning language models and vision models. The paper shows that structured matrices are better at approximating various class of matrices like random (full rank), near-low-rank and near-low-intrinsic-rank than low-rank matrices, and this translates to better performance when using them for finetuning at a lower parameter cost.
strength_weakness: strength_weakness: 1. **No studies on more difficult tasks**:
- While I understand that the authors have shown the effectiveness of the proposed method on smaller models, it would be interesting to see how the proposed method performs on larger models for more difficult tasks like language generation (for e.g., insturction tuning) or math/commonsense reasoning which are commonly used to study PEFT methods on large language models.
2. **Lack of details on choice of hyperparameters**:
- The paper does not provide sufficient details about how the data is split, if all the methods are compared by training and evaluating on the same data splits.
- Moreover, the paper does not provide details on how the hyperparameters are chosen, but only the final values are mentioned. (Section E in the appendix.)
3. **Minor presentation details**:
- Figure 1: caption says the presented methods are in top left (in green), but appear to be in the top right in the plots, and also do not apprear to be in green.
questions: questions: 1. **Section 4.1**:
- What is the significance of Section 4.1? What does the comparison between Circulant and Toeplitz matrices with W(G,H) convey? Could the authors provide more explanation about why this comparison is done, especially since the final PEFT algorithm uses only Circulant and Toeplitz matrices?
- Do all the methods in this study approximate the exact same matrix? Why do the initial errors vary by such a large margin across W(G,H), and Circular and Toeplits matrices?
- Why do Circulant and Toeplitz matrices use more iterations than W(G,H) (200 vs. 2000)? If the number of iterations is the same (i.e., W(G,H) is optimized for 2000 iterations), do the results change?
- Why is there no study for approximation of random matrix using Toeplitz Circular matrices?
- Why is low-rank(I=20) + epsilon not considered for Circular and Toeplitz matrices?

2. **Experiments on image classification using ViTs**:
- What is the pretraining data and task for the base ViT?
- How is the data split into train, validation and test splits, and on which split is are the results reported?
- How and on which split are the hyperparameters tuned? Section E, lines 699-700 mention that the experiments use a learning rate of 5e-5, but SVHN uses 5e-4. How is this chosen?

3. **Experiments on GLUE**:
- What is the difference bewteen SURM (Circular) and SURM (Circular-LoRA/Adapter) (similarly Toeplitz and Kronecker)?
limitations: limitations: Authors have addressed the limitations.

Comments: title: full rank vs PSD?
Thanks for Response
Thank you for your feedback
Recommend Acceptance
Larger Scale
comment: Dear Reviewer Kv7A, 

Thank you for the excellent question. 

The difference between our results and that reported in MoRA [1] arises because the authors in [1] use LoRA in **all** linear layers whereas we only use it in $Q, K, V$. We aim to show that in this low-parameter regime, LoRA and MoRA struggle to fit the data whereas SURM excels in this task. 

The cross-entropy training loss is a valid metric for this task and was reported in Fig. 2 in the original paper [1]. We found that the generation quality depends quite a lot on the hyperparameters (which are not open-sourced yet) and couldn’t exactly replicate the results presented in [1]. Therefore, for a fair comparison, we report the convergence of the training loss for all methods.


[1] MoRA: High-Rank Updating for Parameter-Efficient Fine-Tuning Jiang et al. 2024
Thank you for the question. 

Our goal is to show the approximation capabilities of SURM over a wide class of matrices. We compared SURMs capabilities to full rank random matrices in Fig 4 (top left). The next class we explored is Positive Definite matrices, which have full rank and some structure. It’s worth noting that trained neural network weights also exhibit certain structural patterns [4, 5].


In general, (Symmetric) Positive Definite (SPD) matrices are important in various applications in ML like convex optimization and kernel learning.  SPD-NN is widely used in Riemannian optimization [1], manifold learning [2], and CNNs [3] among others. Given the extensive literature on the use of SPD matrices in machine learning, they provide an ideal test case to evaluate the approximation quality of SURM.

[1] Riemannian Multinomial Logistics Regression for SPD Neural Networks, Chen et al. CVPR 2024

[2] A Neural Network Based on SPD Manifold Learning for Skeleton-Based Hand Gesture Recognition Nguyen et al. 2019

[3] U-SPDNet: An SPD manifold learning-based neural network for visual classification Wang et al. 2023

[4] The training process of many deep networks explores the same low-dimensional manifold, Mao et al. 2024

[5]  Principles of Riemannian Geometry in Neural Networks, Hauser et al. 2017
Thanks for your response, I appreciate it.

You mentioned $\delta W$ is almost full rank and you used PSD as a proxy for it. Why is a PSD matrix a good proxy for full-rank matrices? Am I missing something?
Thanks for the authors' response. My main concerns have been addressed. So I will keep my score.
I appreciate the authors' efforts on experiments with Llama 2 7B. However, I'm suspicious about the experimental settings used for the latest experiments on UUID memorization. From the original MoRA paper [1], LoRA and MoRA can indeed memorize UUIDs well, as evidenced from the 100% character level accuracy (Table 2) in [1]. However, the authors' experiments do not reflect this. Furthermore, why have the authors reported cross-entropy instead of accuracy as done in the original paper? 

This discrepancy looks suspicious, and warrants more careful experimentation. I would encourage the authors to investigate this in detail. Given these results, I'm afraid I cannot change my score.

[1] MoRA: High-Rank Updating for Parameter-Efficient Fine-Tuning Jiang et al. 2024
We sincerely thank the reviewer for their positive feedback and for revising their score.  

> How to change the number of parameters in this formulation (Skew-Circulant etc...)

The skew-circulant matrix, like the circulant matrix, is parameterized by its first row. We consider a general update matrix given by the equation : 
$\Delta W := \sum\_{i=0}^{k-1} A\_i B\_i$, where $A\_i$ is a circulant matrix and $B\_i$ is skew-circulant matrix. Since both $A\_i, B\_i$ are parameterized by $n$ parameters, $A\_iB\_i$ has $2n$ parameters and thus $\Delta W$ has $2nk$ parameters which is the same as rank $k$ LoRA update. We will add these details to the manuscript.

> Hypothesis on the effectiveness of our method in various data regimes. 

We believe our main hypothesis is that LDRs provide a better approximation of general matrices because they are not limited to being low rank. We evaluated this hypothesis and found it to be well-supported by several experiments (see Figure 1, left, and Section 4). In low-data regimes, where we have to learn a data distribution from a small sample size, the flexibility of LDRs helps improve our approximation. Similarly, in large-data regimes, where the data distribution is more complex, the lack of low-rank restrictions allows us to achieve better results.


> Limitations of our technique.

We hypothesize that in cases where the update matrix can be well approximated by a low-rank matrix, LoRA styled methods might converge faster. We will add this to our current limitation section (Appendix M).
Dear Reviewer GJ7U,

We would like to once more sincerely thank you for all the comments and very useful feedback. We think that we have addressed in depth all Reviewer's questions. Please let us know. If the Reviewer has any additional questions, we would be more than happy to answer them.

Yours sincerely,

The Authors
Dear Reviewer aa5x,

We would like to once more sincerely thank you for all the comments and very useful feedback. We think that we have addressed in depth all Reviewer's questions. Please let us know. If the Reviewer has any additional questions, we would be more than happy to answer them.

Yours sincerely,

The Authors
Thank you to the authors for the follow-up experiments and the detailed conversations. I believe that with the new experiments added to the paper and the following, the paper should be accepted.

1. Please add a sentence more information on how we change the number of parameters in this formulation (Skew-Circulant etc...)
2. Please discuss, as a hypothesis which lends itself to future work, why it is that this method seems to perform well at both low data and high data regimes. This is a bit counterintuitive to me.
3. Please address the limitations of this technique a bit more in-depth and when we expect this technique to perform worse than others.

With the changes already presented, and the integration of the above points. I have raised my score to a 6 due to the strong cooperation of the authors towards providing additional information, experiments etc.. and the additional strong results and recommend acceptance.
> Large data Regime

We investigate the performance of SURM in a large data regime using the iNat2021 [1] dataset. iNat2021 has over **2.7 million** training images, 100K validation images, and 500K test images, representing a wide array of **10,000 species (classes)**. 

Full fine-tuning: **69.98%** vs SURM (circulant): **69.01%**

We observe that SURM achieves similar results to full-finetuning using only **55K** parameters as opposed to **86M** in full fine-tuning. We will add these details to the manuscript.

[1] Benchmarking Representation Learning for Natural World Image Collections, Horn et al. 2021.. 

 > Large Model regime/Small data Regime

Thank you for the excellent comment. We present an example below where *methods like LoRA and MoRA struggle to learn a complex task in a low data regime with a large-scale model.*

Following the suggestion reviewer o41z, we created 10k pairs of UUIDs and tested the memorization capability of LLMs. We use the large-scale **Llama-2-7B** model [2]. The goal of this experiment is to show that models struggle to learn out-of-distribution data when using low-rank updates. Since the pdf can not be updated, the results are presented below:

| Method &#8595; / Steps &#8594;    | 25   | 100  | 200  | 300  | 400  | 500  | 600   | 700   | 800   | 900   | 1000  | 3000 |
|----------------------------------|------|------|------|------|------|------|-------|-------|-------|-------|-------|------|
| LoRA (2.9% Param)                | 2.42 | 2.29 | 2.30 | 2.29 | 2.28 | 2.28 | 2.28  | 2.28  | 2.29  | 2.27  | 2.29  | 2.29 |
| MoRA (2.9% Param)                | 2.43 | 2.29 | 2.30 | 2.28 | 2.28 | 2.28 | 2.29  | 2.28  | 2.29  | 2.27  | 2.29  | 2.26 |
| Circulant (0.01% Param)          | 3.40 | 3.32 | 2.96 | 2.70 | 2.35 | 2.04 | 1.92  | 1.83  | 1.78  | 1.74  | 1.72  | 0.97 |
| Circulant+Skew-circulant (0.04%) | 3.78 | 0.34 | 0.09 | 0.05 | 0.02 | 0.02 | 0.006 | 0.009 | 0.004 | 0.003 | 0.001 | 0.0  |


We observe that LoRA and MoRA struggle to fit the data (cross-entropy loss around 2.3) whereas our circulant variant achieves a loss of **0.97**. In this experiment, we used a high rank=256 for both LoRA and MoRA, and modified the $Q, K, V$ parameters for all methods. 


Furthermore, we show the effect of increasing the number of training parameters by using sums of products of circulant and skew-circulant matrices. A skew circulant matrix $S = (s\_{jk})\_{j,k=0}^{n-1}$ is said to be skew-circulant if $s\_{jk} = s\_{j−k}$ and $s\_{−l} = −s\_{n−l}$ for $1 \leq l \leq n − 1$. The motivation for using this particular sum of products comes from the approximation quality of such matrices (see Theorem 1 in [3]). This is evident in practice as circulant+skew-circulant variant obtains a loss=**0** and converges much faster. 

This result and our toy experiment (Figure 5) consistently show that low rank updates may struggle to fit various data regimes and that unrestricted-rank matrices may be required to alleviate this issue. SURMs solve this problem using structured matrices (keeping the parameter budget low) while allowing for arbitrary ranks. 

We will add this result to the manuscript.

[2] MoRA: High-Rank Updating for Parameter-Efficient Fine-Tuning Jiang et al. 2024

[3] Structured Transforms for Small-Footprint Deep Learning Sindhwani et al. 2015
> Large data Regime

We investigate the performance of SURM in a large data regime using the iNat2021 [1] dataset. iNat2021 has over **2.7 million** training images, 100K validation images, and 500K test images, representing a wide array of **10,000 species (classes)**. 

Full fine-tuning: **69.98%** vs SURM (circulant): **69.01%**

We observe that SURM achieves similar results to full-finetuning using only **55K** parameters as opposed to **86M** in full fine-tuning.. We will add these details to the manuscript.

[1] Benchmarking Representation Learning for Natural World Image Collections, Horn et al. 2021.. 

 > Large Model regime 

Following the suggestion reviewer o41z, we created 10k pairs of UUIDs and tested the memorization capability of LLMs. We use the large-scale **Llama-2-7B** model [2]. The goal of this experiment is to show that models struggle to learn out-of-distribution data when using low-rank updates. Since the pdf can not be updated, the results are presented below:

| Method &#8595; / Steps &#8594;    | 25   | 100  | 200  | 300  | 400  | 500  | 600   | 700   | 800   | 900   | 1000  | 3000 |
|----------------------------------|------|------|------|------|------|------|-------|-------|-------|-------|-------|------|
| LoRA (2.9% Param)                | 2.42 | 2.29 | 2.30 | 2.29 | 2.28 | 2.28 | 2.28  | 2.28  | 2.29  | 2.27  | 2.29  | 2.29 |
| MoRA (2.9% Param)                | 2.43 | 2.29 | 2.30 | 2.28 | 2.28 | 2.28 | 2.29  | 2.28  | 2.29  | 2.27  | 2.29  | 2.26 |
| Circulant (0.01% Param)          | 3.40 | 3.32 | 2.96 | 2.70 | 2.35 | 2.04 | 1.92  | 1.83  | 1.78  | 1.74  | 1.72  | 0.97 |
| Circulant+Skew-circulant (0.04%) | 3.78 | 0.34 | 0.09 | 0.05 | 0.02 | 0.02 | 0.006 | 0.009 | 0.004 | 0.003 | 0.001 | 0.0  |


We observe that LoRA and MoRA struggle to fit the data (cross-entropy loss around 2.3) whereas our circulant variant achieves a loss of **0.97**. In this experiment, we used a high rank=256 for both LoRA and MoRA, and modified the $Q, K, V$ parameters for all methods. 


Furthermore, we show the effect of increasing the number of training parameters by using sums of products of circulant and skew-circulant matrices. A skew circulant matrix $S = (s\_{jk})\_{j,k=0}^{n-1}$ is said to be skew-circulant if $s\_{jk} = s\_{j−k}$ and $s\_{−l} = −s\_{n−l}$ for $1 \leq l \leq n − 1$. The motivation for using this particular sum of products comes from the approximation quality of such matrices (see Theorem 1 in [3]). This is evident in practice as circulant+skew-circulant variant obtains a loss=**0** and converges much faster. 

This result and our toy experiment (Figure 5) consistently show that low rank updates may struggle to fit various data regimes and that unrestricted-rank matrices may be required to alleviate this issue. SURMs solve this problem using structured matrices (keeping the parameter budget low) while allowing for arbitrary ranks. 

We will add this result to the manuscript.

[2] MoRA: High-Rank Updating for Parameter-Efficient Fine-Tuning Jiang et al. 2024

[3] Structured Transforms for Small-Footprint Deep Learning Sindhwani et al. 2015
> Large data Regime

We investigate the performance of SURM in a large data regime using the iNat2021 [1] dataset. iNat2021 has over **2.7 million** training images, 100K validation images, and 500K test images, representing a wide array of **10,000 species (classes)**. 

Full fine-tuning: **69.98%** vs SURM (circulant): **69.01%**

We observe that SURM achieves similar results to full-finetuning using only **55K** parameters as opposed to **86M** in full fine-tuning. We will add these details to the manuscript.

[1] Benchmarking Representation Learning for Natural World Image Collections, Horn et al. 2021.. 

 > Large Model regime 

Following the suggestion reviewer o41z, we created 10k pairs of UUIDs and tested the memorization capability of LLMs. We use the large-scale **Llama-2-7B** model [2]. The goal of this experiment is to show that models struggle to learn out-of-distribution data when using low-rank updates. Since the pdf can not be updated, the results are presented below:

| Method &#8595; / Steps &#8594;    | 25   | 100  | 200  | 300  | 400  | 500  | 600   | 700   | 800   | 900   | 1000  | 3000 |
|----------------------------------|------|------|------|------|------|------|-------|-------|-------|-------|-------|------|
| LoRA (2.9% Param)                | 2.42 | 2.29 | 2.30 | 2.29 | 2.28 | 2.28 | 2.28  | 2.28  | 2.29  | 2.27  | 2.29  | 2.29 |
| MoRA (2.9% Param)                | 2.43 | 2.29 | 2.30 | 2.28 | 2.28 | 2.28 | 2.29  | 2.28  | 2.29  | 2.27  | 2.29  | 2.26 |
| Circulant (0.01% Param)          | 3.40 | 3.32 | 2.96 | 2.70 | 2.35 | 2.04 | 1.92  | 1.83  | 1.78  | 1.74  | 1.72  | 0.97 |
| Circulant+Skew-circulant (0.04%) | 3.78 | 0.34 | 0.09 | 0.05 | 0.02 | 0.02 | 0.006 | 0.009 | 0.004 | 0.003 | 0.001 | 0.0  |


We observe that LoRA and MoRA struggle to fit the data (cross-entropy loss around 2.3) whereas our circulant variant achieves a loss of **0.97**. In this experiment, we used a high rank=256 for both LoRA and MoRA, and modified the $Q, K, V$ parameters for all methods. 


Furthermore, we show the effect of increasing the number of training parameters by using sums of products of circulant and skew-circulant matrices. A skew circulant matrix $S = (s\_{jk})\_{j,k=0}^{n-1}$ is said to be skew-circulant if $s\_{jk} = s\_{j−k}$ and $s\_{−l} = −s\_{n−l}$ for $1 \leq l \leq n − 1$. The motivation for using this particular sum of products comes from the approximation quality of such matrices (see Theorem 1 in [3]). This is evident in practice as circulant+skew-circulant variant obtains a loss=**0** and converges much faster. 

This result and our toy experiment (Figure 5) consistently show that low rank updates may struggle to fit various data regimes and that unrestricted-rank matrices may be required to alleviate this issue. SURMs solve this problem using structured matrices (keeping the parameter budget low) while allowing for arbitrary ranks. 

We will add this result to the manuscript.

[2] MoRA: High-Rank Updating for Parameter-Efficient Fine-Tuning Jiang et al. 2024

[3] Structured Transforms for Small-Footprint Deep Learning Sindhwani et al. 2015
> Large Model regime/ UUID Experiments 

Thank you for suggesting the UUID experiment and revising your score. Following [1], we created 10k pairs of UUIDs and we tested the memorization capability of the **Llama-2-7b** model. the results are presented below:

| Method &#8595; / Steps &#8594;    | 25   | 100  | 200  | 300  | 400  | 500  | 600   | 700   | 800   | 900   | 1000  | 3000 |
|----------------------------------|------|------|------|------|------|------|-------|-------|-------|-------|-------|------|
| LoRA (2.9% Param)                | 2.42 | 2.29 | 2.30 | 2.29 | 2.28 | 2.28 | 2.28  | 2.28  | 2.29  | 2.27  | 2.29  | 2.29 |
| MoRA (2.9% Param)                | 2.43 | 2.29 | 2.30 | 2.28 | 2.28 | 2.28 | 2.29  | 2.28  | 2.29  | 2.27  | 2.29  | 2.26 |
| Circulant (0.01% Param)          | 3.40 | 3.32 | 2.96 | 2.70 | 2.35 | 2.04 | 1.92  | 1.83  | 1.78  | 1.74  | 1.72  | 0.97 |
| Circulant+Skew-circulant (0.04%) | 3.78 | 0.34 | 0.09 | 0.05 | 0.02 | 0.02 | 0.006 | 0.009 | 0.004 | 0.003 | 0.001 | 0.0  |


We observe that LoRA and MoRA struggle to fit the data (cross-entropy loss around 2.3) whereas our circulant variant achieves a loss of **0.97**. In this experiment, we used a high rank=256 for both LoRA and MoRA, and modified the $Q, K, V$ parameters for all methods. 


Furthermore, we show the effect of increasing the number of training parameters by using sums of products of circulant and skew-circulant matrices. A skew circulant matrix $S = (s\_{jk})\_{j,k=0}^{n-1}$ is said to be skew-circulant if $s\_{jk} = s\_{j−k}$ and $s\_{−l} = −s\_{n−l}$ for $1 \leq l \leq n − 1$. The motivation for using this particular sum of products comes from the approximation quality of such matrices (see Theorem 1 in [2]). This is evident in practice as circulant+skew-circulant variant obtains a loss=**0** and converges much faster. 

This result and our toy experiment (Figure 5) consistently show that low rank updates may struggle to fit various data regimes and that unrestricted-rank matrices may be required to alleviate this issue. SURMs solve this problem using structured matrices (keeping the parameter budget low) while allowing for arbitrary ranks. 

We will add this result to the manuscript.

[1] MoRA: High-Rank Updating for Parameter-Efficient Fine-Tuning Jiang et al. 2024

[2] Structured Transforms for Small-Footprint Deep Learning Sindhwani et al. 2015 



> Large data Regime

We investigate the performance of SURM in a large data regime using the iNat2021 [3] dataset. iNat2021 has over **2.7 million** training images, 100K validation images, and 500K test images, representing a wide array of **10,000 species (classes)**. 

Full fine-tuning: **69.98%** vs SURM (circulant): **69.01%**

We observe that SURM achieves similar results to full-finetuning using only **55K** parameters. We will add these details to the manuscript.

[3] Benchmarking Representation Learning for Natural World Image Collections, Horn et al. 2021.


Please let us know if you have any questions.
I appreciate the detaild response from the authors. My questions and weakness about hyperparameter tuning strategy have been  addressed. However, I am still not convinced with the authors' reasoning about large scale experiments. Even in settings where data is scarce, when applied to larger models in the scale of billion parameters and to more complex tasks like language generation, methods are not guaranteed to work as well. Without these experiments, it's hard to judge the effectiveness of the method. Hence, I will maintain my score.
Given the new information, I raised my score to a 4.

I feel that there needs to be more testing in higher data regimes to be accepted. Specifically for the following reasons:

- In cases where full fine-tuning performs best, the performance of SURMS don't seem to be as strong, such as on CIFAR-100 and CIFAR-10

- There are much stronger techniques for nearly all the datasets tested that the reported accuracy since in the low data regime, we can either use zero-shot embeddings, ICL, or finetune smaller networks rather than relying on adapter layers.

- A high rank adapter makes most sense when the training process has to encode a lot of data, which outstrip low rank approximations learning capacity.  So not only should there be more comparison against higher rank adapters such as MoRA but there also needs to be more testing in regimes where we expect higher ranks to be most useful, UUID memorization I feel like is an easy one to test at relatively low compute.