DiscQuant: A Quantization Method for Neural Networks Inspired by Discrepancy Theory

Q. Why not VLMs

A. We believe that experiments on vision models are beyond the reasonable scope of this paper. To the best of our knowledge, other major works on PTQ (GPTQ, QuIP, OmniQuant, etc) focus on LLMs only. However, our method is general and can be used on CNNs or vision transformers.

Q. Experiments on Larger LLMs

A. We have initiated experiments on Llama-3-70B, but given our limited resources we cannot finish the experiments (especially hyperparameter tuning) in time for the rebuttal. We will update the paper with results as soon as we can get them.

Q. On Data and resources

A. In our experiments we only use several thousand samples from an open source dataset called RedPajama which should make our method accessible to any practitioner. Our experiments in Section 5.3 were to show the improvement you could get from tailoring your quantization data to your task and even in those experiments we will only use a few thousand samples from the end task. So we believe that not having access to data is not a valid criticism of our method.

On the matter of compute resources, our method requires storing two copies of the model and doing backprop on one of them similar to distillation. This will require large memory and especially for extremely large models like Llama 70b or 405b this will require several GPUs. But we believe that PTQ methods should be evaluated foremost on the quality of the quantization rather than the compute resources needed. A company/lab which pretrains a model and wants to create a quantized version of that model for cheaper inference cares more about the quality of quantization rather than resources needed for quantization. In any case, the amount of resources needed for quantization using our method or most PTQ methods is negligible compared to the pretraining costs. Therefore we appeal to the reviewer to not see this as a serious shortcoming.

Q. Why only search up/down in the quantization grid.

A. Great question! So many resources are spent on pretraining and aligning modern LLMs. We do not want our quantization method to change the original model too much, especially because it is common to use only a couple thousand samples for calibration during PTQ. By only searching up/down in the quantization grid, we are ensuring that trillions of tokens worth of training is not overwritten by several thousand tokens worth of post training quantization. Relaxing this design choice may degrade the LLM in ways not captured by the relatively simple benchmarks that are commonly used to evaluate quantized models.

Q. Will you release code?

A. Yes!

Thanks to the authors for their efforts in responding! Thanks for conducting Llama-70B experiments as well. My apologies for the delayed response.

Regarding data and resources: my original comment was largely concerned with data, but I believe that Reviewer 7uqc expresses a similar concern more effectively, saying, "it is not that fair to claim the superior performance of DiscQ from comparisons with PTQ methods, provided that the costs are much higher than those PTQ methods". I am curious to see the authors' clarification on this.

Resource efficiency is critical, and the argument that this is insignificant compared to what's spent in pre-training, seems, in my opinion, to unfairly downplay the issue. Regardless of availability, one would generally seek to minimize resource expenditure, if doing so does not degrade the outcome significantly. Beyond that, there also lies the matter of complexity: the more complex a method is (simply in terms of running it, for example), the less significant its performance gains become and the harder it is to debug. Consider the very general case (that still applies here) where one needs to set up a third-party codebase and adapt it to their application. Given two third-party implementations with similar resource expenditure, one would generally use another tie-breaking criterion such as simplicity or ultimate performance gain: this would be done to justify the expenditure of an engineer's time, which is arguably a more expensive resource than compute. This is why it becomes so important to compare with methods that use similar resources.

Given the currently available information, I will maintain my score of acceptance but with reservations.

Q. “Why can’t you directly run distillation or quantization-aware training for better compression and better performance”

