BLAST: Block-Level Adaptive Structured Matrices for Efficient Deep Neural Network Inference

Q1. The BLAST matrix in this paper is an existing matrix structure known as BLR^2. The BLR^2 paper should be cited, and all mention of BLAST should be replaced with BLR^2.

Thank you for suggesting an important related work! We agree that BLR^2 Ashcraft, Buttari & Mary, 2021 should be cited and carefully discussed.

However, after carefully reviewing both approaches, we concluded that BLAST is not identical to BLR^2. One cannot replace BLAST with BLR^2 to obtain the same level of generality and efficiency that BLAST provides. Therefore, we think BLAST should be named as-is.

The BLAST matrix structure differs from the BLR^2 Ashcraft, Buttari & Mary, 2021 method in its left, right, and diagonal factors.
(i) The matrix ($S\_{i,j}$) of a BLAST block ($A\_{i,j}=U\_i S\_{i,j} V\_j^T$) is a diagonal matrix, whereas BLR^2 uses a low-rank matrix. Accordingly, a BLAST matrix can capture high-rank blocks with fewer parameters than BLR^2. (ii) BLR^2 restricts its shared left and right factors to have orthonormal bases, which introduces extra overhead and instability at each gradient descent update. In contrast, none of the BLAST factors have such orthonormal constraints so that the training process does not change from the conventional DNN training scheme. In revision, we will cite BLR^2 and discuss the work.

We argue that BLAST is more suitable for efficient DNN inference and simple training than BLR^2 for the following reasons:

Expressiveness: BLR^2 uses a low-rank coupling matrix whereas BLAST utilizes a diagonal matrix. As a consequence, BLAST can represent matrices that BLR^2 cannot. BLR^2's low-rank coupling factor fails to capture high-rank blocks, whereas BLAST's diagonal coupling factor can model high-rank blocks with fewer parameters.
Efficiency: Each low-rank block of a BLR^2 matrix can have a different rank, making it challenging to achieve optimal efficiency on the off-the-shelf GPUs due to zero paddings. On the other hand, the diagonal factor of a BLAST matrix does not require zero padding, allowing for faster matrix multiplication on GPUs, as illustrated in Algorithm 1 and the pseudocode in "General Comments."
Gradient Descent Compatibility: BLR^2's orthonormality constraint adds computational cost and instability during gradient descent steps in training and fine-tuning. In contrast, BLAST avoids these issues as it does not require modifications to the training process.

Therefore, unlike BLR^2, BLAST exhibits unique properties beneficial for efficient DNN inference as claimed in our paper. Once again, we truly appreciate Reviewer 2dKz's constructive suggestion to discuss BLR^2 in our work.

Q2. For CIFAR-10 and CIFAR-100, Gaudi-GBLR seems to perform better than the proposed method.

Please refer to Q3 of “Global Comments.”

Q3. Why does the paper repeatedly mention matrix-vector multiplications? The input to DNNs are not vectors.

Since matrix-matrix multiplication is composed of multiple parallelized matrix-vector multiplication, we discussed BLAST at the matrix-vector multiplication level.
We also thought the vector-shaped inputs were easier to express than the matrix-shaped or tensor-shaped inputs.
Please refer to Q4 of “Global Comments” for the actual implementation.

Q4. Why do the authors mention that "A block low-rank (BLR)

$12$ , also known as Monarch $13$ matrix"? The Monarch matrix is a very different structure from BLR.

Thank you for pointing it out. We assumed the BLR matrix has the blocks of the same rank. In this case, BLR and Monarch are equivalent up to the row permutations. Indeed, the Monarch matrix is decomposed by the block-level SVD, which results in the block low-rank matrix of the same block rank. We will clarify that we assume the same block rank for BLR.

Q5. Why are Gaudi-GBLR, BSP+LR, and BLR excluded from the compression benchmark in Table 2?

Please refer to Q2 of “Global Comments.”

We truly appreciate Reviewer 2dKz’s feedback. Please let us know whether our comments have successfully resolved all of your concerns or not. If so, we kindly request reconsidering the evaluation of our work.

Reference

Ashcraft C, Buttari A, Mary T. Block Low-Rank Matrices with Shared Bases: Potential and Limitations of the BLR ^2 Format. SIAM Journal on Matrix Analysis and Applications. 2021;42(2):990-1010.

Q1. SparseGPT deserves mention.

