# An Efficient Matrix Multiplication Algorithm for Accelerating Inference in Binary and Ternary Neural Networks

arXiv: https://arxiv.org/abs/2411.06360 · HTML: https://mlsanity.com/paper/2411.06360/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 30 references that are in the map.
- First posted on arXiv 10 Nov 2024.

## Builds on (most cited first, 18 of 18)

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [BinaryConnect: Training Deep Neural Networks with binary weights during propagations](https://mlsanity.com/paper/1511.00363/) (2015)
- [Quantized Neural Networks: Training Neural Networks with Low Precision Weights and Activations](https://mlsanity.com/paper/1609.07061/) (2016)
- [A Survey on Large Language Model (LLM) Security and Privacy: The Good, the Bad, and the Ugly](https://mlsanity.com/paper/2312.02003/) (2023)
- [The Era of 1-bit LLMs: All Large Language Models are in 1.58 Bits](https://mlsanity.com/paper/2402.17764/) (2024)
- [Quantized Convolutional Neural Networks for Mobile Devices](https://mlsanity.com/paper/1512.06473/) (2015)
- [Trained Ternary Quantization](https://mlsanity.com/paper/1612.01064/) (2016)
- [BitNet: Scaling 1-bit Transformers for Large Language Models](https://mlsanity.com/paper/2310.11453/) (2023)
- [Security and Privacy Challenges of Large Language Models: A Survey](https://mlsanity.com/paper/2402.00888/) (2024)
- [EfficientQAT: Efficient Quantization-Aware Training for Large Language Models](https://mlsanity.com/paper/2407.11062/) (2024)
- [Examining Zero-Shot Vulnerability Repair with Large Language Models](https://mlsanity.com/paper/2112.02125/) (2021)
- [VS-Quant: Per-vector Scaled Quantization for Accurate Low-Precision Neural Network Inference](https://mlsanity.com/paper/2102.04503/) (2021)
- [Logits of API-Protected LLMs Leak Proprietary Information](https://mlsanity.com/paper/2403.09539/) (2024)
- [Discovering Low-Precision Networks Close to Full-Precision Networks for Efficient Embedded Inference](https://mlsanity.com/paper/1809.04191/) (2018)
- [Fast Matrix Multiplications for Lookup Table-Quantized LLMs](https://mlsanity.com/paper/2407.10960/) (2024)
- [Minimum Energy Quantized Neural Networks](https://mlsanity.com/paper/1711.00215/) (2017)
- [ViT-1.58b: Mobile Vision Transformers in the 1-bit Era](https://mlsanity.com/paper/2406.18051/) (2024)
- [Fast matrix multiplication for binary and ternary CNNs on ARM CPU](https://mlsanity.com/paper/2205.09120/) (2022)

## Built on by (most cited first, 3 of 3)

- [Frequency Matters: Fast Model-Agnostic Data Curation for Pruning and Quantization](https://mlsanity.com/paper/2603.16105/) (2026)
- [RSR-core: A High-Performance Engine for Low-Bit Matrix-Vector Multiplication](https://mlsanity.com/paper/2603.27462/) (2026)
- [SSR: Sparse Segment Reduction for Ternary GEMM Acceleration](https://mlsanity.com/paper/2610.08403/) (2026)

## Abstract (arXiv)

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× n weight matrix, our efficient algorithm guarantees a time complexity of O(fracn2log 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.