A. Thanks for asking us to clarify. Our method has similar memory requirements as distillation, where we hold two copies of the model in memory. And like distillation, we optimize one copy of the weights. However, our method uses only a couple thousand samples, which is negligible compared to what is required for distillation or quantization aware training or full model training which require training again on a significant portion of the pretraining data. We believe that the statement “the cost is almost the same as training the full model” needs this additional context. Though per iteration costs are similar, our method requires way less samples and iterations and therefore not comparable to these methods. And while our method requires greater computational resources than GPTQ, we have shown that it achieves superior compression. So we do not believe that our method should be summarily rejected as a PTQ method because of its computational requirements. Ultimately, when a company which trained a model wants to create a quantized version of their model, they do have the resources to apply any method to quantize it. What matters more in this case is the quality of the quantized model rather than the amount of resources needed to quantize it. In any case, the resources needed for our method and most PTQ methods is negligible compared to pretraining.

Q. Comparison with SOTA PTQ methods

A. Thanks for asking. We ran the recent SOTA OmniQuant [1] method in our experimental setting: Llama-3-8B-Instruct on the Wikitext, PIQA, and HellaSwag tasks. We run the OmniQuant method from their official github, using their default parameters for weight-only quantization. We add the --symmetric argument to match the symmetric quantization grid used in our experiments. We see that our method DiscQuant beats OmniQuant on all tasks and at all bit settings.

Also, we do compare against QuIP, see Section 5.2.

[1] Shao, Wenqi, et al. "Omniquant: Omnidirectionally calibrated quantization for large language models." arXiv preprint arXiv:2308.13137 (2023).

Q.Thm 3.3 weight distribution

A. Great question! As you rightly pointed out, the quantization error will depend on the distribution of weights as well. In our modeling, we made the simplifying assumption that the quantization grid is uniform and fine enough to always give a plus-minus delta approximation to each true weight. Therefore the quantization error depends on delta as well. See the equation in Section 3.1 for this which states that quantization error $\approx \delta \langle \nabla_w f(w;s),x-y \rangle$. In Theorem 3.3, we ignored this delta factor since it is a constant and only focused on the $\langle\nabla_w f(w;s),x-y\rangle$ part. In Appendix C, we have clarified what happens when the quantization grid is not uniform, in this case, as you pointed out, the quantization error will also depend on the distribution of weights since the matrix $M$ will have gradients scaled by $(w^{up}-w^{down})$. In this case, the generalization bound in Theorem 3.3 will need to assume that the covariance of these scaled gradients need to have decaying eigenvalues and the exact theorem continues to hold. If you think this is worth explaining in detail, we are happy to add this theorem in the appendix and write a footnote in the main body.

Q. Expanding on discrepancy theory; more intuition on the algorithm, complexity of Lovett Meka.

A..We regret that we couldn’t provide a more detailed introduction and connections to discrepancy theory in the main body of the paper due to lack of space. We explained the connection briefly in Section 3.1. To recall, $M$ is the matrix whose rows are per-sample gradients and we are given some fractional $y\in [0,1]^n$ which corresponds to the true weights. Our goal is to find an $x\in \\{0,1\\}^n$ such that $M(x-y)\approx 0$ (which corresponds to making the first order approximation of quantization error zero). A famous result of Lovasz et al. 1986 (cited in Section 3.1) shows that

$\min_{x \in \\{0,1\\}^n} ||M(x-y)||_{\infty} \le herdisc(M)$

where $herdisc(M)$ is the hereditary discrepancy of M defined as

$herdisc(M)=\max_{S \subset [n]} \min_{z\in \\{-1,1\\}^S} ||M_S z||_{\infty}$

where $M_S$ is the submatrix of $M$ formed by columns $S\subset [n]$. And there are many well-known techniques to bound herdisc(M). We didn’t go into details because of lack of space. But if the reviewers think it is useful, we can add an appendix elaborating on these connections and also give a gentle introduction to discrepancy theory.