We agree that SparseGPT Frantar & Alistarh, 2023 is an interesting related work that deserves mention. SparseGPT uses unstructured pruning, which makes it inefficient compared to other structured matrices (including BLAST) for GPU execution since the pruned weights are randomly placed without structured patterns. Also, the SparseGPT compression process is not a data-free method since it is based on the Hessian matrix for pruning. In contrast, BLAST can be applied to data-free compression as presented in Algorithm 2, and its matrix multiplications with structured sparsity can be accelerated on off-the-shelf CUDA GPUs with significant inference speed up.
We will include SparseGPU discussion and comparison in the revision.

Q2. The result supports improved hardware efficiency but the runtime speedups in table 4 may be due to the memory and bandwidth savings.

Thank you for the insightful feedback! We agree that memory savings may be the dominant contributor to the runtime improvement in Table 4. We observed that the BLAST matrix multiplication is faster than the dense routine when the weight matrix is large enough. Yet, memory and bandwidth savings are also critical components of hardware efficiency, thus should be rewarded.
Moreover, there is room for improvement to further optimize the BLAST matrix multiplication kernel using optimized / modified CUDA functions, which we left for future work. The optimized kernel can be realized augmenting the gain from computation savings and the reduced memory access overhead.

Q3. The authors stress that U and V are shared along rows and columns, but it's unclear why this is so important.

By sharing U and V factors, we can significantly reduce the number of parameters while being able to model multiple structures by the diagonal factors. If the bases are not shared, more parameters are required to achieve a similar level of expressivity.
Indeed, a BLAST matrix without parameter sharing is identical to a Monarch (i.e., BLR) matrix. Under a similar number of parameters, BLAST matrices outperform BLR matrices in DNNs’ accuracy as we showed in Figures 5, 6, and Table 1.

Q5. Why are some baselines skipped for data-free compression?

Please refer to Q2 of “Global Comments.”

Q6. Compression rates of 10%-20% are fairly limited. What happens at higher compression rates? . Fine details are missing in the images generated by a diffusion model with BLAST weights, although BLAST shows better image quality than Low Rank.

Compressing the LLMs with structured sparsity (including structured matrix) is extremely challenging. The 20% compression ratio was chosen and accepted in the previous work on structured LLM compression (LLM-Pruner $30$ ). Note that LLM-Pruner is not data-free, whereas BLAST does not need any data to compress LLM. Still, BLAST outperforms LLM-Pruner in Table 3 with noticeable gaps.

We conducted additional experiments on 30% compression ratio for diffusion models (Figure A in the attached pdf) and on 40~50% compression ratio for Llama-7B (Figure B in the attached pdf). Despite the difficulty of the data-free compression task beyond 20% ratio, the additional results show that BLAST preserves more accuracy on zero-shot classification and more details on image generation than the non-learnable baselines.

For the generative tasks (e.g., Figure 1 and Table 3), we stress that the goal of model compression is not necessarily to reproduce the outputs of the original model. The main focus should be on whether the compressed models’ outputs have details that look realistic (i.e., whether the ‘compressed’ generative model is still a valid model for the generative task). Based on the quantitative results in Table 2, we show that the perceptual quality of the BLAST-generated images is close to the quality of the images generated by the uncompressed model.

Q7. Is matrix-matrix multiplication built by performing multiple matrix-vector products (Algorithm 1), or is there something more clever that can be done?

Please refer to Q4 of “Global Comments.”

Q8. What is the difference, in line 100, between "learning" and "finding" the structure of a weight matrix?

We differentiate “learning” and “finding” in the following manner: “learning” indicates the structure of a weight matrix is inferred by minimizing the DNN’s prediction loss which involves datasets, whereas “finding” is reserved for the data-free compression in Algorithm 2.

Q9. What rank r is used for the experimental results?

We vary the rank of the BLAST matrix (from 48 to 192) to adjust the compression ratio of the models in Figure 5 and Figure 6. For ImageNet training experiments in Table 1, we use r=128.

Q10. What batch size and input sequence length was used for the results in Table 4?

The batch size was set to one, and the length of the input sequence was set to 3. Specifically, we used the following prompt to let the model generate the desired sequence length: “Increasing sequence: one,” and stopped the generation process when the generated sequence length approaches L=10, 100, or 1000.

Q11. Figure 4 is lacking vertical axis labels.

The normalized Frobenius norm error was used in the vertical axes of Figure 4. We will include the label.

Q12. This technique seems like it'd need extra work to apply to higher-dimensional tensors.

