通过预处理权重矩阵，实现二值/三值神经网络的高效推理加速。
An Efficient Matrix Multiplication Algorithm for Accelerating Inference in Binary and Ternary Neural Networks
- 利用训练后权重不变特性，预建索引压缩存储并优化矩阵乘法。
- 理论复杂度降至 $O(n^2 / \log n)$，实测推理提速最高达29倍、内存减少6倍。
- 特别适合部署在资源受限设备上的大语言模型等二值/三值网络。
尽管深度神经网络（如大语言模型）取得巨大成功，但其推理效率低下且依赖高端计算设施。为解决这一问题，本文提出算法提升二值与三值权重神经网络的推理速度与内存效率。聚焦于推理中的瓶颈操作——矩阵乘法，我们发现训练完成后权重矩阵不再变化，因此可预先处理并构建索引，以对数因子降低存储开销，并实现高效推理。针对 $n imes n$ 的权重矩阵，我们的算法保证时间复杂度为 $O(n^2 / \log n)$，较标准向量-矩阵乘法有对数因子优化。实验表明，该方法在时间和内存上均具显著优势：矩阵乘法耗时最多降低29倍，内存使用最多减少6倍；应用于大语言模型时，推理速度最高提升5.24倍。
原文摘要 · Abstract (English)
Despite their tremendous success and versatility, Deep Neural Networks (DNNs) such as Large Language Models (LLMs) suffer from inference inefficiency and rely on advanced computational infrastructure. To address these challenges and make these models more accessible and cost-effective, in this paper, we propose algorithms to improve the inference time and memory efficiency of DNNs with binary and ternary weight matrices. Particularly focusing on matrix multiplication as the bottleneck operation of inference, we observe that, once trained, the weight matrices of a model no longer change. This allows us to preprocess these matrices and create indices that help reduce the storage requirements by a logarithmic factor while enabling our efficient inference algorithms. Specifically, for a $n\times n$ weight matrix, our efficient algorithm guarantees a time complexity of $O(\frac{n^2}{\log n})$, a logarithmic factor improvement over the standard vector-matrix multiplication. Besides theoretical analysis, we conduct extensive experiments to evaluate the practical efficiency of our algorithms. Our results confirm the superiority of our approach both with respect to time and memory, as we observed a reduction in the multiplication time up to 29x and memory usage up to 6x. When applied to LLMs, our experiments show up to a 5.24x speedup in the inference time.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。