One important distinction concerns separating our analysis from our method. Discrepancy theory, including the Lovett-Meka algorithm, was used to obtain a generalization bound and obtain novel insights on the quantization problem. It just proves mathematically that low-rank gradient structure can imply existence of good quantization. However, we do not use Lovett-Meka in our actual method as it is very expensive to run as the reviewer correctly pointed out. It involves solving a Gram-Schmidt orthonormalization process at each step of the algorithm which is infeasible when the dimension n is in the order of billions such as in LLMs. Therefore our actual method DiscQuant minimizes KL divergence and a linear regularization term using a standard stochastic gradient descent approach. We explained why this is morally similar to finding a vertex of the polytope in Section 4. Recall from Fig 1 that our rounding solution lies on a vertex of polytope “K”. In order to find any vertex, we can maximize $\langle c,x \rangle$ such that $x \in K$, for any direction $c$. It is a well-known fact in linear programming that a linear function is always maximized or minimized at a vertex of a polytope. Intuitively, we can see this by imagining placing a ball inside a convex polytope and let it fall under the action of gravity, it will eventually stop at a vertex of the polytope (if the orientation of the polytope is randomly chosen which is equivalent to choosing a random direction $c$, then almost surely it will not have any horizontal surface where the ball can rest).

Our final algorithm DiscQuant just uses standard (projected) stochastic gradient descent to minimize the objective (3) in Section 4, so it only requires computation of average gradient on a batch of samples for each step using standard backprop. It does a descent step followed by a projection step onto the hypercube which can be achieved by clamping the x parameters to [0,1].

Q. Is gradient covariance within a layer, or for the entire model?

A. We are discussing the gradient covariance with respect to the entire model and we use n to denote all the parameters of the model. Note that our method does not compute this covariance matrix explicitly; we reason about this matrix in our analysis to prove the generalization bound. As explained in the top of Section 5, our method has similar memory requirements as knowledge distillation, which also requires holding two copies of the model in memory. We perform backpropagation and optimize one copy of the model weights. However our method only uses a few thousand samples, far fewer than pretraining, distillation, or quantization aware training.

I thank the authors for the clarifications and responses. Some further thoughts:

While I appreciate the explanations here, what I was hoping for was a more intuitive understanding of the method. Typically, readers who aren't familiar with the literature of a paper, can only "compile" the theoretical statements, but cannot gain insights into the theories. These insights will be crucial in how they will apply the method, and diagnose it if it doesn't work quite well. In that sense, the explanations provided here don't really address my concern on clarity of the presentation.

Some suggestions:

• Can authors provide a toy example (either here or in the paper) of how DiscQuant works? If possible, that would go a long way in clearing up some details?
• Can this toy example, or some other example, explain intuitively why the low-rank assumption helps better quantization?
• Can authors write a pseudo-code for DiscQuant, with clear explanations for all the terms there (rather than a vague "n" term, mention it represents all parameters, or what $c$ means, etc). Also can they provide a complexity estimate?

follow-ups on low-rank:

• Since authors clarify $n$ denotes all parameters of the model, does the low-rank structure somewhat arise from the fact that interactions between different components is very small compared to interactions within a module? For example, parameters within a fully connected layer have a lot of interaction, as opposed to two different layers. Is this the type of low-rank structure that is needed here? Or should the low rank go beyond this, and even the gradients within a fully connected layer must be low-rank?
• I read the discussion in response to reviewer TWTt, but I am still unsure what authors are implying here. Are authors suggesting low-rank assumption is necessary for theoretical analysis, or is it actually needed in practice too? In other words, if it's violated, is it likely that DiscQuant (or other methods) fail in practice too?

Second follow-up: Since the "method" is not really LM algorithm, can they clarify if the main Theorems presented are for LM algorithm, or for the approximate rounding technique used in DiscQuant? The language of the theorems " ... there is a polynomial time algorithm ... " is very vague and leaves a lot of room for interpretation here. The subsequent section 4 does not clarify this either.

Q. A more intuitive understanding of the method

A.. We will include a more approachable explanation for our method in the paper. We believe that the geometric interpretation in Figure 1 provides the best intuition. Our introduction provides a thorough but perhaps too technical explanation of this intuition, but we will try and restate it here.