We do not see a straightforward approach to extend BLAST to high-dimensional tensors. We will discuss this as one of the limitations.

We truly appreciate Reviewer xrxa’s feedback. Please let us know whether our comments have successfully resolved all of your concerns or not. If so, we kindly request reconsidering the evaluation of our work.

Reference

Frantar E, Alistarh D. Sparsegpt: Massive language models can be accurately pruned in one-shot. In International Conference on Machine Learning 2023 Jul 3 (pp. 10323-10337). PMLR.

def blast_matmul(
        X,  # input,        shape=(B, n, q*b), B=batch_size, n=num_seq
        U,  # left factor,  shape=(b, p, r), b=num_blocks, r=rank
        S,  # diag factor,  shape=(b, b, r)
        Vt, # right factor, shape=(b, r, q)
    ): # output = X @ A.T where A is a BLAST matrix of shape (b*p, b*q).
    B = X.shape[0]
    n = X.shape[1]
    b = U.shape[0]
    r = U.shape[2]
    q = Vt.shape[2]
    p = U.shape[1]

    X = X.view(b, B*n, q) #rearrange(b, B*n, q)
    Y = torch.bmm(X, Vt.mT) # multiply right factor
    Z = Y.unsqueeze(0) * S.unsqueeze(2) # multiply diagonal factor
    Z = Z.sum(1) # aggregate, shape=(b, B*n, r)
    Out = torch.bmm(Z, U.mT) # multiply left factor
    return Out.view(B, n, b*p)

r = comp_rate*n / (2 + (b*b/n))  # find the exact r to achieve comp_rate (0.0 .. 1.0) memory savings
r = int((r//16) * 16)  # set to the next-lowest multiple of 16 for hw-friendliness (next-lowest results in more compression than strictly necessary)

Q1. The significance of the proposed method remains unclear. Compared with prior methods such as Gaudi-GBLR

$14$ , the accuracy results of this work do not show consistent superior performance nor with a convincing explanation.

Please refer to Q3 of “Global Comments.”

Q2. The method does not seem to improve efficiency much, showing limited significance.

Firstly, the number of parameters in the ViT model for ImageNet classification is reduced by 72.2% with BLAST, while achieving higher accuracy than Gaudi-GBLR and even the dense baseline. This was done without any hyperparameter tuning. Also, unlike Gaudi-GBLR which requires specialized hardware and/or library to achieve inference speed-up (which has not been demonstrated), BLAST shows significant speed-up on off-the-shelf CUDA GPUs.

Secondly, compressing the LLMs with structured sparsity (including structured matrix) is extremely challenging. The 20% compression ratio was chosen and accepted in the previous work on structured LLM compression (LLM-Pruner $30$ ). Note that LLM-Pruner is not data-free, whereas BLAST does not need any data to compress LLM. Still, BLAST outperforms LLM-Pruner in Table 3 with noticeable gaps.

Lastly, we conducted additional experiments on 30% compression ratio for diffusion models (Figure A in the attached pdf) and on 40~50% compression ratio for Llama-7B (Figure B in the attached pdf). Despite the difficulty of the data-free compression task beyond 20% ratio, the additional results show that BLAST preserves more accuracy on zero-shot classification and more details on image generation than the non-learnable baselines.

For the generative tasks (e.g., Figure 1 and Table 3), we stress that the goal of model compression is not necessarily to reproduce the outputs of the original model. The main focus should be on whether the compressed models’ outputs have details that look realistic (i.e., whether the ‘compressed’ generative model is still a valid model for the generative task). Based on the quantitative results in Table 2, we show that the perceptual quality of the BLAST-generated images is close to the quality of the images generated by the uncompressed model.

Q3. How different is this work compared with block sparse + low-rank

$23$ and Gaudi-GBLR $14$ ?

Please refer to Q1 of “Global Comments.”

Q4. The paper

$23$ is not introduced before use in experimental results.

Thank you for pointing this out, we will introduce it before the experimental result section.

Q5. In Table 4, when L is 100, the execution time of 20% compression ratio increases compared with no compression. What is the reason?

Table 4 actually shows that the execution time decreases with compression with L=100. This may have been an error made by the reviewer.

Q6. Please provide more details that the learned BLAST matrix structures do not need any library function customization. What is specifically used as the backend compute kernel?

Please refer to Q4 of “Global Comments.”

We truly appreciate Reviewer V5GM’s feedback. Please let us know whether our comments have successfully resolved all of your concerns or not. If so, we kindly request reconsidering the evaluation of our work.