S$^{2}$FT: Efficient, Scalable and Generalizable LLM Fine-tuning by Structured Sparsity

Authors: xinyu  yang
jixuan  leng
geyang  guo
jiawei  zhao
ryumei  nakada
linjun  zhang
huaxiu  yao
beidi  chen
  cmu
georgia  tech
  caltech
  rutgers
  w′
  permute
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 03:31:50

Abstract: Current PEFT methods for LLMs can achieve either high quality, efficient training, or scalable serving, but not all three simultaneously. To address this limitation, we investigate sparse fine-tuning and observe a remarkable improvement in generalization ability. 
Utilizing this key insight, we propose a family of Structured Sparse Fine-Tuning (S${^2}$FT) methods for LLMs, which concurrently achieve state-of-the-art fine-tuning performance, training efficiency, and inference scalability. S${^2}$FT accomplishes this by selecting sparsely and computing densely. It selects a few heads and channels in the MHA and FFN modules for each Transformer Block, respectively. Next, it co-permutes weight matrices on both sides of the coupled structures in LLMs to connect the selected components in each layer into a dense submatrix. Finally, \model performs in-place gradient updates on all submatrices. Through theoretical analysis and empirical results, our method prevents overfitting and forgetting, delivers SOTA performance on both commonsense and arithmetic reasoning with 4.6% and 1.3% average improvements compared to LoRA, and outperforms full FT by 11.5% when generalize to various domains after instruction tuning. By integrating our partial back-propagation algorithm, \model saves the fine-tuning memory up to 3$\times$ and improves the latency by 1.5-2.7$\times$ compared to full FT, while delivering an average 10% improvement over LoRA on both metrics. We further demonstrate that S${^2}$FT can be decoupled into adapters, enabling effective fusion, fast switch, and efficient parallelism for serving multiple fine-tuned models.

Main paper: 
 introduction: 
 Recently, Large Language Models (LLMs) have achieved significant success [16, 1, 64] . With these models being applied in diverse domains, full fine-tuning (FT) is commonly employed to enhance their downstream capabilities [54, 6, 71] . However, retraining all parameters comes with three drawbacks: (i) Full FT suffers from catastrophic forgetting, where a model forgets pre-trained knowledge while acquiring new information [44, 8] . (ii) As the model and dataset sizes grow at scale, full FT becomes increasingly computation-demanding and memory-intensive [68] . (iii) It is impractical to store and serve thousands of fine-tuned LLMs on modern GPUs if each requires full parameter storage [77, 58] .Parameter-efficient fine-tuning (PEFT) methods propose to address these bottlenecks by updating a small fraction of parameters [21] . Rather than merely reducing the number of learnable parameters, an ideal PEFT method should possess three key properties to be practically effective and efficient: High Quality: It should exhibit both memorization and generalization capabilities, balancing the acquisition of new information from fine-tuning tasks with the retention of pre-trained knowledge.Efficient Training: It should minimize the memory footprint for model gradient and optimization states, and further translate such memory efficiency into less computation and fine-tuning speedup. Scalable Serving: It should avoid adding inference overhead when serving a single PEFT model. For multiple models, new parameters should be partially stored as adapters to save memory, and allows for effective fusion [75] , fast switch [33] , and efficient parallelism [58] among thousands of adapters.Figure 1 : An Overview of the S 2 FT Family for LLMs: First, we perform sparse selection of specific attention heads and channels within the coupled structures of the MHA and FFN modules. Next, we apply co-permutation to the weight matrices on both sides of these structures, enabling dense gradient computation only for the selected components. While we demonstrate S 2 FT by selecting the same heads/channels on both sides for clarity, our approach also supports asymmetric selection strategies.However, achieving all the aforementioned goals simultaneously is challenging. Common PEFT approaches, such as LoRA [27] , DoRA [38] , and Galore [76] , project the model's weights or gradients onto a low-rank subspace. While this significantly reduces memory footprint, their performance lags behind full fine-tuning in most large-scale scenarios. Recent state-of-the-art PEFT methods have aimed to improve performance but at the cost of serving efficiency. ReFT operates on a frozen base model and learns task-specific interventions on hidden representations that cannot be merged into the original model, leading to a 2.2× increase in inference latency. LISA [48] employs a coarse-grained selective method by randomly freezing most Transformer blocks during optimization, which requires significantly more trainable parameters. Consequently, in scaled serving settings like S-LoRA [58] , LISA can only serve at most 1 10 as many fine-tuned models as LoRA under the same memory budget. Prior to the era of LLMs, PEFT methods based on unstructured sparse fine-tuning (SpFT) have shown a strong trade-off between low number of parameters and high model performance without sacrificing serving efficiency [61, 3, 69] . We hypothesize that SpFT, which selectively updates a small subset of model parameters, can outperform LoRA and its variants in generalization capabilities. In Figure 2 , our findings across various generalization tasks support this hypothesis. However, the unstructured nature of SpFT necessitates sparse operations in computation, hindering its efficient training and scalable serving on modern hardware. This makes SpFT less practical for adapting LLMs at scale.In this work, we propose a family of Structured Sparse Fine-Tuning (S 2 FT) methods to "select sparsely and compute densely" (See Figure 1 ), thereby closing the efficiency gap in SpFT. Inspired by structured weight pruning techniques [45, 42] , we first identify several coupled structures inherent in LLMs that are connected by intermediate activations. For example, in the multi-head attention (MHA) module, each attention head in the query, key, and value projections is linked to only a few rows in the output projection. Similarly, in the feed-forward network (FFN) module, each column in the up and gate projections corresponds to a single row in the down projection. By co-permuting the matrices on both sides of these coupled structures, we can preserve the original output of these structures, with only the order of the intermediate activations changed. Exploiting this property, our S 2 FT strategically selects a subset of attention heads for the MHA module and a subset of channels for the FFN module. We then permute the coupled structures to connect the selected components within each linear layer into a dense submatrix. Finally, through our partial back-propagation algorithm with only two-line code modification, S 2 FT performs in-place gradient updates exclusively for all selected submatrices, boosting training efficiency by eliminating redundant forward activations and backward calculation.Through our theoretical analysis, we demonstrate that S 2 FT mitigates overfitting and forgetting under distribution shifts. Empirically, S 2 FT outperforms other PEFT methods on LLaMA and Mistral family models, improving 1.2-4.1% on commonsense reasoning tasks and 0.6-1.9% on arithmetic reasoning ones. It also surpasses full FT by 11.5% when generalize to various domains after instruction tuning.Finally, we conduct a comprehensive analysis to verify the training efficiency and serving scalability of S 2 FT. Compared to existing PEFT methods, S 2 FT not only saves 1.4-3.0× memory, but also increases latency by 1.5 to 2.7×, making LLM fine-tuning more accessible. Additionally, S 2 FT's parameter updates can be decomposed into adapters, enabling adapter fusion with smaller performance drop than LoRA. Our method also results in more scalable and efficient adapter switch and parallelism through reduced matrix multiplications, showcasing strong potential for large-scale LLM serving scenarios. 
memorization or generalization?: 
 In this section, we evaluate the memorization and generalization capabilities of various fine-tuning methods, including full FT, LoRA, and SpFT. We hypothesize that SpFT can generalize better to downstream tasks. To support this hypothesis, we present detailed observations and analyses. Further theoretical analysis about the generalization capabilities of the S 2 FT family can be found in Section 4. Hypothesis. We hypothesize that SpFT offers superior generalization than both full FT and LoRA, while maintaining comparable memorization to LoRA with the same number of trainable parameters. Experimental Setup. We fine-tune the Llama3-8B on the Math10K data [28] using SpFT, LoRA, and full FT. In addition to training losses, accuracies are measured on downstream tasks in LLM-Adapters, including near out-of-distribution (OOD) generalization on both easy (i.e, MultiArith, AddSub, SingleEq, MAWPS) and hard (i.e, GSM8K, AQuA, SVAMP) arithmetic reasoning tasks, and far OOD generalization on commonsense reasoning ones. For PEFT methods, we set three ratios of trainable parameters (p = 10%, 1%, 0.1%) and search for the optimal hyperparameters on the valid set. In SpFT, trainable parameters are selected randomly with given ratios. See details in Appendix C. Observations. Figure 2 indicates several key findings. First, SpFT achieves lower training losses than LoRA when using the same ratio of trainable parameters, especially at very small ratios. This gap arises from the more complex optimization process in LoRA, which requires the simultaneous updating of two matrices [23] . Second, we observe both elevated training loss and reduced average accuracy on easier math tasks as the ratio decreases, suggesting a positive correlation between memorization abilities and trainable parameters. Notably, with only 10% of the parameters updated, PEFT methods learn comparable memorization abilities to full FT when trained on a 10k-sample dataset.When generalizing to complex mathematical problems or commonsense reasoning tasks, the performance ranking emerges as: SpFT > Full FT > LoRA. SpFT effectively transfers reasoning abilities to commonsense domains, while LoRA exhibits significant performance drops in far OOD generalization. This indicates (i) freezing a larger fraction of the parameters can retain more pre-trained abilities, and (ii) approximating high-dimensional gradients with low-rank decomposition may overfit fine-tuned data and hinder the model from generalization. Since LLMs are pre-trained on high-quality data, SpFT emerges as the preferred choice for fine-tuning on task-specific data of varying quality.3 The S 2 FT family of methods While SpFT demonstrates strong generalization ability and good overall performance in Section 2, its unstructured nature poses challenges for efficient training and scalable serving on modern hardware (e.g., GPU). This is because of the need for sparse operations when storing and computing weights, gradients, and optimization states, which are significantly slower than their dense variants on GPU. This motivates our investigation into structured sparsity approaches that utilize only dense operations: Can structured sparsity improve hardware efficiency while preserving performance by selecting sparsely but computing densely? If so, how far can the flexibility of selection be pushed in this context?To answer this question, we design a family of Structured Sparse Fine-Tuning (S 2 FT) methods with dense-only computations, making PEFT effective, efficient and scalable. We begin by discovering the coupled structure in LLMs in Section 3.1. Leveraging this property, Section 3.2 introduce the selection and permutation strategies of S 2 FT, with overall pipeline illustrated in Figure 1b . In Section 3.3, we present our partial back-propagation algorithm that enables end-to-end training latency reduction. 
discover coupled structures in llms: 
 We initiate our pursuit of flexible structured sparsity by examining the coupled structures in LLMs. Structure Dependency in LLMs. Inspired by prior work on structured pruning [45, 17] , our study start by building the dependencies between activations and weights for LLMs. Let A denote an activation and W denote a weight in the model. We define In(A) as the set of parameters that directly contribute to the computation of A, and Out(A) as the set of parameters that depend on A in the computation of subsequent activations. The dependency between structures can be defined as follows:EQUATIONEQUATIONwhere Deg + (W 1 ) represents the out-degree of weight W 1 , and Deg -(W 2 ) represents the in-degree of weight W 2 . Each equation represents a unqiue directional dependency between activations and weights. When both equations hold simultaneously, a coupled structure exists between W 1 and W 2 .In Figure 3 , we employ deep linear networks to illustrate two types of coupled structures in LLMs: Basic Structures: In Figure 3a , these structures exist in both the multi-head attention (MHA) and feed-forward network (FFN) modules. Taking LLaMA as an example, in the MHA module, we consider the Query (Q), Key (K), and Value (V ) projections as W 1 , and the Output (O) projection as W 2 , while Softmax(QK ⊤ )V (x) acting as the activation between weight matrices. Similarly, in the FFN module, the Up (U ) and Gate (G) projections function as W 1 , with the Down (D) projection corresponding to W 2 . Here, U (x) • SwiGLU(G(x)) serves as the activations connecting W 1 and W 2 .Residual Structures: In Figure 3b , this type of coupled structures exists between the MHA and FFN modules. We further consider how residual connections influence the activations in these structures. Permutation Invariance of Coupled Structures. Figure 3 demonstrates that W 1 and W 2 can be co-permuted using the same order, which only affects the order of activations between them while preserving the original output from the coupled structure. Since residual dependencies require an additional runtime step to permute the residuals, we will focus on basic dependencies in our method.At this point, all coupled structures within the model have been identified. The subsequent sparse selection and permutation processes are straightforward, with overall pipeline illustrated in Figure 1b . MHA Module: There are four linear layers in a MHA module: Q, K, V, O ∈ R d×d . For a model with h attention heads, each head i ∈ [h] has its own projections denoted asQ i ∈ R d×d h , K i ∈ R d×d h , V i ∈ R d×d h , and O i ∈ R d h ×d , where d h = d/h is the dimension per head. Let S MHA ⊆ [h]denotes a small subset of attention heads. By permuting S MHA to the beginning of each weight matrix, we are able to update these selected heads using dense-only operations, while keeping the other ones frozen. FFN Module: There are three linear layers in a FFN module: U, G ∈ R k×d and D ∈ R d×k . In S 2 FT, only a few channels of them require gradient updates. Let S FFN ⊆ [d] denote the selected channels.We can permute S FFN to the beginning of each weight matrix and only fine-tune this compact subset. Next, we provide several strategies for identifying and selecting important subsets in each module.1. S 2 FT-R (S 2 FT): In this strategy, a subset of channels is randomly selected and set to be trainable. 2. S 2 FT-W: This variant selects subsets based on the magnitude of activations on a calibration set.3. S 2 FT-A: This variant selects subsets based on the magnitude of activations on a calibration set. 4. S 2 FT-S: Top-K subsets are ranked and selected by the product of weight and activation magnitudes. 5. S 2 FT-G: This variant selects subsets based on the magnitude of gradients on a calibration set.Here, 1 and 2 can be directly applied without preprocessing. 3 and 4 only require a forward pass on a small calibration dataset. While 5 necessitates a backward pass on this dataset, it does not store optimization states and can mitigate memory footprints for activations through gradient checkpointing [18] . By default, we use S 2 FT-R for a fair comparison and discuss other variants in Section 5.4.  