We reparametrize the model weights as $w^x =(1-x)\cdot w^{down}+x\cdot w^{up}$ by interpolating between the rounded down weights $w^{down}$ and rounded up weights $w^{up}$. We now consider $x$ as the trainable parameters which are constrained to the hypercube $H=[0,1]^n$ as in Figure 1. A full rounding corresponds to a vertex of the hypercube $x\in \\{0,1\\}^n$. If $x_i=0$, then the $i^{th}$ parameter $w_i$ is rounded down and if $x_i=1$, then the $i^{th}$ parameter is rounded up. Our problem therefore is to push all optimization parameters to either $0$ or $1$, corresponding to either rounding down or up to the nearest points on the quantization grid.

But any rounding will not do; we want to ensure that our rounding does not degrade the model. By looking at the first order taylor approximation of the rounding error, this can be written as a set of linear constraints on $x$. This constraint corresponds to the hyperplane $V$ in Figure 1. So in order to round the parameters and have low model degradation, we need to find points of $V$ intersected with the hypercube $H$ with many coordinates set to 0 or 1. This corresponds to finding vertices of the polytope $K= V \cap H$, shown as red points in Figure 1. If the dimension of $V$ is $n-m$, then these vertices have $n-m$ values set to 0 or 1 and at most $m$ values which are still fractional. So we want $m$ to be small to find a nearly full rounding. Now this is where the low-rank assumption comes in. The $m$ here is approximately the rank of the gradient space, so low rank implies an almost fully rounded solution with low rounding error.

Now how does DiscQuant solve this problem. Firstly we can’t even store the subspace $V$ explicitly since storing it will require storing an $m \times n$ matrix where $n$ is the number of parameters and $m$ is a few thousand. Therefore we instead solve: $\min_x D_{KL}(f(w; s) || f(w^x;s)).$ The set of $x$ which minimize this objective roughly corresponds to the subspace $V$ as shown in the equations in Section 4. Now our goal is to find $\min_{x\in \\{0,1\\}^n} D_{KL}(f(w; s) || f(w^x;s)).$ This is a discrete optimization problem, so we need to relax it to a continuous optimization problem. $\min_{x\in [0,1]^n} D_{KL}(f(w; s) || f(w^x;s)).$ But the solution to this is trivially zero which happens when $w^x=w$, i.e., no rounding has actually taken place. So add a linear penalty term which forces each $x_i$ to be either $0$ or $1$. We have already given intuition in our previous response why optimizing a linear penalty over a convex polytope leads us to a vertex. Therefore the final objective is:

$\min_{x\in [0,1]^n} L(x;s)=D_{KL}(f(w; s) || f(w^x;s)) +\lambda \langle c , x \rangle.$

Finally, we choose $c$ in a special way such that vertices of the hypercube which are closest to the original weights are preferred (last equation in Section 4). So we are not repeating this simple calculation here.

We solve this objective using projected stochastic gradient descent as follows: DiscQuant Psuedocode:

For $t=1$ to $T$:

• Sample $s_1,s_2,\dots,s_B\sim D_{data}$ from the calibration data
• $g=\frac{1}{B} \sum_{i=1}^B \nabla_x L(x;s_i)$
• $x \leftarrow x- \eta g$ #descent step
• $x \leftarrow clamp(x,0,1)$ #project to hypercube

$\hat{x}\leftarrow round(x)$ #At this point, most $x_i$ should be close to $0$ or $1$. Round whatever is left to $0$ or $1$ greedily.

Output $\hat{w}=w^{\hat{x}}$ as the quantized weights

Complexity: Each iteration takes linear time in the number of parameters $n$ and batch size $B$ and quadratic in the context length $L$ (for transformer architecture). The projection step is just clamping, so linear in $n$. Therefore total running time is $O(nBL^2T)$. This is exactly the same as usual stochastic gradient descent for standard training of transformer networks. The only extra work is to also evaluate the logits of the original model (using only the forward pass) which is a small fraction of the total cost, so will not change the asymptotics.

