An Efficient Pruner for Large Language Model with Theoretical Guarantee
Authors: Canhong Wen
Yihong Zuo
Wenliang Pan
Venue: ICML 2025 poster (2025)
Keywords: Large Language Model
Pruning
Risk Upper Bound
Monotone accelerated Iterative Hard Thresholding
Primary area: deep_learning->large_language_models

Abstract: Large Language Models (LLMs) have showcased remarkable performance across a range of tasks but are hindered by their massive parameter sizes, which impose significant computational and storage demands. Pruning has emerged as an effective solution to reduce model size, but traditional methods often involve inefficient retraining or rely on heuristic-based one-shot approaches that lack theoretical guarantees. In this paper, we reformulate the pruning problem as an $\ell_0$-penalized optimization problem and propose a monotone accelerated Iterative Hard Thresholding (mAIHT) method. Our approach combines solid theoretical foundations with practical effectiveness, offering a detailed theoretical analysis that covers convergence, convergence rates, and risk upper bounds. Through extensive experiments, we demonstrate that mAIHT outperforms state-of-the-art pruning techniques by effectively pruning the LLaMA-7B model across various evaluation metrics.

An Efficient Pruner for Large Language Model with Theoretical Guarantee
Canhong Wen
Yihong Zuo
Wenliang Pan
Abstract
Network pruning (LeCun al., 1989; Hassibi & Stork, 1992) is well-established method for addressing these challenges by removing redundant parameters while pre- serving model performance. Early pruning techniques often involved retraining after pruning (Han et al., 2015; Liu et al., 2018), process that became increasingly inefficient as model size grew. Moreover, efficient fine-tuning methods like LoRA (Hu et al., 2021) cannot be easily applied to pruned sparse models.
Large Language Models (LLMs) have showcased remarkable performance across range of tasks but are hindered by their massive parameter sizes, which impose significant computational and stor- age demands. Pruning has emerged as an effec- tive solution to reduce model size, but traditional methods often involve inefficient retraining or rely on heuristic-based one-shot approaches that lack theoretical guarantees. In this paper, we refor- fo-penalized
To mitigate these issues, recent research has shifted to- wards one-shot pruning methods, which eliminate parame- ters based on calibration data while retaining performance. These methods often view pruning as a layer-wise subset selection problem, leading to the development of various optimization-basee approaches (Frantar & Alistarh, 2022; Benbaki et al., 2023). However, the sheer scale of modern LLMs makes many traditional pruning methods impractical, and most current approaches rely on heuristic methods. For instance, SparseGPT (Frantar & Alistarh, 2023) leverages the Optimal Brain Surgeon (OBS) framework (Hassibi & Stork, 1992) and relies on heuristic approximations of the loss change, while Wanda (Sun et al., 2023) uses the product of weight magnitude and input activation norms to guide pruning. Although these methods are efficient, they lack theoretical guarantees of optimality due to their reliance on intuition and approximations.
mulate the pruning problem optimization problem and propose monotone accelerated Iterative Hard Thresholding (mAIHT) method. Our approach combines solid theoretical foundations with practical effectiveness, offering detailed theoretical analysis that covers conver- gence. convergence rates, and risk upper bounds. Through extensive experiments, we demonstrate that mAIHT outperforms state-of-the-arr pruning techniques by effectively pruning the LLaMA-7B model across various evaluation metrics.
1. Introduction
Large Language Models (LLMs) have demonstrated ex- ceptional capabilities in tasks such as reasoning, question answering, text generation, and sentiment analysis (Kojima et al., 2022; Wei et al., 2022; Achiam et al., 2023). How- ever, the growing size of these models, with ever-increasing parameter counts, imposes substantial demands on the com- putational and storage resources of hardware devices. For example, rumning the LLaMA 3.1 405B model (Dubey et al., 2024) requires minimum of 486GB of GPU memory in 8-bit mode, demanding least eight S0GB A100 GPUs.
Some recent studies have also explored efficient optimization-
approaches like ADMM (Alter- nating Direction Method of Multipliers--based pruning (Boža, 2024: Meng al., 2024a) and FISTA (Fast Iterative Shrinkage-Treesooldingg Algorithm)-based Pruning (Zhao et al., 2024). However, these approaches still lack theoreti- cal guarantees or introduce bias by relaxing the fn-rrmm problem (Bertsimas et al., 2016).
In this paper, we introduce mAIHT Pruner, novel one-shot layer-wise pruning method based on fo-penalized optimiza- tion. Our contribution are as follows:
Department of Statistics and Finance, School of Management, University of Science and Technology of China, Hefei, China "School of Gifted Young. University of Science and Technology of China, Hefei, China State Key Laboratory of Mathematical Sciences, Academy of Mathematics and Systems Science, Chinese Academy of Sciences, Beijing 100190, China. Correspondence to: Wenliang Pan <panwlinng camss.ac.en>.
1. We reformulate the pruning problem as an fo-penalized optimization problem and propose a monotone accel- erated iterative hard thresholding (mAIHT) algorithm to solve it. This technique not only accelerates the convergence of the traditional iterative hard threshold-
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

An Efficient Pruner for LLM
ing (IHT) method but also significantly improves the solution quality in practice. Furthermore, design adaptive selection of the penalty coefficient, allowing our algorithm to control the sparsity of the solution precisely.
Wi E R xda denote the pre- pre-trained weight matrix of layer l, where d1 and d2 denote the input and output dimension of layer L. For simplicity, we write W, as W in what follows. Given a calibration input X E X2xx of size N and a pre- specified sparsity level k. the layer-wise pruning problem can be formulated fo-constrained optimization problem:
2. We conduct rigorous theoretical analysis to explore the convergence and statistical properties of our algorithms. Specifically, We establish both the convergence and the rate of convergence. Furthermore, we analyze the risk upper bounds of the algorithms, bridging the gap between the experimental results and the theoretical analysis.
|X XW WER-1 2
min
s.t.
[ S K
where [ -i [(way) > 0) is the &o norm count- ing the number of nonzero elements in W (wyy). This formulation is first introduced in (Meng et al., 2024a) and an operator-splitingg technique is employed to solve the optimization problem.
3. In our experiments, we benchmark mAIHT against the latest state-of-the-art methods through the pruning of the LLaMA-7B model (Touvron et al., 2023). The find- ings indicate that mAIHT outperforms its counterparts, delivering superior pruning performance across low to moderate sparsity levels.
Rather than directly optimizing problem equation I, we consider the associated Lagrangian formulation as follows
((W) = 1 - w//
Notations. Denote by [n] = [I.....m] ] for a positive inte- ger n. Denote the cardinality of a set S by |S]. We use bold uppercase and lowercase letters to represent matrices and vectors, respectively. For vector a, denote the Ep norm of a = (ai,..., a² as ||al|p = (Ei a where 0 < p S oc. For a matrix A- = (at) E IR m we denote the
min W V Xd2
(2)
where 2 is the regularization parameter controlling the sparsity of the solution.
lo pseudo-norm as ||A llo. which equal to the number of
2.2. Naive iterative hard-thresholding algorithm
non-zero entries, Frobenius norm as ||A|| ||r = -Ei og the spectral norm as ||A]|2 = max (A), where mmx (A)
o )+,
To solve the optimization problem equation 2, the most tricky component is to deal with the Eg-regularized term, non-convex and non-smooth function. To overcome the computational difficulty,
the largest singular value of matrix A, and l norm as
||||] maxisjsn Eis lasyl- The support of A is de-
consider using the proximal gradient method (Parikh et al., 2014), which updates the weight matrix via a proximal operator. In particular, for any function g(-) defined on W E Rd xd2, the proximal operator of g(-) is defined by
noted by Supp(A) which is the index set {(i,j) aiy + 0}. Given i E [m]..] E [ni] and a set S C [m] [n]] Aij or As, denote aij. As and (A(A) denote projection of A onto S. which means retaining the components of in- dexed by S and zeroing out the remaining components of A. Denote I, as the identity matrix of dimension n. Let A E Th xm= and B E Xm, We define the Kronecker product of A and B A & B E mmmmm x such that (A Ø (). (.. 1hnstth is equal to Aig Bigis with ie E [m E [ma], is E Jo E [no]. For two positive sequences } and } write an = Obr,) if there exists some constant C' > such that an & Cb, for all n. Write a, = o(b,) if an/b,, - 0 as n co.
Prox g()) (W) arg min VER4i
v(V) + +22l | - VII
Denote f /(W) 2 X XWII and (( \// lo. then the objective function in equation 2 can be rewritten as L(W) = f(W)= + h(W). The main challenge in ap- plying the proximal gradient method in solving equation 2 is handling the function h(.). Therefore, we first present the proximal operator of h(W)- = >>llWllo the following proposition.
2. Method and Algorithm
Proposition 2.1. For any nonnegative real number X, the proximal operator of h(W) >l|Wllo can be expressed as
2.1. Model formulation
Post-training compression is typically achieved by dividing the full-model compression problem into smaller, layer- wise subproblems. Given a calibration input, we evaluate the quality of the solution using the residual sum of squares between the pruned and original outputs. To be specific, let
H HZ (W) E ProXA|i (W),
where H Hz is the element wise hard thresholding op- erator. i.e. H (52x((Ws,, = wiy if |wss > 22X and
H V2X W); = otherwise.
2

---

An Efficient Pruner for LLM
Based on Proposition 2.1, given the current estimate W* at the k-th iteration, we can derive the proximal gradient update of ((W) as
is the monitoring variable. Since the proximal gradient step essentially serves as hard-threholsing rule, we refer to this proposed algorithm as the monotone accelerated iterative hard- hard-thresholding (mAIHT) algorithm.
W /ZZX W )V
= H VZn W + Xo-'x(W--'''
2.4. Adaptive IHT//AIHT algorithm
Due to the non-convexity of problems in (I) and (2), they are not equivalent. However, in the context of one-shot pruning for neural networks, our primary target is to directly control the sparsity of the solution, as formulated in problem (1). To address this, we propose an adaptive method for determin- ing an optimal À corresponding to a pre-specified sparsity level. To be specific, we increase À when the sparsity of the current solution, W is below the desired sparsity, and decrease it when the sparsity exceeds the target. Addition- ally, the magnitude of increase or decrease is designed to be positively correlated with the difference between the current and desired sparsity levels. At the (A + 1)-th iteration, the update rule for À is given by
where a denotes the step size. The update scheme in (3) is
related to the well-known iterative hard-thresholding (IHT)
algorithm (Blumensath & Davies, 2008; 2009).
Remark 2.2. By setting W = W. we have W
H. A (W"), which is the magnitude pruning proposed by (Han et al., 2015), a well-estabilishing pruning technique in neural networks. (Frantar & Alistarh, 2023) finds that magnitude pruning fails dramatically on LLMs even with relatively low levels of sparsity.
2.3. Monotone accelerated iterative hard-thresholding algorithm
In practice, the convergence rate of the naive IHT algorithm is relatively slow, leading to significant computational over- head when pruning L.M.s. To address this, we employ the monotone accelerated technique (Li & Lin, 2015) by intro- ducing a momentum term. Following (Beck & Teboulle, 2009), we define the momentum term as a very specific linear combination between the previous two points and the corresponding proximal gradient map. At the (k + 1)- th iteration, this momentum term is added to the current solution W before performing the proximal gradient de- scent step. Furthermore, to determine when to acceler- ate and guarantee the loss function does not increase at the (k + 1)-th iteration, we use a proximal gradient step as a monitoring variable, denoted as Vk+1, The acceler- ation step is accepted only when c(Z*+1) S L(V This monitoring mechanism ensures the sufficient descent property, meaning there exists small constant ō such that L(W*+1) < L(V++1)= < C(W*)- 6||W* v l We summarise this monotone accelerated update for the (I+ + 1) iteration as follows:
x = 1² (1+ W
d1d2
where s denotes the target sparsity level. The initial value of À can be set to retain 99% of the elements, i.e. Amit = Q8 ((W1)/2c where Qo.01 ( ([WI) represents the 0.01 quantile of the absolute values of all elements in W and a is the input step size. With this initialization and adap- tive updating process, a gradual and controlable pruning can be achieved.
Upon terminating the mAIHT IHT iteration, we obtain the selected support through single projection operation (.W*),, where (W) represents the operation of retain- ing the largest elements of the absolute values from W and setting the remaining elements to zero At this stage, the optimal strategy at this point is to backsolve for the least squares solution on the current support. However, solving this exactly computational expensive, as requires com- puting the inverse of the S x 5 submatrix of X for each column support S of W This results in time complexity of (d2df). To mitigate this issue, we adopt the projected gradient descent algorithm (Frantar & Alistarh, 2023) to refine the final solution. This strategy proves to be highly efficient, as the proximal gradient process already provides solution that is close to the optimum.
( w+ + #k- 1 -1 (w* w
y = W
th z H M y a1 ()()')))
th
ph+1 = H V2oz2
W 02 (((W))))
++1 V4(10)2 +I+1
2
Z++1,
if 11) < L(VR+1),
}
Wh+1
vk-
otherwise.
The detailed steps of the adaptive algorithm are outlined in Algorithm 1, which summarizes the process described above.
(4)
Here Y represents the momentum term, Z ++1 denotes the proximal gradient map of the momentum term, and V
Remark 2.3. (Stability improvement) In practical applica- tions, we observe that modifying the problem (2) to the
3

---

An Efficient Pruner for LLM
Algorithm 1 Adaptive IHT/mAIHT algorithm for layer- wise pruning
It is important note that W is a-fixed point if and only
if
Input: step size a > Ainit sparsity level s, maximum iteration time k 1-2 maax.
(X"X(W- 0 Wwel 2 V2a,, for (i,j) Supp(W),
2: Initialize: W = W 7 = W, = =0=00 1
1 =Xinit--
1X"X( W))el
3: for k= 1,2, maax do
for (i,j) $ Supp(W).
4: A + x= (1 + 10-1))-).
did2
5: Update Wh+1 by (3) or (4) with X X
Then for any 0 S on S 022, we have
6: end for
7: T' < Supp(P.(WV1)) ))
F(an) D F(a2).
8: for 0.,1,2
22 1 do
9: W4--+1 (T a V (W)+
This implies that larger step size can reduce the size of the fixed point set, leading to a more concentrated accumulation points. As a result, the algorithm may converge to a more stable solution, as the fixed points will be less spread out. Based on the above definition, properties of the two algorithms. We first present a lemma to highlight the key descent property of the algorithms.
10: end for
11: Output: W th
establish the convergence
following formulation
min WER Xd2
((W) XW- - +
Lemma 3.2. Let a, 01,00, 02 +, and {W*] be the sequence generated by IHT mAIHT. Then L(W*) is descent sequence.
(5)
" 5 W WI? + A//W|oo
2
can improve the quality of the solution, where μ is small positive constant. The additional l regularization term can adjust the trade-off between bias and variance, which can enhance predictive accuracy by preventing overfitting. Moreover, this modified problem is equivalent to the original problem (2) taking X <- (X + y and therefore the theoretical properties of the problem (2) can be directly transferred to this modified problem.
Now we present the convergence results for both IHT and mAIHT algorithms.
Theorem 3.3 (Convergence Theorem).
Tk-o 1. Let 1. and (W be the sequence generated by IHT. Then there is a-fixed point W such that W - W'
2. Let 0n 02 < t (W")
Tk=o and [V* generated by mAIHT are bounded and any accumulation point of { [W*]e Jkmo is an a2- point.
3. Theoretical Analysis
In the following discussion, we consider the step size a and À to be fixed across the implementation. Let a < 1/T,, where L | is the Lipschitz constant of the gradient of f. We use IHT representing the iteration (3) and mAIHT representing the iteration (4).
Li & Lin (2015) proved that for the general mAIHT al- gorithm, any accumulation point W of [W will satisfy 0 E aL(W*), where OL denotes the sub-gradient set of L. The condition 0 OC(W*) is equivalent to (X X(W - W = for (i.j) E Supp(W"). By comparing this condition with ours, we observe that the set composed of all aixfixed points is subset of the points whose subgradients contain 0. This indicates that our result cannot be simply viewed as special case of theirs, but rather a stronger result.
3.1. Convergence and convergence rate
Intuitively, motivated by equation (3), we define W as a-fixed point if W = W leads to W = -W This can be regarded as a characterization of the stationarity of Problem (2). The formal definition of an a-fixed point is presented as follows.
Definition 3.1. Given an a > the matrix W Rd da is said to be a-fixed point of Problem (2) if it satisfies the following fixed point equation
Next, we present the convergence rates of the two al- gorithms. According to Lemma 3.2, the sequences {C( generated by both algorithms are decreasing sequences, and thus have limits L. Therefore, we proceed to analyze the convergence rates of these sequences.
W& E Pro ( + T (XW- XW)).
We denote the set of all o-fixed points as F(a).
Theorem 3.4 (Convergence rate).

---

An Efficient Pruner for LLM
1. Let W be the limit of [W* then L(W is descent sequence with limit & and there exists a kn such that for all k > kl, we have
Jk=0 generated by IHT,
We now present the risk upper bounds for the IHT and mAIHT methods under RIP assumption.
Theorem 3.6 (Risk upper bound for IHT). Let X
W W 13
i.dd. D3 and P( 2la S MMa) 1. For {W") generated by IIT with step size < _ and X. Assume
Vn (1), (1), 22,...,;nn.
31, 22,,..., Fn
~
((w+)- -
2a(k- k1)
0(1), O(1) and 8 satisfies (og(1/5) = O(n). For integer 8, assume with probability 1 Ç: (1) W = lim W s* = l[ llo and 8 2 8; (2) the restricted isometry constant of the matrix Laz @ VaX satisfies dx-4 TT< T < 0.5. Then with probabil- ity at least 1 6 Ç. there exists a K. For any k > K, holds that,
2. Let (W*) be generated by mAIHTT then ((Wk) is a descent sequence that converges to its limit &- at least in the sub-linear convergence rate after finite iterations, iee there exist lo > 0 and constant C, such that for all l > B2 we have
1-28 -(W*)- L (k- (k-b2)d(( 20)
C
R(W*) C
min R(W) +0
1
(20 + )
W.
1 2T
where
E
(0, 2 ( -1) -) (2(V))--))000 20)
and d
+0
V
log(2c9/0)
min+
{
[2((1 - Lozz)
C
n(1 22)
2 1-20
where C = 1 + 2(1 2(1+6,+++)
Theorem 3.4 states that the theoretical asymptotic conver- gence rate of IHT is O(1/k), while that of mAIHT is ((1))))), where 3 E (1, oo) is a constant. This shows that the theoretical convergence rate of mAIHT is not be worse than that of IHT. In addition, Theorem 3.4 suggests that a larger step size can lead to faster convergence rate. As mentioned earlier, a larger step size can help reduce the size of the fixed point set. Combining these insights, we can conclude that a larger step size will endow the stable points with better theoretical properties. Hence, it is necessary to choose relatively large step size in practice to exploit these benefits and improve the overall performance of the algorithm. However, one must also consider practical con- straints such as potential instability or overshooting when setting the step size too large.
I -6,-'
Corollary 3.7. In Theorem 3.6, suppose log(1/8) = o(n)).
8 o(1), < = o(1) and 1 = O1),, then for any > 0.
10z((1-271e) iterations of IHT, w satisfies after O K + log(28,
R(W*) S C² W.lllllos
min R(W) +
with probability 1 o(1.
Theorem 3.8 (Risk upper bound for mAIHT). Let X- / [2) ......,,)TTT, 21.-.., Lnn i.d. Dr and P([ a1 ll2 S M,) 1. For {W"} generated by mAIHT with step size a 1 and X. Assume 01 02 O(1), X O(1) and 8 satisfies log(1/5) = O(n). For integer s, assume with probability - C:
3.2. Risk upper bounds
all of [W")' Ys accumulation points have support size of s and s" 2 s:
Since reconstruction error is a crucial metric in the prun- ing task, we define the population risk as R(W) = Ex~D, (Il=T - x wll?), where D, is the distribution of the calibration data. The goal of this section is to study the population risk of * obtained by IHT or mAIHT with finite calibration samples. In the following discussion, we assume that D is a bounded distribution i.e. there exists a M2 such that IP([|==), 222 < M2) 1. We first define the restricted isometry property (RIP) introduced by Candes & Tao (2005b).
2. the restricted isometry constant of the matrix Idz @ VaX sutisfies 6,+4 S T < u R 0.3478, where u is real root of equation 4u + 4u² + u == 1;
Then with probability at least 1 - 8 - S, there exists K. For any ls > K, it holds that
R(W*) < C²
min R(W) +0
1
D DK-
Pr
(v/
Definition 3.5. (Candes& & Tao, 2005b; Candes, 2008) For matrix A E RRmx,, the Kthh restricted isometry constant (RIC), denoted by 5x, is the smallest number 8 2 0 such that
+0
1og(22l9/0) 18)
nn11 (1(1-p))'
where p 25 1. 1+,,- 12
< 1, Pr = 2yyTTT
< 1 and
(1- ||= < ||xم| < (1 + ||
/ 11-
VI-7
C 1+ / 1 (4+28.++
holds for all K K-sparse vector & E R.
V1-
5

---

An Efficient Pruner for LLM
metric. Specifically, we measure the reconstruction error 5 =1)) Ç= o(1) and T-p- O(1) then for any as | - [e/l///
Corollary 3.9. In Theorem 3.8, suppose log(1/0) o(n),
where W is the estimated
(e)))) 0, after O (K + log(p) satisfies
iterations of mAIIIT, W
weight matrix and W is the true weight matrix the k-th iteration. We also report the estimated sparsity level in each iteration. We apply both IHT and mAIHT to several layers of the LLaMA-7B model. The results are shown in Figure 1. It can be observed that the iterative process of our algorithm is divided into two stages. In the first stage, the support gradually shrinks to the desired sparsity level, with the spar- sity schedule naturally adopting an exponential shape. As shown in (Benbaki al., 2023), such an exponential-shapee shrinking schedule is relatively advantageous. In the second stage, proximal gradient descent is used to optimize the re- construction error. Comparing IHT and mAIH'T, we can see that mAIHT achieves faster convergence and significantly improves the quality of the final stable solution.
R(W*) S
min- W.
+W)+++0(1]
with probability 1 ((1.
Under proper assumptions, the upper bounds of the ex- cess risks R(W*) minw. || R(W) for IHT and MAIHT are composed of three terms. The first term minw.//W/loss Se R(W) represents the unavoided optimization error caused by the non-convyxity of the prob- lem. Luckily, this error is controlled by the optimal risk, Le. the model has an intrinsic sparse structure, this error would be small. In practice, if the underlying problem is sparse, the algorithm is more likely to find solution close to the optimal one, and this error becomes negligible. The second term is a non- non-sufficient optimization error caused by the finite time iterations of the algorithm. The bounds for this error show that the convergence rate is asymptotically linear under stronger assumptions than those discussed in section 3. The last term is the standard generalization error, which reflects how well the learned model can be generalized to the unseen data.
(a) O.se.f.att.k..rro
(b) O.self.att.q..pp
These two theorems suggest that mAIHT shares similar risk upper bound with IHT. Both of them can be controlled by a constant multiple of the optimal risk with high proba- bility. The detailed proofs can be found in Appendix C.
(c) 1 s.ll att.a.mmmmppoo
(d) 1.self Lsselfatt.q atro.
4. Numerical Experiments
Error mAIHT
Sparsity mAIHT Sparsity of IHT
4.1. Experimental setup
Error of IHT
Pre Pre-processing Like Wanda (Sun et al., 2023), we ran- domly utilize 128 calibration samples drawn from the C4 training dataset (Raffel et al., 2020). For each layer L, the calibration data X for the output of the previous é 1 pruned layers. For better scaling, we normalize X before pruning (Meng et al., 2024a). Specifically, we let E = Dia W- < W and +- XE. This technique can improve the pruning performance in practice. Notice that all the computations only need XTX, so we only need to compute it once per layer and store it.
Figure I. Reconstruction Process for IHT and mAIHT in One Layer.
4.3. Pruning LLaMA-7B model
In this section, we compare different methods by pruning the LLaMA-7B model at various levels of sparsity.
First, we train the LLaMA-7B model on the WikiText2 dataset (Merity et al., 2016) and perform weight pruning using different methods. We compare our method with one-shot pruning methods for LLMs, including (i) Mag- nitude Pruning (MP) (Han et al., 2015), (ii)aanda (Sun et al., 2023), (iii) SparseGPT (Frantar & Alistarh, 2023), and (Dv)ADDM
Hyperparameters choice. We set the step size a = 01 02 = 0.95/|| |2. the E2 penalty coefficient
0.1 (as
defined in (5)). the number of mAIHT iterations f1 = 50,
and the number of weight refining iterations t2 = 30.
Pruning (Boža, 2024; Meng et al., 2024a). We use the original settings of these algorithms in the codebase released by Sun et al. (2023) and Boža (2024). For each method, we measure the perplexity, the exponential of the loss function. Table showcases that m AIHT Pruner
4.2. Efficiency of the acceleration
We first use a single-layer experiment to demonstrate the efficiency of the acceleration, using reconstruction error as
6

---

An Efficient Pruner for LLM
outperforms all other methods in 0.2 to 0.5 sparsity. When the sparsity is 0.1, mAIHT is slightly inferior to ADMM but superior to other methods.
research was partially supported by the National Natu- ral Science Foundation of China (12322113, 72495122, 12288201).
Impact Statement
Table 1. Perplexity at different sparsity levels in WikiTex12
Sparsity level
The proliferation of Large Language Models (LLMs) has ushered in a new era of AI capabilities. but their immense parameter sizes pose challenges that hinder accessibility and sustainability. By addressing these issues, mAIHT method offers a significant step forward in making LLMss more efficient and practical. With its solid theoretical foun- dations and demonstrated empirical success, mAIHT not only enables effective pruning with rigorous guarantees but also holds the potential democratize the deployment of LLMs across industries.
Method
0.1
0.2
0.3
0.4
0.5
MP
5.8061
6.0206
6.6685
8.6012
17.2857
Wanda
5,6962
5,8229
5,9951
6,3970
7.2588
Sparsegpt 5.6972
5.8084
5,9730
6.3415
7.2397
ADMM
5.6925
5.8045
5.9586
6.3268
7.0826
MAIHT
5.6928
5,8042
5.9565
6.3240
7.0720
Then we compare our proposal with other existing methods in the zero-shot tasks. We compare the methods on seven zero-shot tasks which are the same as those selected by (Sun al., 2023). The tasks include BoolQ (Clark et al., 2019), RTE (Wang. 2018), HellaSWAG (Zellers al., 2019), Wino- Grande (Sakaguchi et al., 2021), ARC easy and challenge (Clark et al., 2018), and OpenbookQA (Mihaylov et al., 2018). Table 2 presents the accuracy of pruned models across various datasets, showcasing the performance of dif- ferent pruning methods at different sparsity levels.
However, this advancement also demands focus respon- sible Al practices. Reducing model size while maintaining performance raises essential questions about preserving fair- ness, robustness, and explainability in compressed models. As these technologies become more accessible, becomes increasingly important to ensure they are leveraged ethically and inclusively.
Our results reveal that within the low to moderate sparsity range (from 0.2 to 0.5), our method demonstrates accuracy among the top two on the majority of test datasets, and achieves the best mean accuracy across all sparsity levels.
References
Achiam, J., Adler, S., Agarwal, S., Ahmad, L., Akkaya, I., Aleman, F. L., Almeida, D., Altenschmidt, J., Altman, S., Anadkat, S., et al. Gpt-4 technical report. arXiv preprint arXiv:2303.08774, 2023.
5. Conclusion
In this paper, we introduce the mAIHT Pruner, an efficient layerwise one-shot pruning method for LLMs based on fo-penalized optimization. In our theoretical analysis, we prove the convergence of the algorithm and provide its con- vergence rate and risk upper bounds. The mAIHT Pruner is capable of finding high-quality solutions in practical prun- ing tasks. Through extensive experiments, we verify its superiore pruning performance at low to moderate sparsity levels.
Attouch, H. and Bolte, J. On the convergence of the proxi- mal algorithm for nonsmooth functions involving analytic features. Mathematical Programming, 1 16::5-6, 2009.
Beck, A. and Teboulle, M. Fast gradient-based algorithms for constrained total variation image denoising and deblur- ring problems. IEEE transactions on image processing, 18(11):2419-2434 2009.
Future works will consider extending this method other various kinds of pruning strategies, such as structured prun- ing (Meng et al., 2024b) and nonuniform layerwise pruning (Yin et al., 2023), since they can all be formulated or ap- proximately formulated as a variant of problem (1).
Benbaki, R., Chen, W., Meng, X., Hazimeh, H., Pono- mareva, N., Zhao, Z., and Mazumder, R. Fast chita: Neural network pruning with combinatorial optimization. In International Conference on Machine Learning, pp. 2031-2049, PMLR, 2023.
Acknowledgements
Bertsimas, D., King, A., and Mazumder, R. Best subset selection via a modern optimization lens. 2016.
The authors would like to thank the anonymous review- ers for their helpful comments. Wen's research is par- tially supported by National Key R&D Program of China 4024YFA10112000 the National Natural Science Founda- tion of China (12171449), and USTC Research Funds of the Double First-Class Initiative (YDD2040002019), Pan's
Blumensath, T. and Davies, M. E. Iterative Threshold- ing for Sparse Approximations. Journal of Fourier Analysis and Applications, 14(5-6):22 -6,464444 December 2008. ISSN 1069-5869, 1531-5851. 0000110008-9035--4
doi: 10.1007/
7

---

An Efficient Pruner for LLM
Table Zero-shot accuracies on various tasks for different sparsity levels. each dataset, hold the top results, and for the average accuracy. we bold the best result.
Sparsity
Method
BoolQ
RTE
HellaSwag
WinoGrande
ARC-e
ARC-c
OBQA
Mean
MP
54.40
54.15
60.91
59.35
54.34
37.12
35.00
50.75
Wanda
72.78
54.51
70.09
66.14
65.03
40.27
39.60
58.35
0.5
SparseGPT
73.76
52.35
69.27
70.09
65.53
39.76
40.00
58.68
ADMM
74.34
54.51
70.49
69.22
64.90
39.08
40.80
59.05
mAIHT
74.86
58.12
70.38
68.90
64.69
39.76
41.80
59.79
MP
67,46
57.76
70.27
66.38
64.18
39.68
39.20
57.85
Wanda
74.07
61.37
73.77
67.80
70.08
42.66
43.00
61.82
0.4
SparseGPT
74.59
55.96
72.98
69.22
69.07
41.72
41.80
60.76
ADMM
75.57
58.84
73.77
69.53
69.91
43.34
42.40
61.91
mAIHT
75.32
62.82
73.70
69.46
69.61
44.03
42.20
62.45
MP
72.32
61.73
74.05
68.90
70.62
44.62
40.60
61.83
Wanda
76.30
63.18
75.63
69.93
70.92
43.52
43.20
63.24
0.3
SparseGPT
76.00
63.90
75.18
69.46
71.00
45.22
43.00
63.39
ADMM
75.38
61.37
75.48
69.22
71.17
44.45
43.60
62.95
mAIHT
75.78
64.62
75.42
69.77
71.76
44.71
43.20
63.61
MP
74.83
60.65
75.57
70.32
72.10
44.88
43.00
63.05
Wanda
76.02
65.34
76.14
69.77
72.10
45.31
44.20
64.13
0.2
SparseGPT
75.47
63.18
76.08
69.61
71.59
44.71
44.20
63.55
ADMM
75.63
65.70
76.23
69.77
71.59
44.71
45.00
64.09
mAIHT 75.72
66.79
76.13
69.46
71.89
44.97
45.20
64.31
Blumensath. T. and Davies, M. E. Iterative hard threshold- ing for compressed sensing. Applied and computational harmonic analysis, 27(3):265-22) 274,, 2009.
Clark, P., Cowhey, I., Etzioni, O., Khot, T., Sabharwal, A., Schoenick, C., and Tafjord, O. Think you have solved question answering? try arc, the ai2 reasoning challenge. arXiv preprint arXiv: /803:0880300550 88.00355.75 2018.
Bolte, J., Sabach, S., and Teboulle, M. Proximal alternating linearized minimization for nonconvex and nonsmooth problems. Mathematical Programming, 146(1):459-494, 2014.
Diao, H., Jayaram, R., Song, Z., Sun, W., and Woodruff, D. Optimal sketching for kronecker product regression and low rank approximation. Advances in neural information processing systems, 32, 2019.
Boža, V. Fast and Effective Weight Update for Pruned Large Language Models, July 2024.
Dubey, A., Jauhri, A., Pandey, A., Kadian, A., Al-Dahle, A., Letman, A., Mathur, A., Schelten, A., Yang, A., Fan, A., et al. The llama 3 herd of models. arXiv preprint 2024.
Candes, E. and Tao, T. Decoding by linear programming.
IEEE Transactions on Information Theory, 51 51(12)44203- 4215, 2005a. doi: 10. 00.1109/TTT.22055888887
Frantar, E. and Alistarh, D. Optimal brain compression: A framework for accurate post-training quantization and pruning. Advances Neural Information Processing Systems, 35:4475-4488, 2022.
Candes, E. J. The restricted isometry property and its impli- cations for compressed sensing. Comptes rendus. Mathe- matique, 346(9-10):589
2008.
Candes, E. J. and Tao, T. Decoding by linear programming. IEEE transactions on information theory, 51(12))4203- 4215, 2005b.
Frantar, E. and Alistarh, D. Sparsegpt: Massive language models can be accurately pruned in one-shot. In Inter- national Conference on Machine Learning, pp. 10323- 10337. PMLR, 2023.
Clark, C., Lee, K., Chang, M.-W., Kwiatkowski, T., Collins, M., and Toutanova, K. Boolq: Exploring the surprising difficulty of natural yes/no questions. arXiv preprint arXiv: 1905. 10044, 2019.
Gray, S., Radford, A., and Kingma, D. Gpu kernels for block-sparse weights. arXiv preprint arXiv:1711.0922 3(2):2, 2017.
8

---

An Efficient Pruner for LLM
Han, S., Pool, J., Tran, J., and Dally, W. Learning both weights and connections for efficient neural network. Advances in neural information processing systems, 28, 2015.
Sakaguchi, K., Bras, R. L., Bhagavatula, C., and Choi, Y.
Winogrande: An adversarial winograd schema challenge at scale. Communications of the ACM, 64(9):99-106. 2021.
Hassibi, B. and Stork, D. Second order derivatives for network pruning: Optimal brain surgeon. Advances in neural information processing systems, 5, 1992.
Sun, M., Liu, Z., Bair, A., and Kolter, Z. A simple and effective pruning approach for large language models. arXiv preprint arXiv:2306. 11695, 2023.
Hu, E. J., Shen, Y., Wallis, P., Allen Allen-Zhu, Z., Li, Y., Wang, S., Wang, I.., and Chen, W. LoRA: Low-Rank Adaptation of Large Language Models, October 2021.
Touvron, H., Lavril, T., Izacard, G., Martinet, X., Lachaux, M.-A., Lacroix, T., Rozière, B., Goyal, N., Hambro, E., Azhar, F., et al. Llama: Open and efficient foundation lan- guage models. arXiv preprint
2023.
Kojima, T., Gu, S. S., Reid, M., Matsuo, Y., and Iwasawa, Y. Large language models are zero-shot reasoners. Ad- vances in neural information processing systems, 35: 22199-22213,, 2022.
Wang. Glue: multi-task benchmark and analysis plat- form for natural language understanding. arXiv preprint 1804. 0804007661 2018.
Wei, J., Tay, Y., Bommasani, R., Raffel, C., Zoph, B., Borgeaud, S., Yogatama, D., Bosma, M., Zhou, D., Met- zler, D., et al. Emergent abilities of large language models. arXiv preprint arXiv:2206. 076882 2022.
LeCun, Y., Denker, J., and Solla, Optimal brain damage. Advances in neural information processing systems, 2, 1989.
Li, H. and Lin, Z. Accelerated proximal gradient meth- ods for nonconvex programming. Advances in neural information processing systems, 28, 2015.
Wu, Y. N., Tsai, P.-A., Muralidharan, S., Parashar, A., Sze, V., and Emer, Highlight: Efficient and flexible dnn acceleration with hierarchical structured sparsity. In Pro- ceedings of the 56th Anmual IEEE/ACM International Symposium on Microarchiteccture, pp. 1 1106- 1 1120, 2023.
Liu, Z., Sun, M., Zhou, T., Huang, G., and Darrell, T. Re- thinking the value of network pruning. arXiv preprint arXiv:1810.05270. 2018
Yin, L., Wu, Y., Zhang, Z., Hsieh, C.-Y., Wang, Y., Jia, Y., Li, G., Jaiswal, A., Pechenizkiy, M., Liang, Y., et Out- lier weighed layerwise sparsity (owl): missing secret sauce for pruning Ilms to high sparsity. arXiv preprint arXi::2310.0511 2023.
Meng, X., Behdin, K., Wang, H., and Mazumder, R. ALPS: Improved Optimization for Highly Sparse One-Shot Prun- ing for Large Language Models, June 2024a.
Meng, X., Ibrahim, S., Behdin, K., Hazimeh, H., Pono- mareva, N., and Mazumder, R. Osscar: One-shot struc- tured pruming in vision and language models with combi- natorial optimization. arXiv preprint arXiv:2403. 12983, 2024b.
Zellers, R., Holtzman, A., Bisk, Y., Farhadi, A., and Choi, Y. Hellaswag: Can machine really finish your sentence? arXiv preprint arXiv: 1 1990507830 2019.
Zhao, P., Hu, H., Li, P., Zheng, Y., Wang, Z., and layer-wise post- training pruner for large language models, arXiv preprint wrXiv:2408.03728 2024.
Yuan, X. convex-optimizationn
Merity, S. Xiong, C., Bradbury, J., and Socher, R. Pointer sentinel mixture models. arXiv preprint 1609.06609 2016.
Mihaylov, T., Clark, P., Khot, T., and Sabharwal, A. Can a suit armor conduct electricity? a new dataset for open book question answering. arXiv preprint arXiv:1809.02783 2018.
Parikh, N., Boyd, S., et al. Proximal algorithms. Founda- tions and trends@ in Optimization, 1(3):127-239, 2014.
Raffel, C., Shazeer, N., Roberts, A., Lee, K., Narang, S., Matena, M., Zhou, Y., Li, W., and Liu, P. J. Exploring the limits of transfer learning with a unified text-to-text transformer. Journal of machine learning research, (140))1-67, 2020.
9

---

An Efficient Pruner for LLM
A. Properties of the Optimization Function
In this section, we analyze the theoretical properties of the optimization function (2). Recall that we define f(W)
XW X h(W) = lo and L(W) = f(W)+ +WW), where W E Rddi xd2, W E Rdixds and X E RNdd,
A.1. Derivations of f(W)
We first introduce some definitions of tensor trick (Diao et al., 2019), instrument to compute gradients in clean and tractable fashion:
Definition A.1 (Vectorization). For any matrix X E Rmxx we define X == vec(X) E R such that X., ((-1))at) for all E [m]] and j E [n]]
Lemma A.2 (Tensor Trick(Diao et al., 2019)). For any E R Xna B E R X and E 1. X it holds vec(A = (A @ B)X mmm.
Hence, we can compute the gradient f as
df dW
X-X(W- W).
(6)
and the Hessian matrix of f is given by d veo X W))
d² dw2
d((Tdp 8 X W = I, & X
(7)
dW
dW
The second equation relies on the tensor trick (Lemma A.2). The Hessian matrix of f implies that the gradient of is
Lipschitz continuous with Lipschitz constant of L = x ||
X i.e. [Vf(W) f(V))le s L|W V F.-
A.2. Proof of Proposition 2.1
The proximal operator of Al|-Ilo is given by
ProxA||-Io (W) = arg min
X lo +
Iw VI
VER Xd2
By taking condition support size we can decompose the optimization
1 ww- vI AlIVIlo + 2
1
min VER xd2
min OSaddida Vo
min
Al/V|lo + 1IW vI
2
1 As + 2 I|W vIB
min oSeSdida Vo
min
min
As + W W.WPP(W)IP
0S45dida
where P. (W( denotes the operation of retaining the largest elements of the absolute values from W and setting the others to O.
Consider arranging entries of W in ascending order of their absolute values as Wi, W2, ... Weydg For given support
size s, denote
dide-s
A(s) = As + 5 I (.WW) As
Σ
1
then
A(s) A(s 1) = 1/ W do 11
Hence, have for Wdddd-st11 < 22,, A(s) A(s 1), while for (Wdida-stil V2X, A(s) A(s 10-1) 1). Denote s* = SSuupp(H / =SSupp(H>>x(W))) (W)),, then we have (u', dg 2 +1 > 22,, and |wdd do - S 22x. This suggests that
A(s*) < A(s -1) <... <(0)
10

---

An Efficient Pruner for LLM
and
5 A(s A(d,d)).
Since V2x () PP. (w,),,, then we have
H (2) E PIo
A.3. Kurdyka-l.ojasiewice (KI.) properties
In the subsequent proof of our main results, we will leverage the Kurdyka-Lojasiewice (KL) property of the optimization functions f and h. For details on the KL property, please refer to Bolte et al. (2014). Here, we will prove the KL property by showing that the optimization functions are semi-algebraic (Attouch & Bolte, 2009). We begin by defining the semi-algebraic function.
Definition A.3. (Bolte et al., 2014) A subset S of I= is called the semialgebraic set if there exists finite number of real polynomial functions Gij, hij such that
S S=UNtu E I" (e((u) 0, (,)))(()) < O0.
function f(u) called the semi-algebraic function if its graph {(u,t) 12" R,, t f(u)} is semi-algebraic set.
Next, we will prove that f and are semi-algebraic functions and provide some function properties that are needed the subsequent proofs.
Proposition A.4.
1. f and h are semi-algebruic
2. h is proper and lower semi-continuous.
3. C is coercive i.e., C is bounded from below and L(W) + oo when || (WI3 - xc.
Proof. The proofs of 2 and 3 trivial, thus only need to check 1:
For f(W) XW XW
is real polynomial function, is semi-algebraic function.
For h( (W)) X|| oo the graph of is:
didz
di dz
G= ( : |
= i)
U 1=0
U
((W, : = S).
i=0
Since ((W, Ai): Supp(Wp) = {} is semi-algebraic set, G is semi-algebraic set and h is semi-algebraic function.
B. Proof of Optimization Results
B.1. Technical lemmas and some properties
We first define L-smooth functions.
Definition B.1. A function f TR. - R is called the I--moooh function if f is differentiable and satisfies
||V ff(v)l2 & L| -y122-
for every x. y R
Then we give some important lemmas for T-smooth functions and the proximal operator.

---

An Efficient Pruner for LLM
Lemma B.2 (Quadratic upper bound). Let J R IR be L-smooth function. Then,
f(z) - f(v) + (a y, vf(y)) + 2 || - y22 every x, y E R
Lemma B.3 (Convergence rate for convex proximal gradient method). Let f be convex and L-smooth. Let g be convex. Assume then proximal gradient method applied to minimize h = f + 9 with step size a S T. generates {w') }. Then there exists a x² such that x. + x² and
h(x²) - -((x=))=== [1 - 22
20(t 1)
Lemma B.4 (Sufficient descent lemma). Denote f(W) =211Y - XW and h(W) A/ Ler a < 1. Then for any W E RRd xd2, and V defined by
EE Proxat(() (W - -vVf(W))
We have
( a
-L 1 || -V--
S(V) + +MV) /(W) + (WW)))WW--)))
Proof. By the definition of the proximal operator, we can get
1 I w +
V arg
min
UER Xdg 2
Taking W, we can get:
V W + +aVa((()))) 3 + av())) - [ + ah(W),
1
V w + (V- W, W/V/(W)) A(V) S h(W).
20
By using the quadratic upper bound inequality (Lemma B.2) and the above inequality, we can obtain
S(V) + A(V) < f(W) (VS(W), V w) + T
IW-
VI + h(V)
S((W)= +
2 - - VI h(W)
1
W VI
2a
f(W) + h(W) 1
2 1) | W -WI?
| --_
Based on this lemma, we give some direct properties IHT and mAIHT. Proposition B.5. Let a = a < and [W*] Tz
- be the sequence generated in (3). Then we have
(1) The sequence ((W)) satisfies
L(W*) 2 1 L) 1
L(Wk-1) -(WW))
2
and is decreasing and converges to a positive number C*
(2) || - Wh + 0 as k + oc.
(3) For any positive integer M, we have:
W 2(C(W9) - L*)
min M
Mi! L.)
(4) There exists a positive integer K, such that for all integer > K, We has the same support.
12

---

An Efficient Pruner for LLM
Proof. (1) By using Lemma B.4 and the iteration (3), for any integer O, have
1 1
2( - 1.)
W
w < L(W -
-
2 a
This indicates that sequence L(W*) is a positive decreasing sequence, so there exists a positive real number L", such that
lim L(W*)- L.
k-200
(2) For any M 2 0, we have
M Σ
W wh- $ 2(C(WD)
((W
22(WO) -
L L
Let M - oo, this indicates that
| w -
(3) For any positive integer M, we have
2(2(W") L(WM))
2(((WO) L*) M 1.)
min L
W
1
M L))
(4) We will prove (4) by contradiction. Suppose for any integer K > 0, there exists a k > K, such that W and W have different supports.
By the definition of W the absolute value of any of its non-zero elements is greater than 22aA, which implies that
| w 2 2ad,
(8)
W and Wk- have different supports.
From the assumption, we know that there infinitely many such that (8) holds, which implies that
I Wk-1 2(<(W)) -
L
This leads to a contradiction. So there exists positive integer K, such that for all integers > K, W has the same support.
Proposition B.6. Let 02 } and ( Ikz be the sequence generated in mAIHT(4). Then have
(1) The sequence ((W') satisfies
((Wk+)) L(V++)) S L(W*) 1 1 L]] -
022
and is decreasing and converges to positive number L*
(2) ||v w 1 + 0 as + co.
(3) For any positive integer M, we have:
2(C(W9) Lt)
min k= M
|
w
M L)
This proposition's 's proof is essentially the same as Proposition B.5, so we omit its proof.
13

---

An Efficient Pruner for LLM
B.2. Proof of Theorem 3.3
Proof. (1) After a finite number of steps, the support of W remains unchanged(see Theorem B.5(4)). Consequently, the algorithm's iteration is equivalent to performing projected gradient descent over the support set. Since projected gradient descent over closed convex set converges when a* < +. there exists W such that W W Moreover, Since the absolute value of all nonzero entries of W greater than 22r,, W retains the same support as W for sufficiently large k.
Hence, [ llo + || llo - This implies that L(W*) L(W").
The remaining proof only needs to verify that W satisfies the equivalent condition for a-fixed points.
For (1,5) E Supp(W") and sufficiently large k. W = W 8j + (aXT XW*-))) ()) and ( 2 V2aX. Let + 00, we can obtain
x XW = 0 and W 2 V2a
For (i,j) & Supp(WW") and sufficiently large k; ( X) (Xx < V2a.. Let k - oc, we can get
2x
-
(2) Since L(W*) & L(V*) & L(W") for = 1.2,... and C is coercive, {w are bounded; otherwise, ((W*) or L(V*) will tend to positive infinity, which contradicts the boundedness of L L(W*) or C(V*).
Tk=0 and [ generated by (4)
its sub-sequence (Wh, j satisfy lim W W Then we have lim Vky k== has accumulation point W and W Since the absolute value of any non-zero elements of Vh W h = 2, ... is greater than min /2nn X, 22a22), } there exists J > 0, such that for every j > J, W and k have the same support as W Hence, similar to (1) above, the remaining proof only needs to verify that W satisfies the equivalent condition of a a2-fixed point.
By proposition B.6, we know that V W + 0 as k - Suppose (W*)
10300
For (i,j) E Supp(W")) and sufficiently large k, vk++1 wh. if + (a2XT XWh")); and V 2
V2az2. Let
bf
+ 00, We obtain
(X XW = and W 2 20zd.
For (i,j) & Supp(W"") and sufficiently large n, ((axX (o < V2ad.. Let h: - co, we can get
21 V0
XW
This completes the proof.
B.3. Proof of Theorem 3.4
(1) From proposition B.5, the support of W will stabilize after finite iterations. Suppose after k 's iteration the support stabilizes, denoted S. Then the iteration is equivalent
W = Ps (wssss- a (((W"-1)))
where (s( project W to S. By using Lemma B.3 with f f= /(W) and
0,
Supp W) C S
= Is(s)
00, Supp(W) g S.
14

---

An Efficient Pruner for LLM
We have
| W 11
((W*) - S 2a(k k1)
(2) We first illustrate that our optimization function satisfies the KL property through the following theorem:
Theorem B.7 ((Bolte et al., 2014; Attouch & Bolte, 2009)). For a semi-algebraic function f(x),, if it is proper and lower semicontinuous, then I satisfies the KL property and the desingularising function has the form of up (s) = cs--0 where e. is positive real number and E ().
The proof of Theorem 3.4 is a direct application the following theorem established by & Lin (2015).
Theorem B.8 (Li Lin, 2015)). Let f be a proper function with Lipschitz continuous gradients and h be proper and lower semicontinuous. Assume that C is coercive, f and h satisfy the KL. property and the desingularising function has the form of pt)) t for some C 0, 0 E (0, 11, then the monotone accelerated proximal gradient methods satisfies:
1. ff0 1, then there exists kn such that L(Wh)= Lh' for all k > kn and the algorithm terminates finite steps.
2. 1f0 E 1). 1).
then there exists lo such that for all l >> k2.
k(Wh)) - -0- (
d1c2 k-
(1+d,03)
Th2
3. 150 E (0, }), then there exists ka such that for all k > hia.
((W*)- L kk)22) ( 20)
C
where L² is the same function value at all the accumulation points of (W*), L(V)) L", di 2
(12 + L.) (2.a
202 -
5) and d2 = min {
(2
[2 178-11
20-1
(d 1 1-28
Theorem 3.4.2 is a direct consequence of combining Theorem B.7, Theorem B.8, and Proposition A.4.
C. Proof of Statistical Results
C.1. Technical lemmas
Recall that we denote R(W)- B([ W x W Tr(( W -W)), where E = (x) We denote the empirical risk as R(W)- = |XW XWI Tr((W W)TE(W W)), where X
1 / (211, 22, ........, TT..T.
33 1.1.d. D, and = Then offer a lemma give generalization risk bound.
1T, T2........ .....
Lemma C.I. Let Dr be a distribution over Rd which is bounded, i.e. there exits Ma, such that P. PAND, (||0]|| Then for any W E IRd xdd, we have
M₂) 1. Assume X (11, )TT 01 .2...., Bz 1i.d.
2M W W 1 log(
2d
R(W)- - R(W)
with probability at least 1-6
Proof. By using Hoeffding's inequality, for any j, E 1,... di we can get
2dh 2M1 log
1 Σ Σye En41 =
TayTa E(115014)1 S
n
n
with probability at least 5/d4.
15

---

An Efficient Pruner for LLM
2df Then we have,
Denote A V
2M2 log(
d1
- A) = P( U j,k=1
2 21
Σ
P(E
21
1=k=1
Hence, with probability at least - 8, for any W, we have
R(W) -
W) E)(W-WWWW -W)II
de
di
d
((W w)))((E E)jj W)ad
1=
dg
(W- W W)a( (W W)al
k=
s Ad2
We then give a useful lemma for RIP and extend to a matrix version.
Lemma C.2. (Candes & Tao, 2005a) Suppose matrix A satisfies the RIP of order k. Given a vector w E I and a set Q E [N]. one has
1. [I((T- ([(T-ATA)] ATA) S 6el/ua12 1 Supp(u)) S t.
2. ulAT))ll222 v1+ + 5. lull if t.
Corollary C.3. For matrix A Raxdi and matrix W Rulida suppose matrix Id, @ A satisfy the RIP of order k.
Given and set Q E [di) x [d2]. one has
1. 11((I-IAT))) ATA W) - 8, W/lF
St.
2. ||AT S W P $L st.
C.2. Proof of Theorem 3.6
Notice that by taking X' = VaX,a' 1, ad, the IHT iteration remains the same. Without loss of generality, we first consider a = 1.
Since from Proposition B.5, there exists a K, such that for any l 2 K, W have the same support as W Denote the support as S", and by the asumption, |S* = s" For h > K and any W such that || S s, we denote Y = XW, Y XW, Supp(W) W) and G W x XW*-I.. Then by triangular inequality, we have
I
W| = (-= - Wsus-lla l|
< [[( )- (G"))=usllle (GGh):us Wsus-lle
< 2 uuus - wus.-llr.
The second inequality is due to (G*)s. is the best s* sparse approximation of (G (s*)s-us and [/o ss.
W
W 2||( x x XW
XW BV--XP XWw+-)))sus Wsus- $ 2 - X"X) W)) + +2((X
(10)
28 W F + 2 8, 4. /
16

---

An Efficient Pruner for LLM
The third inequality is from Corollary C.3. Then by induction, it's easy to get
I WIF S (26 I|) WilF+ + 2 +
2 d. +e
1 1-20---
From Proposition B.5, we have L(W*) = L(W") = L(W) & Ad1 Hence, we have
V1-66-44 W- 11- S | W + 1/1F +
||
- Y XW ||5 + |
(11)
S v (2(WW)) + ||
3 2Ad + ||00
and
Y - XW S + + |
S |1 $
V1+ ds W
(12)
Hence by combining (10), (11) and (12), have
R(W*) |Y XI
$ ((1 + 2(1 + 6g-
)| F V 0 +0)* * | W|l
1 -5
$ ((1 + 2(1 + 8 85-4s)
(13)
)| v3(28,.++) K (v 2Xd || |[))))
28 48
cv R(W) + v3( 2Xd V3( + + k- 2
where 1 +
2(1+8.-+a)
It's easy to see that c1+ 1-27 0 1-
I-26, 20,
2M WIl logt 242
Denote B(W)-
We choose a fixed W E arg argmin /
|W B( W - x 333) and let
W in (13) equals to W Then B(W-) = O(V lo
Since we assume log(1/6) (1), with probability least
n
= O(VA 1 - 6, [RW+) - R(W +) < 0(1). Hence we have -
SO(A)+
Similar to (11), we also have
V2Xd, d2 + R(W+)
22ddid + (R(W+)+0N O(Vx+ (14)
W W 5
-1-5. -1-55-+0 85
V1/2
Hence, we have
W
W S / - - + W - W+1
5 /ddlw W W w+1
= =((V++1)
This shows that
B(W*) =0 (1
(Vā+ 1) log (2d3/8)
(15)
n
17

---

An Efficient Pruner for LLM
Then have
R(W") - + +
- (VA- ( (2 )²
+ +B(
(CVR(W*)+ (VV (26 (20g-+5)(-K) ) +B(W*)
(16)
+ (C(V++ (26 - +0 +0(1v++ 1)2) (20, (20 K)
+C+B(W")+((W')
VV+1
1 + (VX+1)²) (205++)) k-k +0 (VV + 1)3 (1 (1- 2T) V
/lo((2{{/0)
$ CC²R(W*)+ +0
Hence, for any a I 1/L, when Id, & VaX satisfies 6xts- S T, take in (16) equal to aλ. Since we assume 0(1)
and A = (1), we have
log (gg(2f//)
R(W*) S C2R(W*))+++) + +0( ( (20 (20g-aa) -- +0 (1-27)
27
n1
with probability 1 1- - This completes the proof.
C.3. Proof of Theorem 3.8
Since we assume that all accumulation points of (W*) have the same support size 8", there exists K, such that for k > K, ||W* = s" || llo = s" Otherwise, for any N E N, there exists a ky. such that || loo * s* or V llo * s*. From Proposition B.6 and Theorem 3.3, we know that V and W are bounded and share the same accumulation points. Since the absolute value of any non-zero entries of W and V is greater than minmar ,2)) we conclude that there exists an accumulation point W of either W Viky and we have |W"ll, llo s", which leads contradiction.
Denote a = a1 a2. Notice that by taking X' VoX,a' = 1, = at, the mAIHT iteration also remains the same.
Without loss of generality, we first consider 1. For any W such that | S 8, we denote Y XW, $ Y -XW, 5 Supp(V*) and S Supp(W). Then for any k K, have
YY - XW |X(W- - Wh+1) + 1
(17)
2 1 85-40 W w -
Similar to (9), also have
|V++1 WIF s 2 W + x XW XW ))s))llt
2 (00((IX'x)]) (W W)) 2||(X 4
X"x)
sust
(18)
< 25 25,'+s| W + 1 |
The second incquality is due to Corollary C.3. By repeatedly applying the definition of RIP, we have
8
W
W |F < X(W W
< Y
XW [|y |
Y X +
(19)
X(W - 2| |
V 8, W - V || + 2/ 4
18

---

An Efficient Pruner for LLM
The third inequality is due L(Wk+1) S ((V++)) and [Wo V llo s Combine (18) and (19), we have
V1 45 w || s 0o W W || + (4 + 26 +s))+ |||
We denote 2 V 1669112 Since we assume that 65+45 S < u R 0.34781, where u is the real root of
4u + 2u² + we have p P Pt < where Pr 2vTFFT vI-r
Then we can get
4 4 26
W W S p pk || - -F
| |
VI 6,
Similar to analysis of IHT, by (12) and (11), we have
R(w*) Y XW* F
$ (v1++ 60+0
W W + |1
((1+ V1 + ( 20 +0) )|(01| + VI+ dz 10 " | |
wllp)
(20)
V1 8, (1(1 (1= p)
2( 2dd d2 + @
S (CI|
p R²-Kj2
vI -
where C' ===1 1+ / /1+6,44(44266. It's easy to see that (1--p+
C +++
= 0
vl-
1 Pr
Denote B(W)- 2M W W df log(
We choose fixed W arg minw. E[I =''31 Take
W in (20) equal to W Since we assume (1/(1/)) O()), from Lemma C.1, with probability at least 1 - 5, R(W+) S
R(W+) + O11. Hence we have 2(v2Xdid2 + |1|r) O(VAd12 + v [((+)) s O(v 1) and B B(WW) S
(VX+1)* 16) (similar to (15)). Then we have
0
R(W*) & R(W*) + B(W")
(c (VV (VV+++++ (V*+1)D-K) ) + +B(W*)
(CVR((+)+B(W)) (0 ( x²² + B(W))
(21)
(C (C((VX++1)) pK-K g--K+0(vVee) +0((VV+1))) 1)2) C
<C²R(++) + 0
(VA+1)2
1- )p *
+0 (VV++1)2
log(2d7/8)
n21 - -4
Hence, for any 0 < a 1/L, when Lt, @ VaX satisfies 8sts' S T, since we assume a 0(1), O()), we have
R(W*) < C2R(W +0 (Vax+1) 1)2
P +0 (vvx= 1)²
log(2d4/8)
1 1
n(1 pr)
1
uk +0
(v/ (100g(20//1))
log(2d)//)
C2
min W.IlW/loSs
R(W) + 0
1- Pr
n(1 -{)-)
with probability - 8 - g.
This completes the proof.
19

---

An Efficient Pruner for LLM
D. A Additional Experiments
this section, we present experiments comparing the pruning time and performance of mAIHT with Wanda and SparseGPT. We also evaluate how the number of iterations in mAIHT affects both runtime and perplexity, showing its flexibility in balancing speed and accuracy.
D.1. Results on Larger Model
We conducted additional experiments on the LLaMA-13B model with 50% sparsity, evaluating its performance on Wikitext-2 perplexity well zero-shot tasks. The results are summarized in the tables below:
Table 3. Perplexity Wikitext-2 (11.MMA133, 50% Sparsity)
Method
Perplexity
SparseGPT 6.2535
mAIHT
6.1336
Table 4. Zero-Shot Downstream Task Accuracy (%, LLaMA-13B, 50% Sparsity)
Method
BoolQ
RTE
HellaSwag
ARC-e
ARC-c
WinoGrande
OBQA
Mean
SparseGPT
76.06
60.28
74.00
67.55
41.89
71.98
44.20
62.28
mAIHT
75.47
60.28
75.08
70.03
44.88
71.42
44.80
63.14
These results indicate that mAIHT outperforms SparseGPT both in terms of Wikitext-2 perplexity and the average per- formance across downstream tasks. mAIHT also achieves higher performance on individual tasks, demonstrating its effectiveness for model pruning.
D.2. Runtime Comparison
We compare the pruning times (including activation collection) for the LLaMA-7B model across three methods. All experiments were performed with an A100 GPU.
Table 5, Pruning Time on LLaMA-7B (in Seconds)
Method
Time (s)
Wanda
148.55
SparseGPT
609.04
mAIHT (50 iters)
1370.79
Although mAIHT incurs higher pruning times due to its iterative gradient-based optimization process, it remains significantly more efficient than full model fine-tuning. For instance, the Wanda paper (Sun et al., 2023) reports that LoRA fine-tuning on LLaMA-7B takes approximately hours on single V100 GPU, and full fine-tuning can take up to 24 days. contrast, mAIHT completes pruning under 30 minutes on an A100 GPU, offering practical and efficient alternative fine-tuning,
Importantly, mAIHT also provides controllable trade-off between pruning time and performance. As discussed in Remark 2.2, single iteration of mAIHT is equivalent to magnitude pruning, and with pre-pruning normalization, this reduces to Wanda. Thus, mAIHT can be seen as natural generalization of one-shot methods like Wanda and SparseGPT. By increasing the number of iterations, mAIHT improves performance progressively while keeping the computational cost manageable.
The following table illustrates how performance improves with more iterations of mAIHT when pruning LLaMA-7B to 50% sparsity:
20

---

An Efficient Pruner for LLM
Table 6. mAIHT Runtime and Perplexity at 50% Sparsity I.L.MA-BB
Method
Wanda (1 iter)
20 iters
50 iters
100 iters
Perplexity 7.2588
7.1876
7.0720
7.0765
Time (s)
148
860
1370
2286
These results show that mAIHT steadily improves performance the number of iterations increases, reaching the best perplexity 50 iterations. The slight increase in perplexity at 100 iterations is likely due overfitting the calibration data. Runtime scales approximately linearly with the number of iterations, enabling users to balance speed and accuracy based on their computational budget. Therefore, mAIHT provides a flexible and effective pruning strategy that offers much of the performance benefits of fine-tuning with only fraction of the computational cost, and clear advantages over static one-shot methods.
D.3. Support for Structured Pruning
The mAIHT framework can be extended to support structured sparsity constraints. Specifically, nwm sparsity can be incorporated by replacing the X|| l|o term in the optimization objective with an indicator function Is(W), where S denotes the set of matrices that satisfy the n.m sparsity pattern. The indicator function Is takes a value of when W and +00 otherwise. In this case, the proximal step in mAIHT reduces projection onto S, replacing the standard hard-thresholding operator.
Empirical results LLaMA-7B with 2:4 sparsity are provided in the following tables. As shown, mAIHT outperforms SparseGPT in terms of Wikitext-2 perplexity and achieves competitive superior performance across pero-shot tasks.
Table 7. Perplexity Wikitext-2 (LLaMA-7B, 2:4 Sparsity)
Method
Perplexity
SparseGPT 7.2933
mAIHT 7.2606
Table 8. Zero-Shot Downstream Task Accuracy (%. LLaMA-7B, 2:4 Sparsity)
Method
BoolQ
RTE
HellaSwag
ARC-e
ARC-c
WinoGrande
OBQA
Mean
SparseGPT
73.79
54.51
69.28
66.75
39.33
68.42
38.60
58.67
mAIHT
72.96
60.28
69.56
64.89
40.27
67.48
39.40
59.26
Additionally, the mAIHT framework is compatible with various other structured sparsity patterns, including hierarchical sparsity (Wu al., 2023), block sparsity (Gray al., 2017), and row sparsity (Meng et al., 2024b). For each of these sparsity patterns, the optimization objective is modified by replacing the to term with the indicator function [s()), and the projection step is adapted accordingly.
Although the current theoretical analysis of mAIHT is focused on unstructured sparsity and does not directly extend to structured sparsity due to the geometric and combinatorial differences the sparsity set S, future work will aim to extend these theoretical guarantees to structured sparsity.
D.4. Effect of Gradient-Bard Refinement
We conducted an ablation study on LLaMA-7B at 50% sparsity to evaluate the effect of the gradient- gradient-based refinement step on Wikitext-2 perplexity. The results are shown below:
21

---

An Efficient Pruner for LLM
Table 9, Ablation Study Refinement (Wikitext-2 PPI., LLaMA-7B, 50% Sparsity)
Method
Perplexity
SparseGPT
7.2397
mAIHT (w/o Refinement)
7.0843
mAIHT (Full)
7.0720
Even without explicit refinement, mAIHT achieves lower perplexity than SparseGPT, indicating that the proximal gradient steps implicitly refine the retained weights. The explicit refinement step further improves performance, confirming the effectiveness of the gradient-base based refinement mechanism in mAIHT.
22


Reviews:
[{"review_id": "8wfmEonomP", "reviewer": "Reviewer_gop3", "summary": "The paper introduces monotone accelerated Iterative Hard Thresholding (mAIHT), designed to improve the efficiency and theoretical soundness of pruning large language models (LLMs). The authors reformulated the pruning problem as L0-penality optimization problem, addressing the limitations of heuristic and retraining-based pruning methods. A notable strength of the paper is its rigorous theoretical analysis, including proofs of convergence, convergence rate, and risk upper bounds, which are often missing in existing pruning techniques. Experimental results demonstrate that mAIHT achieves superior pruning performance on the LLaMA-7B model compared to state-of-the-art approaches like SparseGPT and ADMM-based pruning, particularly in maintaining model performance at moderate sparsity levels.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's thoughtful feedback. Below, we provide our responses and clarifications.\n\n**How well does mAIHT scale to larger models? What are the computational trade-offs?**  \n**Reply**: \nWe thank you and Reviewer PbeQ for the comments. In response, we have added pruning experiments on the Llama-13B model. Please refer to our response to Reviewer PbeQ for the experimental results. We address the computational trade-offs in the following question.\n\n---\n\n**How does the runtime complexity and memory overhead of mAIHT compare to SparseGPT and ADMM-based pruning?**  \n**Reply**: The table below compares the runtime of mAIHT, Wanda, SparseGPT, and ADMM-based pruning on the LLaMA-7B pruning task, including the time for generating input activations:\n\n| |Time (s)|\n|---|---|\n|Wanda|148|\n|ADMM|446|\n|SparseGPT|609|\n|mAIHT|1370|\n\nmAIHT takes longer due to its advanced gradient-based optimization for layerwise reconstruction. However, its runtime remains negligible compared to LLM fine-tuning. For instance, Wanda [1] reports that fine-tuning LLaMA-7B with LoRA takes 24 hours on a V100 GPU, while full fine-tuning requires 24 days. In contrast, mAIHT completes pruning in under 30 minutes.\n\nMemory overhead is minimal since pruning is performed layer by layer, requiring only one layer parameters to be stored at a time.\n\n---\n\n**How sensitive is the performance to penalty selection, step size, and number of iterations? Would a different hyperparameter schedule improve results?**  \n**Reply**:\nWe appreciate the reviewer's insightful question. Below, we analyze the impact of different hyperparameters:\n\n1. **Penalty selection**: Our adaptive penalty selection requires only an initial penalty coefficient $\\lambda$. A smaller initial $\\lambda$ leads to better pruning results. In our experiments, we set $\\lambda$ to retain 95% of parameters initially. This aligns with the gradual pruning effect observed in [2].\n    \n2. **Step size and number of iterations**: We conducted experiments on the 0 self-attn.q_proj of the LLaMA-7B model for a fixed $\\lambda$. The table below presents the loss $\\mathcal{L}$ for different step sizes and iteration counts, where $L$ is the largest singular value of $X^{\\top}X$.\n\n| |$0.95/L$|$0.1/L$|$10/L$|\n|---|---|---|---|\n|0|14.59e+6|14.59e+6|14.59e+6|\n|10|7.15e+6|11.76e+6|9.37e+21|\n|50|6.73e+6|11.66e+6|nan|\n|100|6.61e+6|11.51e+6|nan|\n|200|6.59e+6|11.47e+6|nan|\n\nThe results align with our theoretical analysis. Larger step sizes can accelerate convergence, but to ensure stability, we require $\\alpha < 1/L$, where $L$ is the Lipschitz constant of the gradient of $\\frac12 \\Vert X\\hat{W}-XW\\Vert_F^2$. The experiment with $\\alpha=10/L$ confirms divergence.\n\n3.  **Ridge-like term coefficient $\\mu$**: $\\mu$ is introduced for stability. As long as its value remains small, the algorithm is not sensitive to $\\mu$.\n\n---\n\n**Can fine-tuning after pruning further improve performance? How does mAIHT compare with SparseGPT when fine-tuning is allowed?**  \n**Reply**: Fine-tuning can improve performance but significantly increases computational cost. mAIHT is designed as a one-shot pruning method to minimize retraining while preserving model accuracy. If fine-tuning is allowed, mAIHT provides a stronger starting point than SparseGPT, as it retains more critical weights and offers a more precise initial estimate. This results in higher final accuracy after fine-tuning.\n\n\n---\n\n**How does mAIHT compare with Lottery Ticket Hypothesis-based pruning?**  \n**Reply**: Both mAIHT and LTH-based pruning seek to find sparse subnetworks, but mAIHT offers key advantages:\n\n1. **No retraining needed**: mAIHT achieves one-shot pruning, whereas LTH-based methods require costly iterative retraining.\n    \n2. **Theoretical guarantees**: mAIHT provides convergence proofs and risk bounds, while LTH is primarily based on empirical observations without strong theoretical backing.\n\n\n---\n\n**Could mAIHT be used together with quantization (e.g., GPTQ) to further reduce inference cost?**  \n**Reply**: We appreciate this insightful question. Yes, mAIHT can be effectively combined with post-training quantization methods like GPTQ. Since mAIHT retains the most critical weights, subsequent quantization benefits from a well-structured model, leading to even greater inference efficiency and cost reduction.\n\n\n[1] Sun, M., Liu, Z., Bair, A., & Kolter, J. Z. A simple and effective pruning approach for large language models.  \n[2] Benbaki, R., Chen, W., Meng, X., Hazimeh, H., Ponomareva, N., Zhao, Z., and Mazumder, R. F. Fast as Cheetah: Neural network pruning with combinatorial optimization. In International Conference on Machine Learning.", "claims_and_evidence": "The authors make strong claims about mAIHT’s superiority over existing methods, particularly in terms of theoretical rigor and empirical performance. While they provide extensive theoretical justifications, the empirical results focus mostly on LLaMA-7B, which, though relevant, may not generalize across architectures. Some claims (such as scalability to larger models) could be better supported with additional experimental results.", "methods_and_evaluation_criteria": "The choice of perplexity and zero-shot accuracy as evaluation metrics is reasonable. The evaluation setup follows standard pruning benchmarks (using LLaMA-7B, WikiText2, and zero-shot NLP tasks). Ablation studies on penalty selection, iteration count, and sparsity adaptation strategy would add clarity.", "theoretical_claims": "The L0-penalized optimization reformulation is mathematically rigorous. Convergence proofs for monotone accelerated IHT are included. Theoretical comparisons with prior pruning works (SparseGPT, ADMM) are somewhat limited. A deeper discussion on their theoretical limitations vs. mAIHT's advantages would be beneficial.", "experimental_designs_or_analyses": "The experiments align with pruning literature, comparing against relevant baselines. Results focus only on LLaMA-7B, lacking validation across different model families. Computational cost (e.g., runtime, memory footprint) is not discussed—key for real-world deployment. While the paper focuses on one-shot pruning, post-pruning fine-tuning could show practical performance differences.", "relation_to_broader_scientific_literature": "The proposed method builds on SparseGPT and Wanda but replaces heuristic pruning with a more rigorous L0-penalized optimization framework. Monotone accelerated Iterative Hard Thresholding (mAIHT) is an improvement over Iterative Hard Thresholding (IHT) with adaptive sparsity control and faster convergence.", "essential_references_not_discussed": "Frankle, Jonathan, and Michael Carbin. \"The lottery ticket hypothesis: Finding sparse, trainable neural networks.\" arXiv preprint arXiv:1803.03635 (2018).", "other_strengths_and_weaknesses": "See above comments.", "other_comments_or_suggestions": "1. Several issues with citations. for example - citep vs citet. \n2. Inconsistencies in mathematical symbols.\n3. Table captions are not elaborated enough and contains several typos.", "questions_for_authors": "1. How well does mAIHT scale to larger models? What are the computational trade-offs?\n2. How does the runtime complexity and memory overhead of mAIHT compare to SparseGPT and ADMM-based pruning?\n3. How sensitive is the performance to penalty selection, step size, and number of iterations? Would a different hyperparameter schedule improve results?\n4. Can fine-tuning after pruning further improve performance? How does mAIHT compare with SparseGPT when fine-tuning is allowed?\n5. How does mAIHT compare with Lottery Ticket Hypothesis-based pruning?\n6. Could mAIHT be used together with quantization (e.g., GPTQ) to further reduce inference cost?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "fM1xgRBoFx", "reviewer": "Reviewer_iY6M", "summary": "$\\ell_0$ regularization and  propose to use proximal gradient descent to solve it. The authors also provide theoretical analysis for their method, but the review who is very bad at math is unable to justify them. Empirical evaluations show that the proposed method can alightly outperform existing pruning methods.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's insightful comments. Below, we address the concerns and provide clarifications.\n\n**Reply to the concerns in Methods and Evaluation Criteria**\n\nOur method can be directly extended to n:m sparsity by modifying the term $\\lambda\\Vert W\\Vert_0$ in problem (2) to $I_{S}(W)$, where $S$ represents the set of all matrices satisfying n:m sparsity, and $I_S$ is the indicator function ($I_S=0$ if $W \\in S$, $I_S=+\\infty$ otherwise). For this problem, monotone accelerated proximal methods can be applied directly. In practice, this means replacing the hard thresholding operator with a projection operator onto the n:m sparsity set $S$ consistent with the extensions proposed in [1] and [2]. The following table presents the results of LLaMA-7B pruning with 2:4 sparsity:\n\n|Methods|wikitext-2 perplexity|\n|---|---|\n|SparseGPT|7.2933|\n|mAIHT|**7.2606**|\n\n| Methods   | BoolQ     | RTE       | HellaSwag | ARC-e     | ARC-c     | WinoGrande | OBQA      | Mean      |\n| --------- | --------- | --------- | --------- | --------- | --------- | ---------- | --------- | --------- |\n| SparseGPT | **73.79** | 54.51     | 69.28     | **66.75** | 39.33     | **68.42**  | 38.60     | 58.67     |\n| mAIHT     | 72.96     | **60.28** | **69.56** | 64.89     | **40.27** | 67.48      | **39.40** | **59.26** |\n\nThese results demonstrate that mAIHT achieves competitive or superior performance compared to SparseGPT under n:m sparsity constraints.\n\nOur method can also be extended to structured pruning, including Hierarchical sparsity [3], Block sparsity [4], and Row sparsity [5]. In these cases, the $\\lambda\\Vert W\\Vert_0$ term in problem (2) is modified to $I_{S}(W)$, where $S$ represents the corresponding structured sparsity set. The algorithm requires only replacing the hard thresholding operator with a projection operator onto $S$.\n\nWhile our monotonically accelerated algorithm empirically improves performance under n:m sparsity, the theoretical analysis of mAIHT does not directly transfer to structured pruning settings. This is because the theoretical guarantees depend on the structural properties of the set $S$. To maintain a rigorous and principled approach to pruning, we did not include these extensions in the current version. However, we recognize that formalizing the theory for structured pruning is an important open problem. In future work, we plan to extend our theoretical framework to structured and semi-structured pruning settings. We will also discuss these extensions in the next version of our paper.\n\nFinally, we would like to highlight that a key contribution of our work is the **rigorous theoretical analysis** of the pruning algorithm, including convergence guarantees and generalization properties. Unlike heuristic approaches, our method provides a solid theoretical foundation, ensuring both strong empirical performance and efficiency in real-world applications. By establishing a principled approach to pruning, we believe this work lays a strong foundation for future research and further advancements in model compression.\n\n[1] Sun, M., Liu, Z., Bair, A., & Kolter, J. Z. A simple and effective pruning approach for large language models.\n\n[2]Xiang Meng, Kayhan Behdin, Haoyue Wang, Rahul Mazumder. ALPS: Improved Optimization for Highly Sparse One-Shot Pruning for Large Language Models\n\n[3] Wu, Y. N., Tsai, P. A., Muralidharan, S., Parashar, A., Sze, V., & Emer, J. Highlight: Efficient and flexible DNN acceleration with hierarchical structured sparsity.\n\n[4] Gray, S., Radford, A., & Kingma, D. P. GPU kernels for block-sparse weights.\n\n[5] Meng, X., Ibrahim, S., Behdin, K., Hazimeh, H., Ponomareva, N., & Mazumder, R. OSSCAR: One-Shot Structured Pruning in Vision and Language Models with Combinatorial Optimization.", "claims_and_evidence": "The proposed method is reasonable: it adopts the standard proximal gradient optimization to solve the problem. The acceleration with iterative hard-thresholding is also a standard practice in proximal gradient optimization.", "methods_and_evaluation_criteria": "The method and evaluation is generally reasonable. But the main concern is that the authors does not specify whether their pruning method is unstructured or semi-structured (obviously it is not structured pruning). If the method is simply unstructured pruning, the improvement over baselines is too margin -- most of the baselines are designed for semi-structured pruning such as 2:4 or 4:8 sparsity and can actually be deployed for acceleration of LLMs. However, it seems the authors only compare with baselines in unstructured pruning setting, which is far from sufficient -- the improvement is very marginal, and the proposed method can not be used for acceleration of LLMs due to its unstructured property.", "theoretical_claims": "The reviewer is not able to justify the correctness of the proofs and theoretical analysis in Section 3.", "experimental_designs_or_analyses": "Please refer to Section **Methods And Evaluation Criteria**. The main concern regarding the experimental design is the unstructured pruning setting -- nearly all baselines can be used for semi-structured pruning while the proposed method does not prove it can do semi-structured pruning. Unstructured pruning cannot be used for acceleration for LLMs, which hurt the contribution of this paper.", "relation_to_broader_scientific_literature": "N/A", "essential_references_not_discussed": "n/a", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "N/A", "questions_for_authors": "Please refer to Section **Methods And Evaluation Criteria**. If the concerns on efficiency can be resolved, I will be happy to increase my rating.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "F93Sggx12n", "reviewer": "Reviewer_PEKo", "summary": "This paper addresses the challenge of pruning Large Language Models (LLMs) to reduce computational and storage costs without retraining. The authors reformulate the pruning process as an $\\ell_0$-penalized optimization problem and propose a “monotone accelerated Iterative Hard Thresholding” (mAIHT) method. They provide detailed theoretical analyses—covering convergence, convergence rates, and risk upper bounds—and demonstrate experimentally that their approach outperforms several state-of-the-art pruning techniques for LLaMA-7B on tasks such as WikiText2 (perplexity) and multiple zero-shot benchmarks.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's thoughtful feedback. Below are our responses and clarifications for the various concerns raised.\n\n**High-Sparsity Regime: Have you tested or do you plan to test the method at extremely high sparsities (e.g., 80-90%)?**  \n**Reply**: Thank you for the question. We found that at very high sparsities (80-90%), models pruned by all methods degrade significantly, with performance dropping to near-random guessing. Below, we compare mAIHT and SparseGPT at 70% sparsity on the LLaMA-7B model:\n\n|Methods|wikitext-2|\n|---|---|\n|SparseGPT|26.6107|\n|mAIHT|**21.9671**|\n\n|Methods|BoolQ|RTE|HellaSwag|ARC-e|ARC-c|WinoGrande|OBQA|Mean|\n|---|---|---|---|---|---|---|---|---|\n|SparseGPT|63.18|**53.43**|42.82|40.24|26.37|59.04|**30.20**|62.28|\n|mAIHT|**65.29**|51.99|**44.21**|**42.76**|**27.73**|**60.30**|**30.20**|**63.14**|\n\nThese results show that mAIHT performs better than SparseGPT even at high sparsities (up to 70%).\n\n---\n\n**Structured Pruning: Is the proposed method easily adapted to channel-level or head-level pruning?**  \n**Reply**:  \nWe appreciate this important question. Our proposed method can be adapted to semi-structured and structured pruning, including N:M sparsity, hierarchical sparsity [1], block sparsity [2], and row sparsity [3]. Formally, in problem (2), the term $\\lambda\\Vert W\\Vert_0$can be replaced with $I_{S}(W)$, where $S$ represents the set of matrices satisfying the desired sparsity pattern, and $I_S$ is the indicator function ($I_S = 0$ if $W \\in S$, $I_S = +\\infty$ otherwise). For this problem, monotone accelerated proximal methods can be applied by replacing the hard thresholding operator with a projection operator onto $S$. Below are results for 2:4 sparsity in LLaMA-7B:\n\n|Methods|wikitext-2 perplexity|\n|---|---|\n|SparseGPT|7.2933|\n|mAIHT|**7.2606**|\n\n|Methods|BoolQ|RTE|HellaSwag|ARC-e|ARC-c|WinoGrande|OBQA|Mean|\n|---|---|---|---|---|---|---|---|---|\n|SparseGPT|**73.79**|54.51|69.28|**66.75**|39.33|**68.42**|38.60|58.67|\n|mAIHT|72.96|**60.28**|**69.56**|64.89|**40.27**|67.48|**39.40**|**59.26**|\n\nHowever, for channel-level or head-level pruning, our method is not ideally suited, as it evaluates the importance of individual parameters rather than entire channels or attention heads.\n\n---\n\n**Calibration Data: How robust is mAIHT to smaller or noisier calibration sets?**  \n**Reply**:  \nWe compare mAIHT and SparseGPT across different calibration set sizes for 0.5 sparsity pruning in LLaMA-7B.\n\n|Number of calibration data|32|64|128|\n|---|---|---|---|\n|SparseGPT|7.4959|7.3281|7.2397|\n|mAIHT|**7.2305**|**7.1867**|**7.0720**|\n\nResults show that mAIHT is significantly more robust to smaller calibration sets compared to SparseGPT. Regarding noisy calibration sets, we typically use high-quality data for optimal results. While we avoid excessive noise, testing robustness against noisy data is an interesting research direction, and we will consider further experiments to evaluate mAIHT in such scenarios.\n\n---\n\n**Implementation Tips: Could you elaborate on any pitfalls or best practices (beyond step-size selection) that practitioners should keep in mind?**  \n**Reply**:\nWe appreciate the reviewer's question. Below, we discuss key hyperparameter considerations:\n\n1. **Penalty Selection**:We have designed an adaptive penalty selection where practitioners only need to set an initial penalty coefficient $\\lambda$. We recommend setting a small initial $\\lambda$ (e.g., to retain 95% of the parameters) for optimal pruning performance. This phenomenon aligns with gradual pruning observed in [4].\n2. **Step Size and Number of Iterations**: Based on simulations on the 0-self-attn.q_proj layer of the LLaMA-7B model, we suggest using a relatively large step size, ensuring $\\alpha<1/L$, where $L$ is the Lipschitz constant of the gradient. Choosing a step size too large can cause instability, while a smaller value ensures convergence.\n3. **Ridge-like term coefficient $\\mu$**: The $\\mu$ term enhances the stability of the algorithm. As long as $\\mu$ remains small, the algorithm is not sensitive to its exact value.\n    \n\n[1] Wu, Y. N., Tsai, P. A., Muralidharan, S., Parashar, A., Sze, V., & Emer, J. Highlight: Efficient and flexible DNN acceleration with hierarchical structured sparsity.\n\n[2] Gray, S., Radford, A., & Kingma, D. P. GPU kernels for block-sparse weights.\n\n[3] Meng, X., Ibrahim, S., Behdin, K., Hazimeh, H., Ponomareva, N., & Mazumder, R. OSSCAR: One-Shot Structured Pruning in Vision and Language Models with Combinatorial Optimization.\n\n[4] Benbaki, R., Chen, W., Meng, X., Hazimeh, H., Ponomareva, N., Zhao, Z., and Mazumder, R. F. Fast as Cheetah: Neural Network Pruning with Combinatorial Optimization. In International Conference on Machine Learning.", "claims_and_evidence": "1. Claim: The paper claims to offer a layer-wise pruning procedure (mAIHT) that achieves better pruning performance than existing one-shot methods like Wanda, SparseGPT, and ADMM-based pruning.\n   - Evidence: Experimental evaluations on LLaMA-7B at various sparsity levels consistently show improved perplexities on WikiText2 and higher zero-shot accuracies across a variety of tasks.\n\n2. Claim: The proposed $\\ell_0$-penalized optimization framework has strong theoretical guarantees.\n   - Evidence: The paper derives the convergence of both the IHT and mAIHT methods, provides sub-linear or linear rates under certain assumptions, and proves risk upper bounds in the setting of finite calibration data. \n\n3. Claim: The monotone accelerated variant (mAIHT) converges more quickly and finds solutions of higher quality than naive iterative hard thresholding alone.\n   - Evidence: Single-layer experiments and subsequent ablation-like studies show that mAIHT attains lower reconstruction error (based on $\\|XW - XW^{\\text{(orig)}}\\|_F$) more rapidly.", "methods_and_evaluation_criteria": "- Methods:  \n  - $\\ell_0$-penalized Formulation: The pruning is cast as minimizing $\\frac{1}{2}\\|XW_{\\text{orig}} - XW\\|_F^2$ subject to an $\\ell_0$ term.  \n  - IHT and mAIHT: Iterative Hard Thresholding is adapted to an accelerated, monotone version, which helps achieve faster convergence.  \n  - Adaptive Sparsity Scheduling: The regularization parameter $\\lambda$ is adjusted to match a desired target sparsity level.  \n  - Practical Refinement Step: After determining the support, a projected gradient descent step refines the solution.\n\n- Evaluation Criteria:  \n  - Perplexity on WikiText2 (lower is better).  \n  - Accuracy on zero-shot benchmarks (BoolQ, RTE, HellaSWAG, WinoGrande, ARC-e, ARC-c, OpenbookQA).  \n  - Computational Efficiency: Demonstrated by plotting reconstruction error vs. iteration count for IHT vs. mAIHT.", "theoretical_claims": "1. Convergence Guarantees:\n   - The paper proves that both IHT and mAIHT converge to a so-called “$\\alpha$-fixed point,” ensuring there exists a stable solution that the iterative procedure approaches.\n2. Convergence Rate:\n   - IHT has a sub-linear rate of $O\\bigl(\\tfrac{1}{k}\\bigr)$, while mAIHT exhibits a faster asymptotic rate $O\\bigl(\\tfrac{1}{k^\\beta}\\bigr)$ for some $\\beta>1$ under certain monotonicity conditions.\n3. Risk Upper Bounds:\n   - Under assumptions of restricted isometry properties (RIP) and bounded data, the pruned solution’s risk approaches a constant multiple of the optimal risk, indicating good generalization even with finite calibration samples.\n\nThese theoretical contributions are significant because they strengthen the rigor behind pruning methods, which are often heuristic or lacking formal guarantees.", "experimental_designs_or_analyses": "- Data and Setup: The authors select a small calibration set from C4 (128 samples) to prune each layer, then evaluate perplexity (WikiText2) and zero-shot accuracy on multiple tasks.\n- Metrics: They track perplexity, zero-shot accuracy, and reconstruction error. They also compare runtime and iteration counts for single-layer experiments.\n- Model: LlaMA-2 7B.\n- Results: \n  - Across moderate sparsity levels (20–50%), mAIHT typically surpasses other baselines in perplexity and zero-shot accuracy. \n  - For extreme low-sparsity regimes (e.g., 10%), the performance remains comparable, sometimes slightly below ADMM-based methods but still better than standard magnitude pruning or Wanda.", "relation_to_broader_scientific_literature": "- Pruning Methods: Builds on classical magnitude pruning (Han et al., 2015) and more recent single-shot approaches like Wanda and SparseGPT. The paper extends these techniques with a formal $\\ell_0$-based optimization perspective. \n- Optimization for Pruning: Incorporates ideas related to iterative shrinkage/thresholding algorithms from compressed sensing, bridging them with modern large-model pruning. \n- Large Language Model Compression: Contributes to a growing interest in making LLMs more resource-friendly, aligning with a broader literature on LoRA, low-rank factorization, and other parameter-efficient fine-tuning or pruning methods.", "essential_references_not_discussed": "The core references for single-shot pruning and $\\ell_1$/$\\ell_0$-based approaches are covered. However, the authors might consider:\n- Structured Pruning approaches for LLMs (e.g., channel or head pruning) that could benefit from a similar $\\ell_0$-reformulation.  \n- Mixed-precision or quantization methods that often co-occur with pruning and share theoretical frameworks about memory reduction and inference latency.", "other_strengths_and_weaknesses": "Strengths:\n- Clear theoretical foundation, which is relatively uncommon for LLM pruning papers.  \n- Practical and easily implemented (layer-wise) method that converges quickly.  \n- Strong empirical gains at moderate sparsity levels.  \n- Helpful ablation-like results on reconstruction error across multiple iterations.\n\nWeaknesses:\n- Although the method performs well at moderate sparsities, there is somewhat less emphasis on extremely high sparsity (e.g., 90%+).  \n- The approach relies on a small calibration set that can induce overfitting on C4 dataset nature.\n- Integration with quantization or other compression techniques remains an open question.\n- Only one model: LLaMA-2 7B was considered. It is common in pruning papers to include more experimental results with more models (LLaMa-3 from 1B up to 70B)\n- Practicality of the work: it is not well explained why do we need sparsity in LLM. e.g. in quantization we gain memory because it is much easier to store low-bit representation of the weight, but sparsity (unstructured) is not that applicable.", "other_comments_or_suggestions": "- Support for Structured Pruning: Extending mAIHT to structured or blockwise pruning scenarios could be of practical interest.  \n- Real-World Deployments: Future work could explore how performance and latency improvements manifest on actual hardware beyond just theoretical FLOPs or memory measures.  \n- Hyperparameter Sensitivity: While the paper provides defaults, additional clarity on how sensitive the final results are to $\\lambda$, the step size $\\alpha$, or the $\\ell_2$-regularization parameter $\\mu$ would be beneficial for reproducibility.", "questions_for_authors": "1. High-Sparsity Regime: Have you tested or do you plan to test the method at extremely high sparsities (e.g., 80–90%)?  \n2. Structured Pruning: Is the proposed method easily adapted to channel-level or head-level pruning?  \n3. Calibration Data: How robust is mAIHT to smaller or noisier calibration sets?  \n4. Implementation Tips: Could you elaborate on any pitfalls or best practices (beyond step-size selection) that practitioners should keep in mind?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "dI40nSEarH", "reviewer": "Reviewer_PbeQ", "summary": "The paper proposes an proximal-operator based approach that allows to prune linear layers in large language models. The paper provides a solid theoretical analysis of the method as well as experiments on a Llama 7B, where it (marginally) improves over previous methods.\n\nThe proximal operator is (known) the elementwise hard thresholding operator. The key innovations of the paper are the addition of an acceleration step that guarantees descent as well as an adaptive selection of the regularization parameters, depending on how far from the target sparsity level the current matrix is.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer's thoughtful feedback. Below, we provide our responses and clarifications.\n\n**Can you get results on a LLaMA 3.1 model and also on a 70B model?**  \nWe appreciate the reviewer's valuable suggestion. Due to resource constraints, we have conducted additional experiments on the LLaMA-13B model with 0.5 sparsity. The results are summarized below:\n\n|Methods|wikitext-2|\n|---|---|\n|SparseGPT|6.2535|\n|mAIHT|**6.1336**|\n\n|Methods|BoolQ|RTE|HellaSwag|ARC-e|ARC-c|WinoGrande|OBQA|Mean|\n|---|---|---|---|---|---|---|---|---|\n|SparseGPT|**76.06**|**60.28**|74.00|67.55|41.89|**71.98**|44.20|62.28|\n|mAIHT|75.47|**60.28**|**75.08**|**70.03**|**44.88**|71.42|**44.80**|**63.14**|\n\nThese results demonstrate that mAIHT achieves better perplexity and mean performance compared to SparseGPT. We will consider additional experiments on newer models, such as LLaMA-3, in future work.\n\n---\n\n**Will you publish the code?**  \n**Reply**: If the paper is accepted, we will release the code along with detailed documentation and a usage tutorial to facilitate reproducibility and further research.\n\n---\n\n**How fast is your code compared to Wanda or SparseGPT?**  \nWe compare the runtime of mAIHT, Wanda, and SparseGPT for pruning the LLaMA-7B model. The results, including the time required to generate input activations, are as follows:\n\n| |Time (s)|\n|---|---|\n|Wanda|148.55|\n|SparseGPT|609.04|\n|mAIHT|1370.79|\n\nWhile mAIHT is slower than other methods due to its advanced gradient-based optimization for layerwise reconstruction, its pruning time remains negligible compared to LLM fine-tuning. For reference, Wanda [1] reports that fine-tuning LLaMA-7B with LoRA takes 24 hours on a V100 GPU, while full fine-tuning requires 24 days. In contrast, mAIHT prunes the model in under 30 minutes.\n\n---\n\n**Reply to the Concerns in Claims and Evidence**:  \nWe appreciate the reviewer's concern. While our method primarily focuses on unstructured pruning, it can be extended to handle structured pruning (e.g., n:m sparsity, hierarchical sparsity, block sparsity, and row sparsity). For further details and experimental results, please refer to our response to Reviewer iY6M.\n\n---\n\n**Reply to Experimental Designs or Analyses**:  \nWe thank the reviewer for the insightful suggestion regarding our experimental design. Using projected gradient descent (PGD) to refine weights aligns naturally with our approach. The gradient descent step provides a warm start, bringing the solution close to optimality. PGD then fine-tunes the weights efficiently within the sparsity constraints.\n\nTo study the impact of refinement, we conducted an ablation experiment on the LLaMA-7B model with 0.5 sparsity. The results on Wikitext-2 perplexity are as follows:\n\n| |Perplexity|\n|---|---|\n|SparseGPT|7.2397|\n|mAIHT (without refining)|7.0843|\n|mAIHT|7.0720|\n\nEven without refinement, mAIHT achieves better results than SparseGPT. This suggests that proximal gradient descent implicitly refines retained parameters, unlike SparseGPT. The additional refinement step further improves performance, demonstrating its effectiveness.\n\n[1] Sun, M., Liu, Z., Bair, A., & Kolter, J. Z. A Simple and Effective Pruning Approach for Large Language Models.", "claims_and_evidence": "The theoretical claims are well supported with rigorous statements and proofs. These hold irrespective of the the application area (e.g. large language models). \n\nThe empirical claims \"outperforms state of the art pruning techniques\" is not supported enough IMO. They are only conducted on Llama-7B, which is an outdated model and also quite small. To profoundly support this claim, I'd expect more results on other and more modern models. Furthermore I strongly recommend adding always the dense model performance as baseline. From Table 1 it seems that mAIHT improves, but on a very tiny scale compared to the gap to the base model.\n\nIn the abstract they say that \"pruning is an effective solution to reduce model size\". I think this is somewhat false. First, the authors only consider unstructured sparsity which cannot be run on GPU. Second the model performance drops on recent models (llama) is quite large. I do not think anyone is actually using those pruned models. The one model that comes closest is https://neuralmagic.com/blog/24-sparse-llama-smaller-models-for-efficient-gpu-inference/ but it also requires fine-tuning after pruning. I thus recommend to tone down a little bit.", "methods_and_evaluation_criteria": "The proposed methodology is very reasonable and fits the use case very well. As mentioned above, the empirical evaluation is not sufficient.", "theoretical_claims": "I checked Proposition 2.1 in detail and skimmed the other proofs.", "experimental_designs_or_analyses": "Beyond the limitation of the evaluation in terms of datasets, I am wondering to what part of their innovation they attribute the improvement. Are they finding a better mask or do they better optimize the remaining weights? [1] reports that applying masked gradient updates also improves wanda and sparsegpt. Can you add some ablation? \n\nAlso in section 2.4 you say that you use a projected gradient descent step after freezing the sparsity pattern (line 9 in the algorithm). AFAIK SparseGPT does not do this. Or can you point me to where they do it (either code or paper)? I think this might be a novelty of the present work. Concurrent work [1] also uses it, but does not need to be considered due to recency.\n\nWhat's also missing is a/ code to reproduce the results b/ a rough number how long the method takes in wall clock time. Whilst it is usually much smaller than training a model, for the research community it matters a lot.\n\n\n[1] A Proximal Operator for Inducing 2:4-Sparsity (https://arxiv.org/abs/2501.18015)", "relation_to_broader_scientific_literature": "The relation to broader literature are appropriately given. The main established baselines are Wanda and SparseGPT and it also considers more recent work.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "This is a rather theoretical paper. I think it's theoretical contribution is strong and relevant beyond how well it works on the currently hyped LLMs.\n\nOn the other hand, the empirical improvements on LLM pruning are negligible.", "other_comments_or_suggestions": "- in Section 3, line 196, I think it is worthwhile adding a sentence why this is the lipschitz constant of the gradient. Might not be clear to all readers.\n- the formatting on page 5 is over the boundaries. Please fix this. you have enough space left.\n- Section 4.1 line 307. Notice that this is exactly the change that moves magnitude pruning to Wanda. It might be worth mentioning this to the reader.", "questions_for_authors": "Can you get results on a Llama 3.1 model and also on a 70B model? \n\nWill you publish the code?\n\nHow fast is your code compared to Wanda or SparseGPT?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper addresses the challenge of pruning Large Language Models (LLMs) to reduce computational and storage costs without retraining. The authors reformulate the pruning process as a penalized optimization problem and propose a “monotone accelerated Iterative Hard Thresholding” (mAIHT) method. They provide detailed theoretical analyses—covering convergence, convergence rates, and risk upper bounds—and demonstrate experimentally that their approach outperforms several state-of-the-art pruning techniques for LLaMA-7B on tasks such as WikiText2 (perplexity) and multiple zero-shot benchmarks.

The paper received reviews which lean towards acceptance. Even the review with score of 2 reads to me as a positive evaluation of the work. I have read the reviews, rebuttals, and ensuing discussion. 

The reviewers found the paper's strengths to include:
- Clear theoretical foundation, which is relatively uncommon for LLM pruning papers. (However, IHT and accelerated variants have been known for a long time; first developed in the compressed sensing literature)
- Practical and easily implemented (layer-wise) method that converges quickly.
- Strong empirical gains at moderate sparsity levels.
- Helpful ablation-like results on reconstruction error across multiple iterations.

Weaknesses include:
- Although the method performs well at moderate sparsities, there is somewhat less emphasis on extremely high sparsity (e.g., 90%+).
- The approach relies on a small calibration set that can induce overfitting on C4 dataset nature.
- Integration with quantization or other compression techniques remains an open question.
- Only one model: LLaMA-2 7B was considered. It is common in pruning papers to include more experimental results with more models (LLaMa-3 from 1B up to 70B)
- Practicality of the work: it is not well explained why do we need sparsity in LLM. e.g. in quantization we gain memory because it is much easier to store low-bit representation of the weight, but sparsity (unstructured) is not that applicable.

As a result, I recommend acceptance with the expectation that the authors will fully integrate their detailed responses into the paper, plus handle all other relevant criticism (I'll let the authors apply judgement to what criticism is valid and handling of which will improve the paper).

AC
Decision: Accept (poster)