theoretical analysis: 
 In this section, we theoretically explore why S 2 FT demonstrates stronger generalization capabilities compared to LoRA. We consider a pre-trained L-layer deep linear networks, which has been widely used to facilitate the theoretical analysis of complex DNNs [57, 30, 43, 22, 34, 5] . Let f pre (x) := W pre L W pre L-1 . . . W pre 1 x be the pre-trained deep linear network, where W pre ℓ ∈ R d ℓ ×d ℓ-1 , with d 0 = p and d L = q. We fine-tune the ℓ-th layer with low-rankness level r ≤ min{d ℓ , d ℓ-1 } or sparsity levelEQUATIONwhereW pre ℓ := W pre L W pre L-1 . . . W pre ℓ ∈ R d L ×d ℓ-1 and W pre ℓ := W pre ℓ W pre ℓ-1 . . . W pre 1 ∈ R d ℓ ×d0 with W pre 0 = I p and W pre L = I q .In a transformer-based LLM, each row of W ℓ can represents either the parameters in a single head for the MHA module or that in a single channel for the FFN module.Given n observations (x(i) i , y (i) i ) ⊂ R p × R q , we fine-tune f pre by minimizing the empirical risk R (i) n (f ℓ,U,V ) := (1/n) i∈[n] ∥y (i) i -f ℓ,U,V (x (i) i )∥ 2 viagradient descent. For LoRA, we train both low-rank matrices (U, V ) in Equation (3) with d ← r. For S 2 FT, we train only V in Equation (3) with d ← s and fixed U ← U S 2 FT S := [e a1 ; e a2 ; . . . ; e as ], which specifies s rows to fine-tune, where S = {a 1 , . . . , a s } ⊂ [d ℓ ] and e a is the a-th standard basis. Motivated from the results that gradient descent has implicit regularization [74, 19, 5] , we directly consider the minimum norm solutions.We consider a multiple linear regression setting. Assume that the in-distribution training data (x (i) , y (i) ) ∈ R p+q and out-of-distribution test data (x (o) , y (o) ) ∈ R p+q are generated i.i.d. according toy (k) = B (k) x (k) + ϵ (k) , k ∈ {i, o},where B (k) ∈ R q×p is the coefficient matrix, x (k) and ϵ (k) are mean zero sub-Gaussian signal and noise with covariance matrices Σ (k)x and Σ (k) ϵ , respectively. The generalization capacity is measured by the fine-tuned model's excess risk E(f) := E[∥y (o) -f (x (o) )∥ 2 ] -inf f ′ E[∥y (o) -f ′ (x (o) )∥ 2 ].For these OOD data, LoRA suffers from forgetting, while S 2 FT can maintain pre-training knowledge. Σ (i) x = Σ (o) x = Σ x for some Σ x ∈ R p×p , and ∥(W pre ℓ+1 U S 2 FT S )(W pre ℓ+1 U S 2 FT S ) † (B (o) -B (i) )Σ 1/2 x ∥ 2 F ≤ ε 2 E (o) (f pre )for some ε > 0. Assumption 4.1 states that while the covariate distribution remains unchanged, the label distribution conditioned on covariates may shift, but not exceeding a factor of ϵ 2 of the OOD risk of f pre . This holds for fine-tuning with proper channel selection, where primarily the output distribution is changed. Theorem 4.2 (Out-of-distribution Excess Risk, Informal). Suppose Assumption 4.1 holds. Considern → ∞. If B (i) = W pre ℓ+1 B(i) W pre ℓ-1 holds for some B(i) ∈ R d ℓ ×d ℓ-1 , and s ≤ rank(Σ (i) f ), then, E (o) (f ℓ,U S 2 FT S ,V S 2 FT ) ≤ (1 + 3ε 2 )E (o) (f pre ), E (o) (f ℓ,U LoRA ,V LoRA ) ≥ ∥(B (o) -B (i) )Σ 1/2x ∥ 2 F . Theorem 4.2 indicates that the OOD risk of S 2 FT is bounded above by that of f pre , while that of LoRA is bounded below by the label shift magnitude. If f pre already has low risk for OOD tasks, and the label shift is significant, S 2 FT is expected to outperform LoRA. Essentially, when the OOD task deviates significantly from the FT distribution, LoRA may forget the pre-trained knowledge and overfit to the FT data, compromising its generalization capabilities. See formal statements in Theorem E.8. 
experiments: 
 In this section, we conduct a series of experiments across three diverse benchmarks covering more than 20 datasets. Our goal is to provide a rich picture of how S 2 FT performs in different scenarios. Here, we compare our method with different fine-tuning strategies and categories including: (i) Full fine-tuning (FT), (ii) reparameterized fine-tuning: LoRA [27] , DoRA [38] , and Galore [76] , (iii) adapter-based fine-tuning: Series Adapter [26] , Parallel Adapter [24] , and LoReFT [67] , (iv) promptbased fine-tuning: Prefix-Tuning [36] , (v) sparse fine-tuning: LISA [48] . For a fair comparison, we keep a comparable number of trainable parameters in S 2 FT to that of LoRA. The design choices for trainable parameter allocations in S 2 FT will be detailed in Section 5.4. All other hyperparameters are selected via cross-validation. Detailed setups and baseline descriptions are provided in Appendix D.Dataset Descriptions. The commonsense reasoning dataset comprise eight subsets: BoolQ [12] , PIQA [9] , SocialQA [56] , HellaSwag [73] , WinoGrande [55] , ARC-challenge [13] , ARC-easy [13] , and OpenbookQA [46] . Following the experimental setup of LLM-Adapters [28] , we split each dataset into training and test sets. Subsequently, we combine the training data from all eight tasks into a single fine-tuning dataset and evaluate performance on the individual test dataset for each task.Results. Table 1 showcases that S 2 FT consistently outperforms existing PEFT methods across the LLaMA-7B/13B, LLaMA2-7B and LLaMA3-8B models. When compared to LoRA and DoRA, it achieves average performance gains of 4.6% and 2.8%, respectively. Additionally, S 2 FT also demonstrates superior performance against recent approaches including Galore, LoReFT, and LISA, with accuracy improvements of at least 1.0%. Remarkably, despite using less than 1% of trainable parameters, our method surpasses full FT by 0.5%. The 3.0% improvement observed on the LLaMA3-8B suggests that maintaining most pre-trained parameters frozen enables better generalization to test distributions. 5.2 Arithmetic Reasoning Dataset Descriptions. We followed Hu et al. [28] and evaluated S 2 FT on seven math reasoning tasks, including MultiArith [53] , GSM8K [14] , AddSub [25] , AQuA [37] , SingleEq [31] , SVAMP [50] and MAWPS [32] . Our fine-tuning employed the Math10K dataset [28] , which combines training sets from GSM8K, MAWPS, and AQuA, augmented with LM-generated chain-of-thought steps. Therefore, these three tasks are considered ID, while the remaining four are classified as OOD tasks.Results. As showcased in Table 2 , S 2 FT consistently outperforms other PEFT methods for different models. On average, it achieves improvements of 1.3% and 0.9% over LoRA and DoRA, respectively. These results highlight the versatility and effectiveness of our approach across a diverse range of tasks. Additionally, we observe substantial improvements even when compared to Full FT for the LLaMA3-8B model, particularly on complex tasks such as GSM8K and AQuA. This suggests that S 2 FT better preserves the original reasoning capabilities of this stronger model while acquiring new skills from the fine-tuning data, thereby validating the enhanced generalization ability of our method.Dataset Descriptions. To further showcase S 2 FT's superior generalization ability, we employ the instruction-following fine-tuning task with Alpaca GPT-4 dataset, which comprises 52k samples generated by GPT-4 [2] based on inputs from Alpaca [63] . Performance is measured on MT-Bench [78] , featuring 80 high-quality, multi-turn questions designed to assess LLMs on eight different aspects.Results. Table 3 offers a comprehensive evaluation of Full FT, LoRA, LISA, and S 2 FT across various tasks in the MT-Bench benchmark, including Writing, Roleplay, Reasoning, Code, Math, Extraction, STEM, and Humanities. It is observed that S 2 FT > LISA > Full FT > LoRA/Galore ≥ Vanilla for both Mistral-7B and LLama2-7B. This is because sparse FT methods like S 2 FT and LISA retain more pre-trained knowledge while acquiring new skills on the FT dataset, thereby generalizing better to diverse tasks in MT-Bench. Moreover, our method outperforms LISA due to its fine-grained and flexible selection strategy, enabling all layers to learn to follow instructions on the full fine-tuning set.Finally, we detail how S 2 FT distribute trainable parameters across layers, modules, and channels. Uniform across Layers: Following Chen et al. [10] , we allocate parameters to each layer uniformly. Table 4 : Comparison of various channel selection strategies on the commonsense and arithmetic reasoning datasets for the LLama3-8B. We report the average accuracy (%) as the evaluation metric. Selection across Channels: In Section 3.2, we discuss several strategies for channel selection. In our main experiments, we employ random selection to ensure fair comparisons with baseline methods, as these approaches treat all channels with equal importance. However, the sparse structure of S 2 FT offers controllability during fine-tuning, allowing us to prioritize important channels in the selection process to further boost performance. Table 4 compared nine different strategies, incorporating five varying selection metrics (i.e., random, weight, activation, weight-activation product, and gradient), each choosing either the largest or smallest values. For S 2 FT-A, S 2 FT-S, and S 2 FT-G, we employ 1% of the fine-tuning data as a calibration set, introducing only negligible overhead during inference.Task S 2 FT-R S 2 FT-W S 2 FT-A S 2 FT-S S 2 FT-G Large SmallOur results demonstrate that random selection serves as a strong baseline due to its unbiased nature. Among heuristic metrics, selecting channels with the smallest activations (i.e., S 2 FT-A and S 2 FT-S) outperforms random selection. This indicates that these channels contain less task-specific information, enabling us to inject new knowledge through fine-tuning while preserving pre-trained capabilities in other channels. In contrast, other strategies introduce bias that compromises model performance. Notably, the counterintuitive accuracy decrease in S 2 FT-G (Large) suggests that channels with large gradients contain task-related pre-trained knowledge, and modifying them will disrupt these abilities. 