Q. Better explain the role of discrepancy theory and relation of DiscQuant to Lovett-Meka algorithm (random walk).

A. Thanks for pointing this out. We will provide relevant background to readers unfamiliar with discrepancy theory. We explained the connection briefly in Section 3.1. To recall, $M$ is the matrix whose rows are per-sample gradients and we are given some fractional $y\in [0,1]^n$ which corresponds to the true weights. Our goal is to find an $x\in \\{0,1\\}^n$ such that $M(x-y)\approx 0$ (which corresponds to making the first order approximation of quantization error zero). A famous result of Lovasz et al. 1986 (cited in Section 3.1) shows that

$\min_{x \in \\{0,1\\}^n} ||M(x-y)||_{\infty} \le herdisc(M)$

where $herdisc(M)$ is the hereditary discrepancy of M defined as

$herdisc(M)=\max_{S \subset [n]} \min_{z\in \\{-1,1\\}^S} ||M_S z||_{\infty}$

where $M_S$ is the submatrix of $M$ formed by columns $S\subset [n]$. And there are many well-known techniques to bound herdisc(M). We didn’t go into details because of lack of space. But if the reviewers think it is useful, we can add an appendix elaborating on these connections.

One important distinction concerns separating our analysis from our DiscQuant method. Discrepancy theory, including the Lovett-Meka algorithm, was used to obtain a generalization bound and obtain novel insights on the quantization problem. It just proves mathematically that low-rank gradient structure can imply existence of good quantization. However, we do not use Lovett-Meka in our actual method as it is very expensive to run. Our actual practical method DiscQuant minimizes KL divergence and a linear regularization term using a standard stochastic gradient descent approach which is very efficient. But the caveat is that we cannot prove the generalization bound holds for this practical method.

Q. Is the random walk to find a vertex of the polytope necessary for our generalization bound (in the Lovett-Meka algorithm)?

A. Great question! Yes, there are many ways to find a vertex of a polytope (for example maximize an arbitrary linear function on the polytope). But the random walk as done in the Lovett-Meka algorithm is necessary for our generalization bound to hold. The random walk ensures that the covariance of the vertex it finds is approximately the identity matrix and this is crucially used to prove the generalization bound. In fact, any deterministic way to pick a vertex will not generalize. But it is an interesting open question if we pick a vertex by maximizing a random linear function, then will it generalize. This is generally not true, we constructed a counter example. But with some additional assumptions, this might be true.

Q. Real world impact, compute / memory cost, deployment.

A. There is an important distinction between the one-time quantization cost, and the repeated inference cost, that we can make more clear. To clarify, our approach is not “iterative”, because we round all parameters at once. While our method has increased compute or memory costs compared to GPTQ and RTN, this is only occurred once during quantization. GPTQ only holds a single decoder layer in GPU memory. As explained in the top of Section 5, our method has similar memory requirements as knowledge distillation, which also requires holding two copies of the model in memory. Our method is a rounding algorithm; once the weights are rounded then there is no additional inference overhead or complexity compared to GPTQ or RTN.

Q. Alternative metrics beyond KL divergence.

A. Great question. Please see Table 6 in the Appendix, where try several variations of a normalized MSE between intermediate layers, and linear combinations of the KL loss and this MSE loss. We found the standard KL divergence worked best.

Q. What happens when the gradient covariance is not strongly low rank.

A. This is a great question. First of all, we are the only PTQ LLM paper which provides any kind of generalization guarantee. Doing so requires a low-rank assumption on the gradients.We can see that without low rank assumption any PTQ method will fail to generalize beyond the small calibration dataset. Suppose the gradient covariance matrix is the identity matrix $I_n$ for simplicity, i.e., it is full rank and the eigenvalues do not decay at all. In this case, any PTQ method which outputs a quantization $\hat{w}$ will incur an error of