analysis: 
 Having demonstrated the strong generalization capability and overall performance of S 2 FT, we now further explore its training efficiency and serving scalability compared to other fine-tuning techniques.To evaluate training efficiency, we examine two crucial metrics: peak memory footprint and average training latency. These numbers are measured on a single Nvidia A100 (80G) SXM GPU. We keep a comparable number of parameters for all methods. To obtain the average latency, we fine-tune the model for 50 runs, each run including 200 iterations, with 10 warmup runs excluded in measurement. In Figure 5 , we thoughtfully profile S 2 FT on various model sizes, sequence lengths, and batch sizes. Compared to Full FT, S 2 FT saves 1.4-3.0× memory, and speedups fine-tuning by 1.5-2.7 times. When benchmarked against other PEFT methods, S 2 FT establishes new standards for efficiency, offering average reductions of 2% in memory usage and 9% in latency. Notably, S 2 FT outperforms the widely adopted LoRA, achieving about 10% improvement in both matrics by avoiding the need to store new parameters and perform additional calculations. Our partial back-propagation algorithm further improves efficiency by saving unnecessary forward activations and backward calculations.While S 2 FT avoids additional inference overhead for a single fine-tuned model through in-place gradient updates, we will now discuss its scalability for serving thousands of fine-tuned models. To begin, we introduce the unmerged computation paradigm of S 2 FT: Given a pre-trained weight matrix W pre ∈ R d×k and its corresponding fine-tuned weight matrix W with sparsity level s, we define the weight difference as ∆W = W -W pre . Similar to Section 4, ∆W can be decomposed into the product of a weight matrix V ∈ R k×s and a permutation matrix U ∈ R d×s . This decomposition allows us to "unmerge" an adapter ∆W = U V ⊤ from W , thereby sharing similarities with other adapters during inference. Following Zhong et al. [79] , we consider three different adapter composition scenarios:Adapter Fusion. To combine knowledge from multiple trained adapters, we employ weighted fusion when fine-tuning is impractical due to limited data access or computational resources. However, this approach degrades performance. In Table 5 , we compare the effectiveness of LoRA and S 2 FT when combining adapters trained separately on commonsense and arithmetic reasoning tasks, where we consider both fine-tuning overlapped and non-overlapped parameters for different adapters in S 2 FT. Our results show that S 2 FT with non-overlapped parameters achieves the best performance, while the overlapped variant shows inferior results. This is because S 2 FT (non-overlap) modifies orthogonal low-rank spaces for different tasks. Similarly, LoRA largely retains task-specific capabilities during adapter fusion by optimizing low-rank projection matrices to create separate spaces for each adapter.Table 5 : Adapter Fusion Results for LoRA and S 2 FT trained on the commonsense and arithmetic reasoning datasets using the LLama3-8B. We report the average accuracy (%) as the evaluation metric. 6b . Adapter Parallelism. To serve thousands of adapters in parallel, we decompose the computation into separate batched computations for W pre and ∆W following S-LoRA [58] . While LoRA requires two matmul and one add on GPU, S 2 FT reduces this to a matmul, an add, and either a scatter or gather for W 1 and W 2 in Section 3.1. Figure 6c shows that S 2 FT achieves up to 22% faster inference than LoRA under the same memory constraints, with more speedup as the number of adapters scales. 
related work: 
 PEFT methods reduce the fine-tuning cost for large models, which can be categorized into 4 groups: Adapter-based Fine-tuning introduces additional trainable module into the original model. Series Adapters insert components between MHA or FFN layers [51, 26] , while parallel adapters add modules alongside existing components [24] . Recently, ReFT [67] was introduced to directly learn interventions on hidden representations. However, they introduce additional latency during inference.Prompt-based Fine-tuning adds randomly-initialized soft tokens to the input (usually as a prefix) and train their embeddings while freezing the model weights [36, 40, 35] . These approaches result in poor performance compared to other groups, while come at the cost of significant inference overhead.Reparameterized Fine-tuning utilizes low-rank projections to reduce trainable parameters while allowing operations with high-dimensional matrices. LoRA [27] and its recent variants like DoRA [38] , AsyLoRA [80] , and FLoRA [59] , use low-rank matrices to approximate additive weight updates during training. To alleviate the limitations of low-rank structure, other work also add or multiply orthogonal matrices to enable high-rank updating, including MoRA [29] , OFT [52] , and BOFT [39] . These methods require no additional inference cost as the weight updates can be merged into models.Sparse Fine-tuning aims to reduce the number of fine-tuned parameters by selecting a subset of pre-trained parameters that are critical to downstream tasks while discarding unimportant ones. This kind of methods are commonly used in the pre-LLM era [20, 72, 62] . However, they cannot reduce the memory footprints due to their unstructured nature. Recent approaches address this limitation through three directions: (1) developing structured variants that sacrifice selection flexibility for better hardware efficiency [48, 81] , (2) incorporating sparsity into LoRA [66, 15, 41] but yield limited efficiency gains, or (3) using sparse operators for lower memory cost but slow down training [4, 49, 7] .Our work is based on the last category but achieving better performance and efficiency simultaneously. Additionally, we focus on scalable inference of PEFT methods, with S 2 FT being the only approach that enables effective fusion, rapid switching, and efficient parallelism when serving multiple adapters. 
conclusion: 
 This paper introduces S 2 FT, a novel PEFT family that simultaneously achieves high quality, efficient training, and scalable serving for LLM fine-tuning. S 2 FT accomplishes this by selecting sparsely and compute densely. It selects a subset of heads and channels to be trainable for the MHA and FFN modules, respectively. The weight matrices from the two sides of the coupled structures in LLMs are co-permuted to connect the selected components into dense matrices, and only these parameters are updated using dense operations. We hope S 2 FT can be considered as a successor to LoRA for PEFT. 
 
 Appendix: While our work demonstrates the effectiveness of S 2 FT for LLM fine-tuning, several promising directions remain unexplored. First, extending S 2 FT to other architectures with coupled structures, such as CNNs and RNNs, can broaden its applicability. Second, verifying our approach beyond language tasks, particularly in large vision/multi-modal models, will enhance its versatility. Third, exploring more selection strategies can provide deeper insights into optimal fine-tuning protocols due to S 2 FT's controllability. Finally, although our work confirms the feasibility of scalable deployment, developing a practical and efficient serving system for S 2 FT remains an important next step.Since our work focuses on PEFT, it leads to a reduction in hardware resource and energy consumption.Given the growing adoption of LLMs across diverse domains and the corresponding surge in finetuning demands, S 2 FT should represent an important step toward more sustainable AI development.In this study, we use SpFT, LoRA, and Full FT to fine-tune the LLaMA-3-8B model on Math10K dataset [28] for 3 epochs. The Math10K dataset combines training sets from GSM8K [14] , MAWPS [32] , and AQuA [37] , augmented with language model-generated chain-of-thought steps.We train the model for 3 epochs with a batch size of 64. For both PEFT methods-SpFT and LoRA-we tune with three ratios of trainable parameters (p) in each linear layer: 10%, 1%, and 0.1%. We evaluate the model's performance on both arithmetic and commonsense reasoning tasks, representing near out-of-distribution (OOD) and far OOD generalization scenarios, respectively. The arithmetic tasks comprise seven subtasks: MultiArith [53] , GSM8K [14] , AddSub [25] , AQuA [37] , SingleEq [31] , SVAMP [50] , and MAWPS [32] . The commonsense reasoning evaluation includes eight subtasks: BoolQ [12] , PIQA [9] , SocialQA [56] , HellaSwag [73] , WinoGrande [55] , ARC-challenge [13] , ARC-easy [13] , and OpenbookQA [46] . Based on task complexity within arithmetic reasoning, we categorize MultiArith, AddSub, SingleEq, and MAWPS as easy subtasks, while the remaining arithmetic tasks are classified as hard subtasks.The detailed selection strategies and number of trainable parameters are presented in Section 5. Additional hyperparameter configurations for all tasks are provided in Table 6 . We maintain the same hyperparameter settings across the LLaMA-7B, LLaMA-13B, LLaMA2-7B, and LLaMA3-8B models. Here we provide proofs for the results in Section 4.For a vector a, let ∥a∥ be the ℓ 2 norm of a. For a deep learning model fine-tuned on n i.i.d. samples (x(i) i , y (i) i ) ⊂ R p × R q ,we say an event F occurs with high probability when P(F) = 1 -exp -Ω(log 2 (n + p + q)) .We consider multivariate regression task. Using n i.i.d. samples (x(i) i , y (i) i ) ⊂ R p × R q fromin-distribution task, we fine-tune a pre-trained network f pre : R p → R q for better prediction.Deep Linear Networks We consider deep linear networks of the form x → W L W L-1 . . . W 1 x : R d → R p , where W ℓ ∈ R d ℓ ×d ℓ-1 , with d L = q and d 0 = p. In comparison to multi-head attention transformers, each row of W ℓ can be viewed as corresponding to the parameters in a single head. Let f pre (x) = W pre L W pre L-1 . . . W pre 1 x : R p → R q represent a pre-trained neural network. We denoteW pre ℓ := W pre L W pre L-1 . . . W pre ℓ ∈ R d L ×d ℓ-1as the weights up to the ℓ-th layer, andW pre ℓ := W pre ℓ W pre ℓ-1 . . . W pre 1 ∈ R d ℓ ×d0as the weights above the ℓ-th layer, with the promise that W pre 0 = I. Deep linear networks have been widely used to facilitate the theoretical analysis of modern complex deep neural networks [57, 30, 43, 22, 34, 5] .We employ ℓ 2 distance as the error metric. Given a pre-trained network f pre , we finetune its ℓ-th layer by minimizing the empirical in-distribution riskR (i) n (f ) := (1/n) i∈[n] ∥y (i) i - f (x (i) i )∥ 2 , where (x (i) i , y (i) i ) ⊂ R p ×R q are n i.i.d. observations from in-distribution task. More specifically, we consider a class of rank-d adaptation defined asEQUATIONwhere U ∈ R d ℓ ×d and V ∈ R d ℓ-1 ×d are parameters to fine-tune. Note that by regarding multiple consecutive layers as a single layer, our settings can be extended to multi-layer fine-tuning.We specifically compare two fine-tuning methods: LoRA and S 2 FT.• LoRA. For a fixed ℓ ∈ [L], and low-rankness level 1 ≤ r ≤ min{d ℓ , d ℓ-1 }, we train the lowrank matrices (U, V ) in ( 4) by minimizing the empirical in-distribution risk via gradient descent. Motivated from the previous results that gradient descent has implicit regularization [74, 19, 5] , we directly consider the minimum norm solutions:EQUATION• S 2 FT. For a fixed ℓ ∈ [L], and a sparsity level s = ⌊r • d ℓ +d ℓ-1 d ℓ-1 ⌋, we train only V in (4) with the fixed choice of U ← U S 2 FT S := [e a1 ; e a2 ; . . . ; e as ], which specifies s channels to fine-tune, whereS = {a 1 , a 2 , . . . , a s } ⊂ [d ℓ ]. Here e a is the standard basis vector with the a-th entry being 1. We minimize the empirical in-distribution risk via gradient descent. Similar to LoRA, we consider the following minimum norm solution:EQUATIONData Generating Process As a simplification of the data generating process, we consider multiple linear regression. Assume that the in-distribution data (x (i) , y (i) ) ∈ R p+q and out-of-distribution data (x (o) , y (o) ) ∈ R p+q are generated according toEQUATIONwhere B (k) ∈ R q×p , and ϵ (k) ∈ R q is the error term satisfyingE[ϵ (k) |x (k) ] = 0. Assume that Σ (k) ϵ := E[ϵ (k) ϵ (k)⊤ ] ∈ R q×q exists and E[x (k) ] = 0. The signal covariance matrix is denoted by Σ (k) x := E[x (k) x (k)⊤ ] ∈ R p×p .We define the in-distribution and out-of-distribution risks of f : R p → R q as:R (k) (f ) = E[∥y (k) -f (x (k) )∥], k ∈ {i, o}.For notational brevity, we can writeW pre = W pre L ∈ R q×p . Let X (i) := (x (i) 1 , . . . , x (i) n ) ∈ R p×n , Y (i) := (y (i) 1 , . . . , y (i) n ) ∈ R q×n , and E (i) = (ϵ (i) 1 , . . . , ϵ (i) n ) := Y (i) -B (i) X (i) ∈ R q×n . Denote the in-distribution sample covariance matrices by Σ(i) x := (1/n)X (i) X (i)⊤ , Σ(i) ϵ := (1/n)E (i) E (i)⊤ , Σ(i) x,ϵ := (1/n)X (i) E (i)⊤ , Σ(i) ϵ,x = Σ(i)⊤ x,ϵ . Define Σ(k) x,ϵ = (X (i)⊤ ) † E (i)⊤ , Â := (W pre ℓ-1 Σ(i) x W pre⊤ ℓ-1 ) 1/2 , A := (W pre ℓ-1 Σ (i) x W pre⊤ ℓ-1 ) 1/2 , Φ ′ := Φ * (W pre ℓ+1 ), Φ ′′ S := Φ * (W pre ℓ+1 U S 2 FT S ), D = B (i) -W pre , D := B (i) -W pre + Σ(i) ϵ,x . Also define M := Φ ′⊤ DΣ (i) x W pre⊤ ℓ-1 A † and M := Φ ′⊤ D Σ(i) x W pre⊤ ℓ-1 Â † .Let Ψ′ := Ψ * ( Â), andG (i,o) ℓ := (W pre ℓ Σ (i)1/2 x ) † W pre ℓ Σ (o)1/2 xbe a matrix that captures the covariate shift at the ℓ-th layer.We consider fine-tuning the ℓ-th (ℓ ∈ [L]) layer of the pre-trained deep linear network f pre (x) = W pre L W pre L-1 . . . W pre 1 x using in-distribution observations (x(i) i , y (i) i ) i∈[n] .To measure the performance of models, we define the excess risks of f for the task k ∈ {i, o} asE (k) (f ) := E[∥y (k) -f (x (k) )∥ 2 ] -inf f ′ E[∥y (k) -f ′ (x (k) )∥ 2 ], where the infimum is taken over all square integrable functions.We assume that W pre ℓ-1 Σ (i)x W pre⊤ ℓ-1 ̸ = 0, since otherwise W pre ℓ-1 x (i) = 0 almost surely and fine-tuning the ℓ-th layer does not improve the performance of pre-trained model. Define the in-distribution prediction residuals for pre-trained model f pre by Σ (i)f := E[(B (i) x (i) -W pre x (i) )(B (i) x (i) -W pre x (i) ) ⊤ ]. Note that E (i) (f pre ) = tr Σ (i) f. We also assume that ∥Σ(i) f ∥ op > 0. Since otherwise E (i) (f pre ) = ∥Σ (i) f ∥ 2F = 0 and there is no room for improvement from pre-trained model. We introduce several assumptions. Assumption E.1 (Sub-Gaussianity). Assume that there exist some constants c 1 , c 2 ∈ (0, ∞) such that (x (i) , ϵ (i) ) in the model 7 satisfiesγ ⊤ Σ (i) x γ ≥ c 1 ∥γ ⊤ x (i) ∥ 2 ψ2 , and γ ′⊤ Σ (i) ϵ γ ′ ≥ c 2 ∥γ ′⊤ ϵ (i) ∥ 2 ψ2, for any γ ∈ R d and γ ′ ∈ R p , where ∥y∥ ψ2 is the sub-Gaussian norm defined as∥y∥ ψ2 := inf{υ > 0 : E[exp y 2 /υ 2 ] ≤ 2}for a random variable y taking values in R. Assumption E.2 (Sufficiently Many Observations). Assume thatn ≫ (κ 4 * (A)r e (A 2 ) + κ 2 * (Σ (i) x )r e (Σ (i) x ) + r e (DΣ (i) x D ⊤ )) log 2 (n + d + p), n ≫ ∥Σ (i) ϵ ∥ op ∥DΣ (i) x D ⊤ ∥ op (r e (Σ (i) ϵ ) + r e (A 2 )) log 2 (n + d + p),andEQUATIONx )(r e (ΣEQUATIONx )) r e (A 2 ) log 2 (n + d + p).). Assume that there exists some constant C g > 0 such thatλ s (Φ ′⊤ DΣ (i) x W pre⊤ ℓ-1 A † ) λ s (Φ ′⊤ DΣ (i) x W pre⊤ ℓ-1 A † ) -λ s+1 (Φ ′⊤ DΣ (i) x W pre⊤ ℓ-1 A † ) ≲ C g holds.Assumption E.3 is necessary to identify the rank-s approximation of M , which is used to derive the risk of LoRA. Assumption E.4 (Approximate Sparsity of Heads). Assume that there exists someS 0 ⊂ [d ℓ ] with |S 0 | ≤ s and δ > 0 such that a∈[d ℓ ]\S0 ∥e ⊤ a (W pre ℓ+1 ) † (B (i) -W pre )Σ (i)1/2 x ∥ 2 ≤ δ 2 ∥(W pre ℓ+1 ) † (B (i) -W pre )Σ (i)1/2 x ∥ 2 F holds. Assumption E.5 (Distribution Shift). Assume that Σ (i) x = Σ (o) x = Σ x for some Σ x ∈ R d×d and that ∥Φ ⊤ * (W pre ℓ+1 U S 2 FT S )(B (o) -B (i) )Σ 1/2 x ∥ 2 F ≤ ε 2 E (o) (f pre ) for some ε > 0. Assumption E.6 (Condition Number). Assume that κ * (M ) ≲ 1, κ * (W pre ℓ+1 ) ≲ 1, κ * (Σ (i) f ) ≲ 1 and κ * (W pre ℓ-1 Σ (i)x W pre⊤ ℓ-1 ) ≲ 1. Note that Assumption E.6 is not essential to our analysis.We first demonstrate that LoRA and S 2 FT exhibit comparable memorization abilities. Next, we present a formal restatement of 4.2 that combine Theorems E.10, E.11, E.13, E.15, and Lemma E.14. Theorem E.7. Suppose that Assumptions E.1, E.2, E.3, E.4, and E.6 hold. Choose S such that S ⊃ S 0 holds. Let U LoRA , V LoRA be the LoRA adaptation matrices defined in (5) . Let V S 2 FT be the S 2 FT adaptation matrices given U S 2 FT S defined in (6) . Then, for all sufficiently large n, the following holds with probability 1 -exp -Ω(log 2 (n + d + p)) : for any η > 0,E (i) (f ℓ,U S 2 FT S ,V S 2 FT ) ≤ (1 + η)(T S 2 FT bias ) 2 + (1 + η -1 )(T S 2 FT variance ) 2 , E (i) (f ℓ,U LoRA ,V LoRA ) ≤ (1 + η)(T LoRA bias ) 2 + (1 + η -1 )(T LoRA variance ) 2 , where 0 ≤ (T LoRA bias ) 2 -E (i) (f full ℓ ) ≤ (T S 2 FT bias ) 2 -E (i) (f full ℓ ) ≲ δ 2 E (i) (f pre ), (T S 2 FT variance ) 2 ≲ (∥Σ (i) ϵ ∥ op + ∥Σ (i) f ∥ op ) sd ℓ-1 log 2 (n + p + q) n , (T LoRA variance ) 2 ≲ (∥Σ (i) ϵ ∥ op + ∥Σ (i) f ∥ op ) r(d ℓ + d ℓ-1 ) log 2 (n + p + q) n .Theorem E.8 (Restatement of Theorem 4.2). Consider the limit n → ∞. Suppose that Assumption E.5 holds. Let U LoRA , V LoRA be the LoRA adaptation matrices defined in (15) . Let V S 2 FT be the S 2 FT adaptation matrices given U S 2 FT S defined in (25) .If B (i) = W pre ℓ+1 BW pre ℓ-1 holds for some B(i) ∈ R d ℓ ×d ℓ-1 , and s ≤ rank(Σ (i) f ), then, E (o) (f ℓ,U S 2 FT S ,V S 2 FT ) ≤ (1 + 3ε 2 )E (o) (f pre ), E (o) (f ℓ,U LoRA ,V LoRA ) ≥ ∥(B (o) -B (i) )Σ 1/2 x ∥ 2 F .Intuition of the proof of Theorem E.8. LoRA forgets pre-trained tasks due to its model complexity.Consider the simplest low-rank adaptation to a single-layer linear network:∆ 1 ∈ arg min ∆ ′ 1 ∈R d 1 ×d 0 rank(∆ ′ 1 )=s E[∥y (i) -(W pre 1 + ∆ ′ 1 )x (i) ∥ 2 ].Assume that Σ (i)x = I, then we can show that the solution is ∆ 1 = SVD s (B (i) -W pre 1 ). Under the condition that the rank of B (i) -W pre 1 is smaller than, or comparable to s, LoRA fine-tuned model can learn the in-distribution best regressor in ℓ 2 sense, since(W pre 1 + ∆ 1 )x ≈ B (i) x = E[y (i) |x (i) = x].Hence it makes LoRA fine-tuned model vlunerable to distribution shift.On the other hand, we model S 2 FT as fine-tuning only a few heads:∆ 1 ∈ arg min ∆ ′ 1 = a∈S eav ⊤ a ,va∈R d 0 E[∥y (i) -(W pre 1 + ∆ ′ 1 )x (i) ∥ 2 ].Although S 2 FT is a special case of LoRA, the constraint on the direction of low-rank matrix prevents overfitting to the in-distribution task. To see this, note that a sparse fine-tuned model can be written as(W pre 1 + ∆ 1 )x = W pre 1 x + a∈S e a e ⊤ a (B (i) -W pre 1 )x = a∈S ce a e ⊤ a W (U LoRA , V LoRA ) ∈ arg min (U,V )∈R d ℓ ×s ×R d ℓ-1 ×s ∥(U, V )∥ 2 F s.t. (U, V ) minimizes R (i) n (f ℓ,U,V ).Then, the low-rank adaptation matrix satisfiesEQUATIONE (k) (f ℓ,U LoRA ,V LoRA ) = tr B (k) -W pre -SVD s (W pre ℓ+1 (W pre ℓ+1 ) † D Σ(i) x W pre⊤ ℓ-1 Â † ) Â † W pre ℓ-1 Σ (k) x • B (k) -W pre -SVD s (W pre ℓ+1 (W pre ℓ+1 ) † D Σ(i) x W pre⊤ ℓ-1 Â † ) Â † W pre ℓ-1 ⊤ for k ∈ {i, o}.Proof of Lemma E.9. The empirical risk of f ℓ,U,V for the in-distribution task can be written asEQUATIONSinceEQUATIONwhere we used(I -Â Â † )W pre ℓ-1 Σ(i)1/2 x = 0. From (9), minimizing R (i) n (f ℓ,U,V) is equivalent to minimizing the norm:EQUATIONwhere A 1 , A 2 ∈ R d ℓ ×d ℓ-1 are arbitrary matrices. Since we particularly consider the minimum norm solution, we must have A 1 = 0 and A 2 = 0. HenceW pre ℓ+1 U LoRA V LoRA⊤ W pre ℓ-1 = SVD s (W pre ℓ+1 (W pre ℓ+1 ) † D Σ(i) x W pre⊤ ℓ-1 Â † ) Â † W pre ℓ-1 .Therefore, the excess risk for k ∈ {i, o} becomesE (k) (f ℓ,U LoRA ,V LoRA ) = E B (k) x (k) -W pre ℓ+1 (W pre ℓ + U LoRA V LoRA⊤ )W pre ℓ-1 x (k) 2 = tr B (k) -W pre -SVD s (W pre ℓ+1 (W pre ℓ+1 ) † D Σ(i) x W pre⊤ ℓ-1 Â † ) Â † W pre ℓ-1 Σ (k) x • B (k) -W pre -SVD s (W pre ℓ+1 (W pre ℓ+1 ) † D Σ(i) x W pre⊤ ℓ-1 Â † ) Â † W pre ℓ-1 ⊤ .This concludes the proof.Let E (i) (f full ℓ ) denote the excess risk of f pre after fine-tuning all the parameters of the ℓ-th layer under population in-distribution risk. Theorem E.10 (Restatement of Theorem E.7: LoRA Part). Suppose that Assumptions E.1, E.2 and E.3 hold. Then, the following holds with probability 1 -exp -Ω(log 2 (n + d + p)) . For any η > 0,E (i) (f ℓ,U LoRA ,V LoRA ) ≤ (1 + η)(T LoRA bias ) 2 + (1 + η -1 )(T LoRA variance ) 2, whereEQUATION(T LoRA variance ) 2 ≲ C 2 κ 4 * (M )∥Σ (i) ϵ ∥ op κ 2 * (A) s(r e (Φ ′⊤ Σ (i) ϵ Φ ′ ) + r e (A 2 )) log 2 (n + d + p) n + C 2 κ 4 * (M )∥DΣ (i) x D ⊤ ∥ op s(κ 2 * (A)r e (Φ ′⊤ DΣ (i) x D ⊤ Φ ′ ) + κ 6 * (A)r e (A 2 )) log 2 (n + d + p) n .Note that the first term on the right hand side of ( 11) depends on the rank of residual matrixΣ (i) f = DΣ (i)x D ⊤ . It becomes zero when rank(Σ (i) f ) ≤ s and small when s/ rank(Σ(i) f ) ≈ 1. Proof of Theorem E.10. Let W LoRA ℓ := W pre ℓ+1 U LoRA V LoRA⊤ .From Lemma E.9, we haveE (i) (f ℓ,U LoRA ,V LoRA ) = tr (D -W LoRA ℓ W pre ℓ-1 )Σ (i) x (D -W LoRA ℓ W pre ℓ-1 ) ⊤ = ∥(W LoRA ℓ AA † W pre ℓ-1 -D)Σ (i)1/2 x ∥ 2 F ,where we used(I -AA † )W pre ℓ-1 Σ (i)1/2 x = 0.From Lemma E.9W LoRA ℓ A = SVD s (W pre ℓ+1 (W pre ℓ+1 ) † D Σ(i) x W pre⊤ ℓ-1 Â † ) Â † A.This gives∥(W LoRA ℓ AA † W pre ℓ-1 -D)Σ (i)1/2 x ∥ F ≤ ∥(W LoRA ℓ A -SVD s (W pre ℓ+1 (W pre ℓ+1 ) † DΣ (i) x W pre⊤ ℓ-1 A † ))A † W pre ℓ-1 Σ (i)1/2 x ∥ F + ∥SVD s (W pre ℓ+1 (W pre ℓ+1 ) † DΣ (i) x W pre⊤ ℓ-1 A † )A † W pre ℓ-1 Σ (i)1/2 x -DΣ (i)1/2 x ∥ F =: T LoRA variance + T LoRA bias .We bound T LoRA variance and T LoRA bias separately.Bound T LoRA variance . For the term T LoRA variance , sinceA † W pre ℓ-1 Σ (i) x W pre⊤ ℓ-1 A † = A † A 2 A † , T LoRA variance = ∥SVD s (W pre ℓ+1 (W pre ℓ+1 ) † D Σ(i) x W pre⊤ ℓ-1 Â † ) Â † A -SVD s (W pre ℓ+1 (W pre ℓ+1 ) † DΣ (i) x W pre⊤ ℓ-1 A † )A † A∥ F . Therefore, T LoRA variance ≤ ∥SVD s (W pre ℓ+1 (W pre ℓ+1 ) † DΣ (i) x W pre⊤ ℓ-1 A † )A † A -SVD s (W pre ℓ+1 (W pre ℓ+1 ) † D Σ(i) x W pre⊤ ℓ-1 Â † )A † A∥ F + ∥SVD s (W pre ℓ+1 (W pre ℓ+1 ) † D Σ(i) x W pre⊤ ℓ-1 Â † )( Â † A -A † A)∥ F =: T LoRA variance,1 + T LoRA variance,2 ,We first bound T LoRA variance,1 . From Lemma F.1 and Assumption E.3, we haveT LoRA variance,1 ≤ ∥SVD s ( M ) -SVD s (M )∥ F ≤ κ 2 * (M ) λ s (M ) λ s (M ) -λ s+1 (M ) √ s∥ M -M ∥ op ≤ κ 2 * (M )C √ s∥ M -M ∥ op , where M = W pre ℓ+1 (W pre ℓ+1 ) † D Σ(i) x W pre⊤ ℓ-1 Â † and M = W pre ℓ+1 (W pre ℓ+1 ) † DΣ (i) x W pre⊤ ℓ-1 A † . From Lemma F.3, ∥ M -M ∥ op ≤ ∥Φ ′⊤ D Σ(i) x W pre⊤ ℓ-1 -Φ ′⊤ DΣ (i) x W pre⊤ ℓ-1 ∥ op ∥ Â † ∥ op + ∥DΣ (i) x W pre⊤ ℓ-1 ∥ op ∥ Â † -A † ∥ op ≲ ∥Σ (i) ϵ ∥ 1/2 op κ * (A) (r e (Φ ′⊤ Σ (i) ϵ Φ ′ ) + r e (A 2 )) log 2 (n + d + p) n + ∥DΣ (i) x D ⊤ ∥ 1/2 op κ * (A) (r e (Φ ′⊤ DΣ (i) x D ⊤ Φ ′ ) + r e (A 2 )) log 2 (n + d + p) n + ∥DΣ (i) x W pre⊤ ℓ-1 ∥ op κ * (A) λ * (A) r e (A 2 ) log 2 (n + d + p) n ≲ ∥Σ (i) ϵ ∥ 1/2 op κ * (A) (r e (Φ ′⊤ Σ (i) ϵ Φ ′ ) + r e (A 2 )) log 2 (n + d + p) n + ∥DΣ (i) x D ⊤ ∥ 1/2 op (κ 2 * (A)r e (Φ ′⊤ DΣ (i) x D ⊤ Φ ′ ) + κ 4 * (A)r e (A 2 )) log 2 (n + d + p) nholds on the event F, where we used ∥DΣ(i) x W pre⊤ ℓ-1 ∥ op ≤ ∥DΣ (i)1/2 x ∥ op ∥A∥ op . Hence T LoRA variance,1 ≲ C g κ 2 * (M )∥Σ (i) ϵ ∥ 1/2 op κ * (A) s(r e (Φ ′⊤ Σ (i) ϵ Φ ′ ) + r e (A 2 )) log 2 (n + d + p) n + C g κ 2 * (M )∥DΣ (i) x D ⊤ ∥ 1/2 op s(κ 2 * (A)r e (Φ ′⊤ DΣ (i) x D ⊤ Φ ′ ) + κ 4 * (A)r e (A 2 )) log 2 (n + d + p) n .Next we bound T LoRA variance,2 . Again from Lemma F.3,T LoRA variance,2 ≤ √ s∥ D Σ(i) x W pre⊤ ℓ-1 ∥ op ∥ Â † ∥ op ∥ Â † -A † ∥ op ∥A∥ op ≲ ∥DΣ (i)1/2 x ∥ op ∥Σ (i)1/2 x W pre⊤ ℓ-1 ∥ op κ 2 * (A) λ * (A) sr e (A 2 ) log 2 (n + d + p) n = ∥DΣ (i)1/2 x ∥ op κ 3 * (A)sr e (A 2 ) log 2 (n + d + p) n holds on the event F. Therefore,EQUATIONhold with high probability.Bound T LoRA bias . Note that (T LoRA bias ) 2 = ∥SVD s (M )A † W pre ℓ-1 Σ (i)1/2 x -DΣ (i)1/2 x ∥ 2 F = ∥ SVD s (M )A † W pre ℓ-1 Σ (i)1/2 x -Φ ′ Φ ′⊤ DΣ (i) x W pre⊤ ℓ-1 (A 2 ) † W pre ℓ-1 Σ (i)1/2 x =:T1 ∥ 2 F + ∥ DΣ (i)1/2 x (I -Σ (i)1/2 x W pre⊤ ℓ-1 (A 2 ) † W pre ℓ-1 Σ (i)1/2 x ) =:T2 ∥ 2 F + ∥ (I -Φ ′ Φ ′⊤ )DΣ (i) x W pre⊤ ℓ-1 (A 2 ) † W pre ℓ-1 Σ (i)1/2 x =:T3 ∥ 2 Fwhere the second equality follows from the fact that cross terms are zero, i.e., trEQUATIONEQUATIONwhere the last inequality follows since∥DΣ (i)1/2 x ∥ 2 F = ∥Λ * (DΣ (i)1/2 x )∥ 2 F ≥ rank(DΣ (i)1/2 x )λ 2 * (DΣ (i)1/2 x ) = rank(DΣ (i)1/2 x ) κ 2 * (DΣ (i)1/2 x)∥DΣ (i)1/2 x ∥ 2 op .Summary Note that for any η > 0, (T LoRA variance + T LoRA bias) 2 ≤ (1 + η)(T LoRA bias ) 2 + (1 + 1/η)(T LoRA variance ) 2 holds. Therefore, E (i) (f ℓ,U LoRA ,V LoRA ) ≤ (1 + η)(T LoRA bias ) 2 + (1 + η -1 )(T LoRA variance ) 2 .Combined with ( 12), (13) , and ( 14), this concludes the proof.We define the low-rank matrix obtained by LoRA under population in-distribution risk asEQUATIONTheorem E.11 (Restatement of Theorem E.8: LoRA Part).EQUATIONE (o) (f ℓ,U LoRA ∞ ,V LoRA ∞ ) ≲ ∥(I -Φ ′ Φ ′⊤ )B (o) Σ (o)1/2 x ∥ 2 F + ∥(B (o) -B (i) )Σ (i)1/2 x ∥ 2 F ∥G (i,o) ℓ-1 ∥ 2 op + ∥(B (o) -W pre )(Σ (o)1/2 x -Σ (i)1/2 x G (i,o) ℓ-1 )∥ F + 0 ∨ (rank(DΣ (i) x D ⊤ ) -s) rank(DΣ (i) x D ⊤ ) κ 2 * (DΣ (i) x D ⊤ )∥G (i,o) ℓ-1 ∥ 2 op E (i) (f pre ).Furthermore, for any η ∈ (0, 1),EQUATIONProof of Theorem E.11. With a slight modification to the proof of Lemma E.9, it follows thatEQUATIONRecall thatM := Φ ′ Φ ′⊤ DΣ (i) x W pre⊤ ℓ-1 A † . Then, (B (o) -W pre )Σ (o)1/2 x -SVD s (Φ ′ Φ ′⊤ DΣ (i) x W pre⊤ ℓ-1 A † )A † W pre ℓ-1 Σ (o)1/2 x F ≤ (B (o) -W pre )Σ (o)1/2 x -Φ ′ Φ ′⊤ DΣ (i) x W pre⊤ ℓ-1 (A 2 ) † W pre ℓ-1 Σ (o)1/2 x F + ∥M A † W pre ℓ-1 Σ (o)1/2 x -SVD s (M )A † W pre ℓ-1 Σ (o)1/2 x ∥ F = (B (o) -W pre )Σ (o)1/2 x -Φ ′ Φ ′⊤ DΣ (i)1/2 x (W pre ℓ-1 Σ (i)1/2 x ) † W pre ℓ-1 Σ (o)1/2 x F + ∥M A † W pre ℓ-1 Σ (o)1/2 x -SVD s (M )A † W pre ℓ-1 Σ (o)1/2 x ∥ F ≤ ∥(I -Φ ′ Φ ′⊤ )B (o) Σ (o)1/2 x ∥ F + ∥Φ ′ Φ ′⊤ (B (o) -B (i) )Σ (i)1/2 x G (i,o) ℓ-1 ∥ F + ∥Φ ′ Φ ′⊤ (B (o) -W pre )(Σ (o)1/2 x -Σ (i)1/2 x G (i,o) ℓ-1 )∥ F + ∥M A † W pre ℓ-1 Σ (o)1/2 x -SVD s (M )A † W pre ℓ-1 Σ (o)1/2 x ∥ F ≤ ∥(I -Φ ′ Φ ′⊤ )B (o) Σ (o)1/2 x ∥ F + ∥(B (o) -B (i) )Σ (i)1/2 x ∥ F ∥G (i,o) ℓ-1 ∥ op + ∥(B (o) -W pre )(Σ (o)1/2 x -Σ (i)1/2 x G (i,o) ℓ-1 )∥ F + ∥M -SVD s (M )∥ F ∥A † W pre ℓ-1 Σ (o)1/2 x ∥ op ,where we used Φ ′ Φ ′⊤ W pre = W pre . From ( 14), we have{E (o) (f ℓ,U LoRA ∞ ,V LoRA ∞ )} 1/2 ≤ ∥(I -Φ ′ Φ ′⊤ )B (o) Σ (o)1/2 x ∥ F + ∥(B (o) -B (i) )Σ (i)1/2 x ∥ F ∥G (i,o) ℓ-1 ∥ op + ∥(B (o) -W pre )(Σ (o)1/2 x -Σ (i)1/2 x G (i,o) ℓ-1 )∥ F + ∥G (i,o) ℓ-1 ∥ op κ * (DΣ (i) x D ⊤ ) 0 ∨ (rank(DΣ (i) x D ⊤ ) -s) rank(DΣ (i)1/2 x ) E (i) (f pre ),where we used∥A † W pre ℓ-1 Σ (o)1/2 x ∥ op = ∥G (i,o)ℓ-1 ∥ op . This gives the first claim. Using 2 tr AB ⊤ ≥ -η∥A∥ 2 F -(1/η)∥B∥ 2 F for any η > 0 and any matrices A, B of the same shape, ( 17) can be rewritten asEQUATIONChoose η ∈ (0, 1). By a similar argument as above, and using Φ ′ Φ ′⊤ W pre = W pre , we can show that∥T 1 + T 2 + T 3 ∥ 2 F ≤ 3∥T 1 ∥ 2 F + 3∥T 2 ∥ 2 F + 3∥T 3 ∥ 2 F ≤ 3∥(I -Φ ′ Φ ′⊤ )B (i) Σ (o)1/2 x ∥ 2 F + 3∥(B (i) -W pre )(Σ (o)1/2 x -Σ (i)1/2 x G (i,o) ℓ-1 )∥ 2 F + 3 0 ∨ (rank(DΣ (i) x D ⊤ ) -s) rank(DΣ (i)1/2 x ) κ 2 * (DΣ (i) x D ⊤ )∥G (i,o) ℓ-1 ∥ op E (i) (f pre ),where we used (14) again. This concludes the proof.E.6 Proofs for Structured Sparse Fine-tuning E.6.1 Excess Risk of Structured Sparse Fine-tuning Lemma E.12 (Excess Risk). Given S ⊂ [d ℓ ], consider the minimum norm solutionV S 2 FT ∈ arg min V ∈R d ℓ-1 ×s ∥V ∥ 2 F s.t. V minimizes R (i) n (f ℓ,U S 2 FT S ,V ).Then, the low-rank adaptation matrix satisfiesEQUATIONandE (k) (f ℓ,U S 2 FT S ,V S 2 FT ) = tr B (k) -W pre -W pre ℓ+1 U S 2 FT S (W pre ℓ+1 U S 2 FT S ) † D Σ(i) x W pre⊤ ℓ-1 ( Â † ) 2 W pre ℓ-1 Σ (k) x • B (k) -W pre -W pre ℓ+1 U S 2 FT S (W pre ℓ+1 U S 2 FT S ) † D Σ(i) x W pre⊤ ℓ-1 ( Â † ) 2 W pre ℓ-1 ⊤ for k ∈ {i, o}. Proof. Since Σ(k) x,ϵ = (1/n)X (k) E (k)⊤ and Σ(k) x = (1/n)X (k) X (k)⊤ , we have Σ(k) x,ϵ = Σ(k) x (X (k)⊤ ) † E (k)⊤ =: Σ(k) x Σ(k)x,ϵ . Similar to (9), we haveR (i) n (f ℓ,U S 2 FT S ,V ) = ∥W pre ℓ+1 U S 2 FT S V ⊤ Â -D Σ(i) x W pre⊤ ℓ-1 Â † ∥ 2 F -∥ D Σ(i) x W pre⊤ ℓ-1 Â † ∥ 2 F + tr D Σ(i) x D ⊤ + 2 tr D Σ(i) x,ϵ + tr Σ(i) ϵ . Thus minimizing R (i) n (f ℓ,U S 2 FT S ,V) is equivalent to minimizing the norm∥W pre ℓ+1 U S 2 FT S V ⊤ Â -D Σ(i) x W pre⊤ ℓ-1 Â † ∥ 2 F (20) = ∥W pre ℓ+1 U S 2 FT S V ⊤ Â -W pre ℓ+1 U S 2 FT S (W pre ℓ+1 U S 2 FT S ) † D Σ(i) x W pre⊤ ℓ-1 Â † ∥ 2 F + ∥(I -(W pre ℓ+1 U S 2 FT S )(W pre ℓ+1 U S 2 FT S ) † ) D Σ(i) x W pre⊤ ℓ-1 Â † ∥ 2 F .By the same argument as in the proof of Lemma E.9, the minimum norm solution V S 2 FT is obtained byV S 2 FT = ( Â † ) 2 W pre ℓ-1 Σ(i) x D⊤ (U S 2 FT⊤ S W pre⊤ ℓ+1 ) † .The excess risk for k ∈ {i, o} becomesE (k) (f ℓ,U S 2 FT S ,V S 2 FT ) = E B (k) x (k) -W pre ℓ+1 (W pre ℓ + U S 2 FT S V S 2 FT⊤ )W pre ℓ-1 x (k) 2 = tr B (k) -W pre -W pre ℓ+1 U S 2 FT S (W pre ℓ+1 U S 2 FT S ) † D Σ(i) x W pre⊤ ℓ-1 ( Â † ) 2 W pre ℓ-1 Σ (k) x • B (k) -W pre -W pre ℓ+1 U S 2 FT S (W pre ℓ+1 U S 2 FT S ) † D Σ(i) x W pre⊤ ℓ-1 ( Â † ) 2 W pre ℓ-1 ⊤ .This concludes the proof. For any η > 0,E (i) (f ℓ,U S 2 FT S ,V S 2 FT ) ≤ (1 + η)(T S 2 FT bias ) 2 + (1 + η -1 )(T S 2 FT variance ) 2 ,where T S 2 FT bias ≥ T LoRA bias andEQUATION(T S 2 FT variance ) 2 ≲ ∥Σ (i) ϵ ∥ op κ 2 * (A) s(r e (Φ ′′⊤ S Σ (i) ϵ Φ ′′ S ) + r e (A 2 )) log 2 (n + d + p) n + ∥DΣ (i) x D ⊤ ∥ op s(κ 2 * (A)r e (Φ ′′⊤ S DΣ (i) x D ⊤ Φ ′′ S ) + κ 8 * (A)r e (A 2 )) log 2 (n + d + p) n .Note that the term∥(Φ ′ Φ ′⊤ -Φ ′′ S Φ ′′⊤ S )Φ * (DΣ (i)1/2 x)∥ op in (21) measures the distance between subspaces spanned by Φ ′ and Φ ′′ S in a label space, weighted by Φ * (Σ(i) f ).In high level, this quantity shows the closeness between the ℓ-th layer full fine-tuning and S 2 FT. It takes small values when the important 'heads' for residual prediction are sparsely distributed among all heads. This aligns with the intuition that S 2 FT only selectively fine-tunes small number of coordinates, and thus relying on the information contained in those coordinates.Proof of Theorem E. 13 . By the same argument as in the proof of Theorem E.10 combined with Lemma E.12, we haveEQUATION∥(W pre ℓ+1 U S 2 FT S V S 2 FT⊤ AA † W pre ℓ-1 -D)Σ (i)1/2 x ∥ F ≤ ∥W pre ℓ+1 U S 2 FT S (W pre ℓ+1 U S 2 FT S ) † ( D Σ(i) x W pre⊤ ℓ-1 ( Â2 ) † -DΣ (i) x W pre⊤ ℓ-1 (A 2 ) † )A∥ F + ∥W pre ℓ+1 U S 2 FT S (W pre ℓ+1 U S 2 FT S ) † DΣ (i) x W pre⊤ ℓ-1 (A 2 ) † W pre ℓ-1 Σ (i)1/2 x -DΣ (i)1/2x ∥ F =: T S 2 FT variance + T S 2 FT bias . We bound T S 2 FT variance and T S 2 FT bias separately.Bound T S 2 FT variance . Note thatT S 2 FT variance = ∥W pre ℓ+1 U S 2 FT S (W pre ℓ+1 U S 2 FT S ) † D Σ(i) x W pre⊤ ℓ-1 ( Â † ) 2 A -W pre ℓ+1 U S 2 FT S (W pre ℓ+1 U S 2 FT S ) † DΣ (i) x W pre⊤ ℓ-1 A † ∥ F ≤ ∥W pre ℓ+1 U S 2 FT S (W pre ℓ+1 U S 2 FT S ) † DΣ (i) x W pre⊤ ℓ-1 A † -W pre ℓ+1 U S 2 FT S (W pre ℓ+1 U S 2 FT S ) † D Σ(i) x W pre⊤ ℓ-1 A † ∥ F + ∥W pre ℓ+1 U S 2 FT S (W pre ℓ+1 U S 2 FT S ) † D Σ(i) x W pre⊤ ℓ-1 (( Â † ) 2 -(A † ) 2 )A∥ F =: T S 2 FT variance,1 + T S 2 FT variance,2 .For the term T S 2 FT variance,1 , using Lemma F.3,T S 2 FT variance,1 ≤ 2 √ s∥Φ ′′⊤ S DΣ (i) x W pre⊤ ℓ-1 -Φ ′′⊤ S D Σ(i) x W pre⊤ ℓ-1 ∥ op ∥A † ∥ op ≲ ∥Σ (i) ϵ ∥ 1/2 op κ * (A) s(r e (Φ ′′⊤ S Σ (i) ϵ Φ ′′ S ) + r e (A 2 )) log 2 (n + d + p) n + ∥DΣ (i) x D ⊤ ∥ 1/2 op κ * (A) s(r e (Φ ′′⊤ S DΣ (i) x D ⊤ Φ ′′ S ) + r e (A 2 )) log 2 (n + d + p) nholds on the event F, where the first inequality follows since the term inside the norm is at most rank-2s. Again from Lemma F.3,T S 2 FT variance,2 ≤ √ s∥Φ ′′⊤ S D Σ(i) x W pre⊤ ℓ-1 ∥ op ∥( Â † ) 2 -(A † ) 2 ∥ op ∥A∥ op ≲ ∥DΣ (i)1/2 x ∥ op ∥Σ (i)1/2 x W pre⊤ ℓ-1 ∥ op κ 3 * (A) λ * (A) sr e (A 2 ) log 2 (n + d + p) n = ∥DΣ (i)1/2 x ∥ op κ 4 * (A)sr e (A 2 ) log 2 (n + d + p) n holds on the event F. Therefore,EQUATION)Bound T S 2 FT bias . By the same argument as in the proof of Theorem E.10,EQUATIONwhere we used ∥DΣ(i) x W pre⊤ ℓ-1 A † ∥ 2 F ≤ ∥DΣ (i)1/2 x ∥ 2 F = E (i) (f pre ℓ ).We can verify T S 2 FT bias ≥ T LoRA bias by comparing ( 13) and ( 23), since SVD s (Φ ′ Φ ′⊤ DΣ (i)x W pre⊤ ℓ-1 A † ) is the best rank-s approximation of Φ ′ Φ ′⊤ DΣ (i) x W pre⊤ ℓ-1 A † and Φ ′′ S Φ ′′⊤ S DΣ (i)x W pre⊤ ℓ-1 A † is at most rank-s.Summary Note that for any η > 0, (T S 2 FT variance + T S 2 FT bias ) 2 ≤ (1 + η)(T S 2 FT bias ) 2 + (1 + 1/η)(T S 2 FT variance ) 2 holds. Thus (22) and (24) , this concludes the proof.E (i) (f ℓ,U S 2 FT S ,V S 2 FT ) ≤ (1 + η)(T S 2 FT bias ) 2 + (1 + η -1 )(T S 2 FT variance ) 2 . Combined withNext we characterize the bias terms T LoRA bias and T S 2 FT bias under sparsity assumption. Lemma E.14. Suppose that Assumption E.4 holds. Then, for a sparse fine-tuned network with the choice S ⊃ S 0 , it follows thatE (i) (f full ℓ ) ≤ (T LoRA bias ) 2 ≤ (T S 2 FT bias ) 2 ≤ E (i) (f full ℓ ) + δ 2 κ 2 * (W pre ℓ+1 )E (i) (f pre ).Proof. Note that Φ ′′ S Φ ′′⊤ S is a projection into a subspace, which is contained in a subspace projected by Φ ′ Φ ′⊤ . ThusEQUATIONF , where the second inequality follows from ∥Σ 4 and S ⊃ S 0 . The conclusion follows from ( 13) and ( 23).(i)1/2 x W pre⊤ ℓ-1 A † ∥ op ≤ 1, Assumption E.Given S ⊂ [d ℓ ] with |S| = s, we define the low-rank adaptation matrix obtained by S 2 FT under population in-distribution risk asEQUATION) Theorem E.15 (Restatement of Theorem E.8: S 2 FT Part). Fix S ⊂ [d ℓ ] with |S| = s. For V S 2 FT ∞ defined in (25), E (o) (f ℓ,U S 2 FT S ,V S 2 FT ∞ ) ≤ E (o) (f pre ) + 3 Φ ′′ S Φ ′′⊤ S (B (o) -B (i) )Σ (o)1/2 x 2 F + 3∥B (i) (Σ (o)1/2 x -Σ (i)1/2 x G (i,o) ℓ-1 )∥ 2 F + 3∥W pre ℓ ∥ 2 op ∥W pre ℓ-1 Σ (o)1/2 x -W pre ℓ-1 Σ (i)1/2 x G (i,o) ℓ-1 ∥ 2 F .Remark E.16. If there is no covariate shift, i.e., Σx = Σ (o)x = Σ x for some Σ x , Theorem E.15 further gives the boundE (o) (f ℓ,U S 2 FT S ,V S 2 FT ∞ ) ≤ E (o) (f pre ) + 3 Φ ′′ S Φ ′′⊤ S (B (o) -B (i) )Σ 1/2 x 2 F + 3∥B (i) Σ 1/2 x (I -(W pre ℓ-1 Σ 1/2 x ) † W pre ℓ-1 Σ 1/2 x ))∥ 2 F .Proof of Theorem E.15. With a slight modification to Lemma E.12, we obtainE (o) (f ℓ,U S 2 FT S ,V S 2 FT ∞ ) = tr B (o) -W pre -W pre ℓ+1 U S 2 FT S (W pre ℓ+1 U S 2 FT S ) † DΣ (i) x W pre⊤ ℓ-1 (A † ) 2 W pre ℓ-1 Σ (o) x • B (o) -W pre -W pre ℓ+1 U S 2 FT S (W pre ℓ+1 U S 2 FT S ) † DΣ (i) x W pre⊤ ℓ-1 (A † ) 2 W pre ℓ-1 ⊤ = (B (o) -W pre )Σ (o)1/2 x -Φ ′′ S Φ ′′⊤ S DΣ (i) x W pre⊤ ℓ-1 (A † ) 2 W pre ℓ-1 Σ (o)1/2 x 2 F = ∥(I -Φ ′′ S Φ ′′⊤ S )(B (o) -W pre )Σ (o)1/2 x ∥ 2 F + Φ ′′ S Φ ′′⊤ S (B (o) -W pre )Σ (o)1/2 x -DΣ (i)1/2 x (W pre ℓ-1 Σ (i)1/2 x ) † W pre ℓ-1 Σ (o)1/2 x =:T 2 F ,where we usedΣ (i)1/2 x W pre⊤ ℓ-1 (A † ) 2 W pre ℓ-1 Σ (o)1/2 x = (W pre ℓ-1 Σ (i)1/2 x ) † W pre ℓ-1 Σ (o)1/2 x . Note that ∥T ∥ F ≤ Φ ′′ S Φ ′′⊤ S B (o) Σ (o)1/2 x -B (i) Σ (i)1/2 x (W pre ℓ-1 Σ (i)1/2 x ) † W pre ℓ-1 Σ (o)1/2 x F + Φ ′′ S Φ ′′⊤ S W pre ℓ W pre ℓ-1 Σ (o)1/2 x -W pre ℓ-1 Σ (i)1/2 x (W pre ℓ-1 Σ (i)1/2 x ) † W pre ℓ-1 Σ (o)1/2 x F ≤ Φ ′′ S Φ ′′⊤ S (B (o) -B (i) )Σ (o)1/2 x F + Φ ′′ S Φ ′′⊤ S B (i) (Σ (o)1/2 x -Σ (i)1/2 x G (i,o) ℓ-1 ) F + Φ ′′ S Φ ′′⊤ S W pre ℓ (W pre ℓ-1 Σ (o)1/2 x -W pre ℓ-1 Σ (i)1/2 x G (i,o) ℓ-1 ) F .Therefore,E (o) (f ℓ,U S 2 FT S ,V S 2 FT ∞ ) = ∥(I -Φ ′′ S Φ ′′⊤ S )(B (o) -W pre )Σ (o)1/2 x ∥ 2 F + ∥T ∥ 2 F ≤ E (o) (f pre ) + 3 Φ ′′ S Φ ′′⊤ S (B (o) -B (i) )Σ (o)1/2 x 2 F + 3∥B (i) (Σ (o)1/2 x -Σ (i)1/2 x G (i,o) ℓ-1 )∥ 2 F + 3∥W pre ℓ ∥ 2 op ∥W pre ℓ-1 Σ (o)1/2 x -W pre ℓ-1 Σ (i)1/2 x G (i,o) ℓ-1 ∥ 2 F ,where we used x + y + z ≤ 3x 2 + 3y 2 + 3z 2 . This concludes the proof.Define f full ℓ (x) = W pre ℓ+1 (W pre ℓ + ∆ full ℓ )W pre ℓ-1x as a fine-tuned network with full fine-tuning applied to the ℓ-th layer, evaluated under the population in-distribution risk, where ∆ full ℓ is obtained by∆ full ℓ ∈ arg min ∆ ′ ∈R d ℓ ×d ℓ-1 E B (i) x (i) -W pre ℓ+1 (W pre ℓ + ∆ ′ )W pre ℓ-1 x (i) 2 .Lemma E.17 (In-distribution Excess Risk). For f full ℓ , it holds thatE (i) (f full ℓ ) = ∥DΣ (i)1/2 x (I -Σ (i)1/2 x W pre⊤ ℓ-1 (A 2 ) † W pre ℓ-1 Σ (i)1/2 x )∥ 2 F + ∥(I -Φ ′ Φ ′⊤ )DΣ (i) x W pre⊤ ℓ-1 (A 2 ) † W pre ℓ-1 Σ (i)1/2 x ∥ 2 F .Proof of Lemma E.17. Similar to the proof of Theorem E.10, we haveEQUATION∥DΣ (i)1/2 x -W pre ℓ+1 ∆W pre ℓ-1 Σ (i)1/2 x ∥ 2 F = ∥ W pre ℓ+1 ∆W pre ℓ-1 Σ (i)1/2 x -Φ ′ Φ ′⊤ DΣ (i) x W pre⊤ ℓ-1 A † =:T1 ∥ 2 F (26) + ∥ DΣ (i)1/2 x (I -Σ (i)1/2 x W pre⊤ ℓ-1 (A 2 ) † W pre ℓ-1 Σ (i)1/2 x ) =:T2 ∥ 2 F + ∥ (I -Φ ′ Φ ′⊤ )DΣ (i) x W pre⊤ ℓ-1 (A 2 ) † W pre ℓ-1 Σ (i)1/2 x =:T3 ∥ 2 F ,where we used the fact that the inner products trT 1 T ⊤ 2 = tr T 2 T ⊤ 3 = tr T 3 T ⊤ 1 = 0. By choosing ∆ = (W pre ℓ+1 ) † DΣ (i)x W pre⊤ ℓ-1 A † for example, the term T 1 becomes 0. ThusEQUATIONF . This gives the desired result.We obtain the following corollary as a direct consequence of Lemma E.17. Corollary E.18. For f full ℓ , it holds thatEQUATIONThe first term on the right hand side of ( 27) measures the distance between two subspaces spanned by Ψ * (DΣ(i)1/2 x ) and Ψ * (W pre ℓ-1 Σ (i)1/2 x). Intuitively speaking, this quantifies the information coded at the ℓ-th layer, and the necessary information to predict residuals. Thus, it bounds the maximum improvement by the ℓ-th layer fine-tuning. The second term measures the subspace distance between the subspace where prediction residuals reside, and the subspace predictable by the ℓ-th layer finetuning.Lemma F.1. Fix s, d 1 , d 2 ∈ N + . For any A, B ∈ R d1×d2 , if ∥B -A∥ op ≤ ∥A∥ op and λ s (A) > λ s+1 (A) hold, then, ∥SVD s (B) -SVD s (A)∥ F ≲ κ 2 * (A) λ s (A) λ s (A) -λ s+1 (A) √ s∥B -A∥ op ∧ ∥B -A∥ F .Proof. By triangle inequality, This concludes the proof.EQUATIONWe cite the concentration inequality for cross-covariance matrices from [47] .Lemma F.2 (Proposition 9.1 from [47] ). Let Z and Z be mean zero random vectors taking values in R d1 and R d2 , respectively. Denote covariance matrices of Z and Z by Σ Z and Σ Z , respectively. Fix any t > 0. Assume that there exist constants c 1 , c 2 > 0 such thatEQUATION)holds for any γ ∈ R d1 and γ ′ ∈ R d2 . Choose n ≫ (r e (Σ Z ) ∧ r e (Σ Z ))(t + log(d 1 + d 2 )). Let (Z i , Zi ) i∈[n] be n independent copies of (Z, Z). Then, there exists a constant C = C(c 1 , c 2 ) > 0 such that with probability at least 1 -e -t , Note that if a random variable Z taking values in R d satisfies γ ⊤ Σ Z γ ≥ c∥γ ⊤ Z∥ 2 ψ2 for any γ ∈ R d with some constant c > 0, AZ also satisfies γ ′⊤ Σ AZ γ ′ ≥ c∥γ ′⊤ AZ∥ 2 ψ2 for any γ ′ ∈ R d ′ and any matrix A ∈ R d ′ ×d and arbitrary d ′ ∈ N + , where Σ AZ = AΣ Z A ⊤ .1 n i∈[n] Z i Z⊤ i -E[Z Z⊤ ]We then prove the following lemma to show the existance of a 'good' high probability event to bound multiple inequalities. Lemma F.3. Suppose that Assumptions E.1 and E.2 hold. Fix any S ⊂ [d ℓ ]. Then, there exists an event F with P(F) = 1 -exp -Ω(log 2 (n + d + p)) such that on the event F, for Φ ∈ {Φ ′ , Φ ′′ S }, ∥Φ ⊤ D Σ(i)x W pre⊤ ℓ-1 ∥ op ≲ ∥DΣ (i)1/2xEQUATIONand ϵ Φ) ∧ r e (A 2 )) log 2 (n + d + p), n ≫ (r e (Φ ⊤ DΣ (i) x D ⊤ Φ) ∧ r e (A 2 )) log 2 (n + d + p).EQUATIONUsing Lemma F.2, we obtainEQUATIONand ∥ Σ(i) ϵ,x ∥op ≲ ∥Σ (i) ϵ ∥ 1/2 op ∥Σ (i)x ∥ 1/2 op (re(ΣEQUATION∥ Σ(i)x -Σ (i) x ∥op ≲ ∥Σ (i) x ∥op re(ΣEQUATIONEQUATIONEQUATIONwith high probability. Hereafter we only focus on the event F where these inequalities hold. We divide the proof into 2 parts.Part 1. In this part we derive (30) , (31) and (32) . Note that ∥ Â2 -A 2 ∥ op ≤ λ * (A 2 )/2 holds on the event F since n ≫ κ 4 * (A)r e (A 2 ) log 2 (n + d + p) by Assumption E.2, and hence rank( Â2 ) = rank(A 2 ). Using Theorem 5.2 from [60] ,∥( Â2 ) † -(A 2 ) † ∥ op ∥(A 2 ) † ∥ op ≲ 1 - κ * (A 2 )∥ Â2 -A 2 ∥ op ∥A∥ 2 op -1 κ * (A 2 )∥ Â2 -A 2 ∥ op ∥A∥ 2 op .Again from Assumption E.2, (34) gives∥( Â2 ) † -(A 2 ) † ∥ op ≲ κ * (A 2 ) λ * (A 2 )r e (A 2 ) log 2 (n + d + p) n .This yields (30) . Proposition 3.2 from [65] and (34) yield, where Φ ′′′ := Φ * (A 2 ), and we used λ * (Φ ′′′⊤ A 2 Φ ′′′ ) ≥ λ * (A 2 ). Since Â = Φ ′′′ (Φ ′′′⊤ Â2 Φ ′′′ ) 1/2 Φ ′′′⊤ and A 1/2 = Φ ′′′ (Φ ′′′⊤ A 2 Φ ′′′ ) 1/2 Φ ′′′⊤ , we obtain (31) as∥(Φ ′′′⊤ Â2 Φ ′′′ ) 1/2 -(Φ ′′′⊤ A 2 Φ ′′′ ) 1/2 ∥ op ≤ ∥Φ ′′′⊤ ( Â2 -A 2 )Φ ′′′ ∥ opEQUATIONAgain using Theorem 5.2 from [60] combined with Assumption E.2, we obtain (32) as This yields ∥ Â † ∥ op ≲ ∥A † ∥ op .∥ Â † -A † ∥ op ≲ κ 2 * (A) λ * (A)Part 2. Next we derive (33) . By a similar argument as Part 1, (36) and Assumption E.2,∥( Σ(i) x ) † -(Σ (i) x ) † ∥ op ≲ ∥Σ (i)x ∥ op λ 2 * (Σ(i)x ) r e (Σ (i)x ) log 2 (n + d + p) n .Since D -D = Σ(i) ϵ,x = Σ(i) ϵ,x ( Σ(i)x ) † , ∥Φ ⊤ ( D Σ(i)x -DΣ (i)x )W pre⊤ ℓ-1 ∥ op ≤ Φ ⊤ ( D -D)Σ (i) x W pre⊤ ℓ-1 op+ Φ ⊤ D( Σ(i) x -Σ (i) x )W pre⊤ ℓ-1 op + Φ ⊤ ( D -D)( Σ(i) x -Σ (i) x )W pre⊤ ℓ-1 op = Φ ⊤ Σ(i) ϵ,x ( Σ(i) x ) † Σ (i) x W pre⊤ ℓ-1 op + Φ ⊤ D( Σ(i) x -Σ (i) x )W pre⊤ ℓ-1 op + Φ ⊤ Σ(i) ϵ,x ( Σ(i) x ) † ( Σ(i) x -Σ (i) x )W pre⊤ ℓ-1 op ≤ Φ ⊤ Σ(i) ϵ,x (Σ (i) x ) † Σ (i) x W pre⊤ ℓ-1 op + Φ ⊤ Σ(i) ϵ,x (Σ (i) x ) † Σ (i) x -( Σ(i) x ) † Σ (i) x W pre⊤ ℓ-1 op + Φ ⊤ D( Σ(i) x -Σ (i) x )W pre⊤ ℓ-1 op + Φ ⊤ Σ(i) ϵ,x ( Σ(i) x ) † ( Σ(i) x -Σ (i) x )W pre⊤ ℓ-1 op =: Q 1 + R 1 + Q 2 + R 2 .We bound Q 1 , Q 2 , R 1 and R 2 separately. For the terms Q 1 and Q 2 , ( 37) and (38) giveEQUATIONQ 2 ≲ ∥DΣ (i) x D ⊤ ∥ 1/2 op ∥A∥ op(r e (Φ ⊤ DΣ (i)x D ⊤ Φ) + r e (A 2 )) log 2 (n + d + p) n .For the term R 1 , using ( 35) and ( 40),EQUATION(r e (Σ x )) log 2 (n + d + p) nFor the term R 2 , using (35) and (36), R 2 ≤ ∥ Σ(i) ϵ,x ∥ op ∥( Σ(i)x ) † ∥ op ∥ Σ(i)x -Σ (i)x ∥ op ∥(Σ (i) x ) † ∥ 1/2 op ∥Σ (i) where we used ∥(Σ(i) x ) † ∥ op ≲ ∥(Σ (i)x ) † ∥ op by Assumption E.2 combined with (40) . Again from Assumption E.2, R 1 + R 2 is bounded by the right hand side of (41) . Therefore, ∥Φ ⊤ ( D Σ(i) x -DΣ (i) x )W pre⊤ ℓ-1 ∥ op ≲ ∥Σ (i) ϵ ∥ 1/ 


Decision: The reviewers generally found the paper well written, the proposed method to be technically sound and easy to understand, the work well motivated, and supported by the comprehensive experimental results. Reviewer's concerns during the rebutal centred on the theoretical analysis, confusing naming of the method, novelty of the pruning method itself, complex notation used in theoretical analysis and lack of explanatory figures. Thanks to the significant discussion and efforts of the author's and reviewers, it appears most of these concerns have been addressed and the reviewers are unanimous in accepting the paper.

Reviews: review: paper_summary: paper_summary: This paper introduces a new family of methods called Structured Sparse Fine-Tuning (S$^2$FT) for large language models (LLMs). S$^2$FT aims to achieve state-of-the-art fine-tuning performance, training efficiency, and inference scalability simultaneously. The method selects a few heads in the multi-head attention (MHA) module and a few channels in the feed-forward network (FFN) module for each Transformer block, then co-permutes the weight matrices to connect these selected components. This results in multiple compact, dense, and trainable weight submatrices that are updated during fine-tuning. The approach prevents overfitting and forgetting, delivers superior performance on benchmarks, and improves memory and throughput efficiency compared to full fine-tuning and existing parameter-efficient fine-tuning (PEFT) methods.
strength_weakness: strength_weakness: While the results look impressive, the reviewer is not fully convinced by the theoretical motivations. For example, the paper relies on the assumption that structured sparsity can effectively represent the necessary model adaptations, which is hard to verify in realistic settings. 

Although the benchmarks are comprehensive, most of the benchmarks do not include SFT or other SFT-based methods. Since S$^2$FT is in some sense an SFT-based method, it would be necessary to include such comparisons to understand if the performance improvements come from the "structure" (i.e. the $^2$) or SFT itself. Based on the current benchmarks, it is difficult to make such conclusions.

While the paper includes some implementation details, aiding reproducibility, the code is not provided, making it hard to verify or reproduce the results, especially for a paper with mostly empirical results.
questions: questions: Could the authors elaborate on the scaling of trainable parameters, as well as the space and time complexity, compared to other SFT-based or LoRA-based methods?

Could the authors elaborate on how the hyperparameters are chosen, and provide a more comprehensive list of hyperparameters used in this paper, the procedure to choose them, and the discarded hyperparameters?

Right now, the paper mainly discusses how to apply S$^2$FT to attention-based LLMs. The reviewer wonders how to identify the important weights and apply this method to other models.

Most of the experiments were performed on LLaMA and LLaMA2. The reviewer wonders if there is any difficulty in applying the method to LLaMA3.

Is it possible that different datasets/tasks could result in a different set of "important weights"? The reviewer wonders if the authors explored this possibility.

The reviewer wonders if the author could release the source code into an anonymous repository for review purposes.

In the NeurIPS checklist, the author claims that their results include confidence intervals. Could the authors make some comments on the confidence intervals for the tables in the paper?
limitations: limitations: The limitations and broader impacts are addressed.
paper_summary: paper_summary: Current PEFT methods for LLMs fail to achieve high quality, efficient training, and scalable serving simultaneously. To overcome this, the authors developed Structured Sparse Fine-Tuning (S²FT), which excels in all three areas. S²FT improves generalization by selecting a few heads in the Multi-Head Attention (MHA) and channels in the Feed-Forward Network (FFN) modules for each Transformer block. It forms dense, trainable submatrices by co-permuting weight matrices, preventing overfitting and forgetting. S²FT achieves state-of-the-art performance and reduces fine-tuning memory usage by up to 3 times and increases throughput by 1.5-2.7 times.
strength_weakness: strength_weakness: 1. The author claimed that S2FT prevent overfitting and forgetting. However except the toy experiments in 2nd section, I did not see any experimental proof. E.g. The author only gives MTBench results after the finetuning on AlpacaGPT4, what about the overfitting and forgetting issues?
2. Experiments only conducted on relative small models.
3. The name SFT may incur some confusions as it already has the meaning of supervised fine-tuning.
4. The experiments parts are not sufficient to proof the effectiveness of the proposed method especially on some downstream tasks.
questions: questions: 1. The author has some ablations on the trainable allocation choice within a block, what about the allocation in different layers?
2. Can this paper be combined with quantization just like QLoRA.
limitations: limitations: Yes
paper_summary: paper_summary: The paper introduces a structured pruning method for LLMs. The main idea is to permute the rows and columns of the weight matrices and select a submatrix during the fine-tuning process. The authors show that the proposed technique outperform previous techniques in terms of accuracy and efficiency.
strength_weakness: strength_weakness: Novelty in the pruning technique itself is limited. It is basically a structured sparse training method. Similar structured pruning methods have been proposed on non-LLM models previously (e.g., [27, 24]).
questions: questions: Will the authors open-source the code?
limitations: limitations: Yes.
paper_summary: paper_summary: This paper aims to address the fact that the current parameter efficient fine-tuning methods cannot simultaneously achieve high-quality, efficient training or scalable LLM services. Therefore, a series of structured sparse fine-tuning methods for LLM are proposed, which simultaneously achieve state-of-the-art fine-tuning performance, training efficiency and reasoning scalability. S2FT achieves this through "sparse selection and dense computation". It only selects a few heads in the MHA module and a few channels in the FFN module in each Transformer block. Then the weight matrix of the coupling structure in the LLM is rearranged so that the selected parts are interconnected to generate multiple compact and dense trainable weight sub-matrices. S2FT only needs to update these sub-matrices for efficient parameter fine-tuning. The paper focuses on the fact that current methods such as LoRA, DoRA, etc., although they can reduce memory, are not as good as fine-tuning in large language models. The unstructured characteristics of SFT require matrix sparse operations, which makes service scalability and training efficiency impossible to guarantee. This is the main reason and motivation for the proposal of S2FT in this paper. In addition, this paper establishes an interface between S2FT and LoRA to support joint or non-joint computing paradigms.
strength_weakness: strength_weakness: The advantages of the S2FT method in this paper are very prominent, and it provides some references for efficient, scalable, and high-quality fine-tuning methods for large language models. However, the author can consider the following areas for improvement or sufficient explanation: 
1. The symbols in the proof process of this paper can be slightly organized. Readers may feel that the symbols of the proof are a little messy when reading the entire proof process, but the whole process is complete and flawless. 
2. There are few figures for the method in this paper, only the right picture of Figure 2 is shown, and the overall picture is not clear enough. In addition, does this method extract the same layer for each different model? Or is it better to extract specific layers for each model? 
3. This paper locks the U of the low-rank decomposition matrix, which is a good attempt, but for different data sets, will the distribution of data affect the data form of the U matrix and the form of the U matrix basis? 
4. In the experimental results, there are many phenomena that the method used in this paper is lower than the previous methods. Can the author analyze each task more fully, because it can be seen from the table that some tasks are more obviously degraded?
questions: questions: 1. The symbols in the proof process of this paper can be slightly organized. Readers may feel that the symbols of the proof are a little messy when reading the entire proof process, but the whole process is complete and flawless. 
2. There are few figures for the method in this paper, only the right picture of Figure 2 is shown, and the overall picture is not clear enough. In addition, does this method extract the same layer for each different model? Or is it better to extract specific layers for each model? 
3. This paper locks the U of the low-rank decomposition matrix, which is a good attempt, but for different data sets, will the distribution of data affect the data form of the U matrix and the form of the U matrix basis? 
4. In the experimental results, there are many phenomena that the method used in this paper is lower than the previous methods. Can the author analyze each task more fully, because it can be seen from the table that some tasks are more obviously degraded?
limitations: limitations: This paper mentions some limitations of this paper in the limitations. For example, although various model architectures show coupled structures, this paper does not explore the opportunity to extend S2FT to other architectures. At the same time, in terms of model deployment, although this paper verifies the feasibility of scalable services in the work, there is still a lack of a practical and scalable actual service system. However, when using this method, is it necessary to consider the fairness or importance of each layer? For example, for a large language model, the first layer may contain more information, and some information in the middle layer can be appropriately eliminated. 
Secondly, whether it is truly quality-oriented needs to be considered because S2FT does not perform well in any task in the experiment of this paper. Finally, this paper also mentions that the subsequent optimization direction may be targeted at the residual dependency network, and how to perform S2FT on this type of network needs further consideration. However, since the work of this paper mainly focuses on PEFT, it leads to a reduction in GPU computing resource consumption. Therefore, this method has the potential to have a positive impact on the computing environment by minimizing the computing resources required for fine-tuning LLM.

Comments: title: Response to authors' rebuttal
Reminder on follow-up discussion (2 days left before the discussion period ends)
Reminder on follow-up discussion (2 days left before the discussion period ends)
Reminder on follow-up discussion (2 days left before the discussion period ends)
Code Release in an Anonymous Repository
Code Release in an Anonymous Repository
Code Release in an Anonymous Repository
comment: Author's rebuttal mostly addresses my concern. I will change the score.
Thanks for the authors' response. I have no more questions right now. I choose not to change the scores.
Thank you very much for your response. Please don't hesitate to reach out if you have any further questions. We greatly appreciate your willingness to consider raising the score.
Thank you so much for your dedicated review of our paper. We recognize the significant time and effort involved in your review, and we greatly appreciate it. With only 2 days remaining before the conclusion of the discussion phase, we wish to extend a respectful request for your feedback about our responses. Thank you!
Thank you so much for your dedicated review of our paper. We recognize the significant time and effort involved in your review, and we greatly appreciate it. With only 2 days remaining before the conclusion of the discussion phase, we wish to extend a respectful request for your feedback about our responses. Thank you!
Thank you so much for your dedicated review of our paper. We recognize the significant time and effort involved in your review, and we greatly appreciate it. With only 2 days remaining before the conclusion of the discussion phase, we wish to extend a respectful request for your feedback about our responses. Thank you!
Thanks a lot for taking the time and effort to answer my questions. I would like to keep my recommendation for acceptance of the paper, and am considering raising the score in the next 2 days.
To facilitate reproduction, we have provided our code at https://anonymous.4open.science/r/S2FT_Rebuttal-7B17 for reviewer’s verification and will make it publicly available upon paper acceptance.

This repository contains the training and inference code necessary to fine-tune a LLaMA-7B model on commonsense reasoning tasks. We hope this addresses your reproduction concerns.
To facilitate reproduction, we have provided our code at https://anonymous.4open.science/r/S2FT_Rebuttal-7B17 for reviewer’s verification and will make it publicly available upon paper acceptance.

This repository contains the training and inference code necessary to fine-tune a LLaMA-7B model on commonsense reasoning tasks. We hope this addresses your reproduction concerns.
To facilitate reproduction, we have provided our code at https://anonymous.4open.science/r/S2FT_Rebuttal-7B17 for reviewer’s verification and will make it publicly available upon paper acceptance.

This repository contains the training and inference code necessary to fine-tune a LLaMA-7B model on commonsense reasoning tasks. We hope this addresses the reproduction concerns raised by Reviewer CFWk and Reviewer d9g6.