An Efficient Matrix Multiplication Algorithm for Accelerating Inference in Binary and Ternary Neural Networks
Authors: Mohsen Dehghankar
Mahdi Erfanian
Abolfazl Asudeh
Venue: ICML 2025 poster (2025)
Keywords: Deep Learning
Large Languange Models
Matrix Multiplication
Quantized Neural Networks
Algorithm Design
Primary area: deep_learning->algorithms

Abstract: 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.

An Efficient Matrix Multiplication Algorithm for Accelerating Inference in Binary and Ternary Neural Networks
Mohsen Dehghankar' Mahdi Erfanian Abolfazl Asudeh
Abstract
efficiency. These models demand substantial computational resources, including specialized, costly GPUs with ample memory to achieve real-time inference. This inefficiency leads to slower response times, clevated energy consump- tion, higher operational expenses, and, particularly, limited accessibility for everyday users who lack access to advanced computational infrastructure. For instance, current deploy- ments of LLMs on typical consumer devices rely predom- inantly on API calls to powerful, remote servers (OpenAl
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 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 n X n weight matrix, our effi- cient algorithm guarantees time complexity of n
2024 Hu et al., 2021; Hugging Face While this approach enables users to leverage LLMS without needing advanced hardware, introduces additional costs and delays due to network dependency. along with po- tential privacy concerns stemming from data transmitted
2024
A121 Labs
2023
and processed by external servers Yaao et al.,
2024 Pearce
et al. 2023
Das et al. 2024 Finlayson et al.
2024
Consequently, optimizing inference time and memory elfi- ciency on standard, widely available hardware has become essential to make DNNs more practical and accessible for broader, real-world applications.
( Ting logarithmic factor improvement over the standard vector-matris multiplication. Besides theoretical analysis, we conduct extensive exper- iments 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 mul- tiplication time up to 29x and memory usage up to 6x. When applied to LLMs, our experiments show up 5.24x speedup in the inference time.
To that end, recent efforts have focused quantizing the weights of DNNs, to enhance their computational efficiency and reduce energy consumption (Moons et al.
2017 Hubara
et al.
2018 Wang et al., 2023 Chen et al. 2024 Ma et al.
2024 For example. limiting the weights to ternary values (-,0 1) in 1.58-bit LLMs has demonstrated to preserve
accuracy comparable to that of general LLMs, thereby of- fering more effective alternative for inference tasks (Mal ct al. 2024
Expanding on recent advancements of DNNs with binary and ternary weights, in this paper, we propose algorithms that improve their inference time and memory efficiency. Our approach makes deploying these models viable on a broader range of devices, including those with limited com- putational power, ultimately making these tools more widely accessible and cost-effective.
1. Introduction
Deep Neural Networks (DNNs) such as Large Language Models (LLMs) have achieved remarkable success and demonstrated versatility across wide range of domains, yet they encounter significant challenges related to inference in-
'Department of Computer Science, University of Illinois Chicago, Chicago, USA. Correspondence to: Mohsen Dehghankar Emdehgh2@uic.cdt uic.edu>>
Specifically, while viewing the inference process as se- quences of multiplying activation vectors to weight matrices, we make a critical observation: once the model is trained, the weight matrices remain fixed and do not change.
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
RRelated Work is further discussed in Appendix B

---

An Efficient Matrix Multiplication Algorithm for Accelerating Inference in Binary and Ternary Neural Networks
Following this observation, while focusing on matrix mul- tiplication as the bottleneck operation, we preprocess the weight matrices of the trained model and create indices that enable efficient multiplication during the inference time. At a high level, our indices are bucketized permutation lists. Interestingly, by replacing each weight matrix with its preprocessed indices, our approach reduces the space complexity of storing the weights by logarithmic factor.
We explain the generalization of our algorithms beyond binary and ternary settings in Section 4.4 and discuss parallelization in Appendix C.1
Sections 5 We conduct various experiments to demon- strate the applicability of our algorithms for matrix multi- plication using different implementation configurations. We show that we can achieve up to 29x faster run time and 6x less space usage on matrix multiplication. We also conduct experiments on 1.58-bit L...s. We discuss our approach's ' advantages and limitations in Appendix D
We propose two algorithms for efficient multiplication of input vectors to the preprocessed weight matrices. When the weight matrices are ternary, our algorithms first trans- form those into pairs of binary matrices. Next, each binary matrix is partitioned into a set of column blocks. Then, permuting the rows based on a lexical order, we compute a set of aggregate values that contribute to different ele- ments of the result vector. This process guarantees time complexity of O( log(n))log log(m)) ) for n x n matrices in our first algorithm. Furthermore, introducing an efficient approach for writing the aggregate values in the result vec- tor, our second algorithm improves the time complexity to ( [og(n)) ). The run-timg time of our algorithms further improves by fine-tuning their blocking parameter. Many widely used advanced DNNs are characterized by weight matrices of substantial sizes. For instance, the matrix size of GPT-3 12,288 (= 213 (Tsai 2020 Tech 2023 Brown 2020), and this value is even greater for GPT-4. Consequently, achieving even logarithmic factor improvement can have significant impact.
2. Preliminaries
We consider the quantized DNNs with binary and ternary weights. The computation bottleneck of the inference pro- cess is a sequence of activation vector to weight matrix multiplications - the primary focus of our work. In this section, we formally build the necessary notations, followed by our problem formulation. To simplify the explanations, we use ternary weights
n²
generalization of the binary weights. As result, all of our algorithms are readily appli- cable to DNNs with either binary or ternary weights.
2.1. Notation
We denote vectors by V and use capital letters to refer to matrices. For example, A E Enx" is matrix of size n X m with elements belonging to a set of permissible values, E. Specifically, if E = {0, 1} (resp. E = {-1.0,1), then A E Faxm is denoted as a binary (resp. ternary) matrix.
In addition to theoretical analysis, we perform rigorous experiments to evaluate the time and memory of our algo- rithms in practice. Confirming our theoretical findings, our experiments demonstrate the superiority of algorithms over the standard 0(n²) multiplications approach. In particu- lar, Our algorithms achieved up to a 29x reduction in inference time and a 6x reduction in memory usage for vector-matrix multiplication. When applied to 1.58-bit LLMs, the inference speedup is up to 5.24x.
Let Σnn denote the set of all bijective permutation functions : {1, nn (1, n). For vector ह, the permuted vector under a is represented as To (T). where each element is repositioned such that To [T] = (i)) moving the element (i) in ū" to position i of the permuted vector. We extend T. to matrices by permuting their rows. When o clear by the context, we may simplify n, to x. Let L denote the of all ordered lists of length n with entries in N, and let LN represent the set of sorted lists with length at most n. We use A]; jl to indicate the j-th column of a matrix A. Similarly, we use Ali, :] to refer to the i-th row the matrix A and A [ j] to indicate an element.
1.1. Paper Organization and Summary of Contribution
We formalize the rector-temarry matrix mul- tiplication problem and demonstrate its reduction to the vector-binary-matte multiplication problem.
Section 2
2.2. Problem Formulation
Section 3 Given the weight matrices of a trained model, we preprocess them and construct indices that enable the development of our efficient algorithms while reducing the memory requirements by a logarithmic factor.
Given a vector T E IR" and ternary matrix A E {-1, 0, 1 1 our objective is to efficiently compute the product (7 A) In this setting, the vector ö serves as the activation output from the previous layer of the neural net- work, and A is the weight matrix (See Figures 7 anddd in
Section We introduce the RSR algorithm with time
complexity of O Tog(n)) (og[og())) for vector-binary-
n
Please refer to Appendix A for a background review. Whiile all our algorithms and definitions are designed for any matrix, simplify our complexity analysis, we assume is a square matrix.
matrix multiplication for by matrices. We further op- timize this algorithm and introduce RSR++ that achieves a faster running time of ( log(n)
n²
2

---

An Efficient Matrix Multiplication Algorithm for Accelerating Inference in Binary and Ternary Neural Networks
Appendix Ap. Note that, while the vector d is provided at in- ference time, weight matrices fixed during the inference time.
Given ternary matrix A W representing the weights between layers of ternary NN, first present it the subtraction of two binary matrices A B() B(2), as de- scribed in Proposition 2.1 Let B be either ( ((2), At high level, during the preprocessing time, we partition the columns of into a set of column blocks, associating each block www-peruutation as its index to identify the longest common segments across the columns. This permutation used later at the inference time for efficient vector-to-matrix multiplication.
Here, we focus on single multiplication instance and aim to accelerate this operation beyond the quadratic time com- plexity the standard vector-matrix multiplication.
Problem 1 Neetoo--Ternar--aatiee
Product). Given input vector T R" and pre-defined ternary matrix A E (-1,0, 0, 1,,,0,11xx0.. jxxn, compute the product E. A.
The space complexity for representing a matrix B is (n²)). Interestingly, as we shall explain Section [3.41 the space complexity of our indices is O log mic factor in the space required for representing B.
2.3. Solution Overview
Initially, use the following proposition to reduce our problem into Vector- Bectr--innryyMatrri product.
reducing logarith-
Proposition 2.1. Any ternary matrix A can be expressed as A = B()) B(2, where B()) and B(2) are the following binary matrices:
3.1. Step 1: Column Blocking
The first step of our preprocessing is Column Blocking - the process of partitioning consecutive columns of the origi- nal binary matrix B to construct set of smaller, compact matrices, each representing distinct block of columns.
O if A[i,j (-1,0),
[1,1]
(1)
A[i =1
Definition 3.1 (k--oolum Block). Let B E T= and 21,2. [T]]. We define B!a] an n x & matrix containing columns (i 1)
A E (0,1), [1 A[i =-1
[1,1-
to through min(i k. n). This construction yields a series of submatrices BA that partition B into [ contiguous column blocks. Each B! is called a k-Collun Block of B
Therefore, we focus on solving the following problem. Product). Given input vector 7 E E. and a pre-defined binary matrix B E {0, 1)mxn, compute the product T. B.
Problem 2 (Vector-Binary-Maree
For example, consider the following binary matrix,
Following Proposition 2.1 any guarantees established for Problem 2 equivalently apply Problem by constant factor. We introduce two algorithms efficiently solves Problem (hence Problem I (1) Redundant Segment
0
1
0
0
0
1
1
0
1 1 0
1
1
0
B
1
0 1
0
1
0
Reduction (RSR) and (2) RSR++.
0
0
1
Figure ! provides an overview of our approach. Our al- gorithms identify and reuse redundant computations, by
0
0
1
0
first preprocessing the weight matrices and constructing es-
The of 2-Column Blocks of B are as follows:
sential data structures utilized during inference time. The preprocessing phase explained in Section Subsequently, in Section
4 we describe the inference time operations, il- lustrating how our algorithms accelerate the multiplication process, reducing the quadratic complexity of the standard vector-matrix
0
I
1
0
0
DUUDOO
O
1
1
vetor-matrii-muuliiiccaaao muutipliicaiin by logarithmic factor.
B
O
.B|21
DI VIUI
B!!
1
3
O
3. Preprocessing: Index Construction
0
O
1
0
In this section, we outline the preprocessing phase of our approach, during which we construct the essential data struc- tures for the matrix in Problem These structures are designed to optimize and accelerate the multiplication pro- cess during the inference time (explained Section 4).
When & is clear by the context, we use B, instead of B3! to denote the i-th block.
*This definition can be extended to any E Rox
3

---

An Efficient Matrix Multiplication Algorithm for Accelerating Inference in Binary and Ternary Neural Networks
Preprocessing
Inference Time
Binary Matrix 17
B1
Bg
00
10
Step Blocking
Permutation
8 14782538
3:2.710
8/
10
11
10
01
11
33
80
1.0
11
10
01
10
611
1
Input Query 34103984
Step Segmented Sum
1321
11g
10
16g
34126226
77024
144
Step 2: Permutation
6. 68123447
94118
Step Block Product
Kon, (Br)
Ten (Bp)
Ten Teg (B²)
Ton, ( (Ba)
4
1257
0.0
0.0
0.0
00
FEEE
Segmentation
011
011
0.1
0.0
01
Concatenate
80
1355
10
Resalt
30
11
01
10
T 1238
11
11
31
30
A
Figure visualization the Redundant Segment Reduction method. The calculation J this example, 2.
3.2. Step 2: Row Permutation
We define Bing as a binary 2 & matrix which has exactly one row for each binary value from 0 to 2 1, and is also Binary Row Ordered. For example,
The next step after column blocking is binary now ordering, where the rows of each column block are sorted according lexicographic order.
Definition 3.2 (Binary Row Order). Let B; E Bank be bi- nary matrix. For each row Br =], let [r 2 be the corre- sponding binary value of concatenating [r; 1J... Br(r, k). For example, if [r
0
0
0
0
0
O
0 0
[1,0, 0, 1, 1], then [r.r; (1011)2. The Binary Row Order of B, denoted as Man," is defined as a permutation on B. such that the rows of Tan, (B:) are sorted based on their corresponding bi- nary value in ascending order. That is, Vr + s n.
[0 Binp
1
1 0 0 1
Bing
BBirss]
[
0
1
1
1
1
1
1
1
B,[r, f22 < B,[s, 1/2, then BB < (s). We call Top, (B:) as the Binary Row Order of B
3.3. Step 3: Segmentation
To further clarify the Binary Row Order, let us consider Example 3.3
Next, we segment each binary row ordered matrix (the sorted column blocks) into groups of rows with the same binary value representation, enabling further matrix compaction.
Example 3.3. Let B; be block with two columns. The permutation function OB, (, 1, 4 provides a Binary Row Order Ta (B.) of the matrix B.
Definition 3.4 (Segmentation List). Given a Binary Row Ordered matrix B of size n x k the function S(B) returns the list the boundary indices, specifying the ranges of rows with the same binary value representations.
0
0
0
0
0
For example, the segmentation on column block B, is defined S(Ton, (B.)). For simplicity. denote this seg- mentation as S S(B,). Specifically, let S(B,)Li) Then, all rows in range (, + 1]), have the binary value representation [: :)2. Note that min(2k, n)) provides an upper bound on the size of S(B.).
0
0
0
B.
Ton; (B))
(2)
0
0
1
The right expression results from 002 < 012 < 112.
Consider the Binary Row Ordered matrix To (B:) shown in Example 3.3 The Segmentation list of this matrix is [1,4, 6] because the first row is the beginning of 00 rows. Then, starts from index 4, and starts at index 6.
'In general, any binary matrix following this lexicographic order is called Binary Row Ordered matrix in this paper. B, (1) is the j-th value in dB. For example, dB

---

An Efficient Matrix Multiplication Algorithm for Accelerating Inference in Binary and Ternary Neural Networks
Row Binary Value Start Index
00
01
10
11
3.4.1. 1. COMPLEXITY ANALYSIS
1
4
6
6
Theorem 3.6. Representing binary or ternary weight ma-
The Full Segmentation of Example 3.3 There is no starting index for row 10, so skip it by using the same start index of next available value. The Full Segmentation list is the second row of the table.
Figure 2:
trix block indices requires a space complexity O and the preprocessing algorithm to generate the block in- dices has a time complexity of (n?))
n
log(n)
4. Inference Time: Vector-to-Matrix Multiplication
Algorithm 1 Preprocess
1: Input: binary matrix B, and a parameter
To simplify our analysis, without loss of generality, let us assume the weight matrices are of size n. Specifically, given a preprocessed x n binary matrix B, we aim to efficiently compute the product T. B when vector ग E I" is provided at inference time (see Figure 8 in Appendix A)
2: Output: permutations B, and segmentations L, S(B))
3: Create k-Column blocks B;
D Blocking
4: for each block B, do
5: OB, + Binary Row Order of B,
Permutation
6: L; f Segments of Tan; (B,)
Segmentation
7: end for
4.1. Segmented Sum Computation
8: Return: {OB, Vij and {T& Vi)
Recall that during the preprocessing time, for each column block B;, we construct a permutation function dB, and full segmentation list L; as its index.
For a Binary Row Ordered matrix of dimensions n x k, we extend this concept to define Full Segmentation as the list of exactly 2* elements, where the jth element of the list indicates the first index of For example, the Full Segmentation of matrix Top; (B,) in Example 3.3 is [1 4, 6, 6]. Since there are rows for 10, the same boundary is assigned for the next value. See Figure for an illustration.
At the inference time, given a vector ö. our objective is to efficiently compute the multiplication of by each column block B₁, using (a Lt).
that has the binary value
Our first step is computing the Segmented Sums over the permuted vector Tan, (T) - i.e., the sum for each interval in the permuted vector that corresponds to groups of similar rows in the binary matrix B,
From now on, we use the same notation S denote the Full Segmentation for Binary Row Ordered matrix.
Definition 4.1 (Segmented Sum). Consider the permutation function σB, and the full segmentation list L, for column block B. Let Tr Way, (iT) be the permutation of the vector J E R". The Segmented Sum of e on L; is defined as a vector SS,, (ūx) of size |Li] where,
Proposition 3.5. For a binary matrix B, E (0, 1jnxk and j < 2h, S(B.)l + I]- S(B represents the number of rows in B, whose binary value corresponds to j. The number of rows for j 2* is + S(B.)L)
Given the Full Segmentation of Binary Row Ordered ma- trix, a compact representation of the matrix can be obtained by retaining only the first indices of each unique row value in the segmentation list. In the following sections, for sim- plicity, we use L, instead of S(B)) to show the Full Seg- mentation of the permuted Column Block B..
1.b++111 [
if
Li]
SSL (U+)bl
(3)
Σk=L,b (z
if j = L,]
For example, for the Full Segmentation defined for Example
3.3 and a given vector J = [3, 2, 4, 5, 9, 1]. we have:
3.4. Preprocessing Algorithm
Putting all three steps together, the preprocessing algorithm described in Algorithm [ The algorithm starts by select- ing a parameter & such that k < In)2(n). Next, it computes the k-Column Blocks of B. Hereafter, blocks as B, rather than B3!4] for i < [+ For each B;, the algorithm proceeds to calculate both the Binary Row Orders B, and the Full Segmentations L,. Figure [ (Pre- processing- the left figure) provides a visual example of the preprocessing steps.
SS(T) = (9, 14,0,
(4)
denote these
Where 9 = 3 + 2 4,14 14 = 5 5 1, and the third element is 0 because there is no 10z in the segmentation.
Computing the Segmented Sums using Equation 3 requires first computing the permuted vector JT Instead, to effi- ciently compute the Segmented Sums in place (without
5

---

An Efficient Matrix Multiplication Algorithm for Accelerating Inference in Binary and Ternary Neural Networks
Algorithm 2 RSR (Inference Time)
Binu M
RSR (Step 2)
1: Input: vector E RR, binary matrix B
0
2: Output: result F" = V. B where F E R"
Inpul Vector i
0
3: for each block B; do
X
28 22 23
4: i7 4 SST,. r2, (T)
T> Step I; Segmented Sum (Eg 5 >> Step 2; Block Product
5:
i t 17. Bin()
1
6: end for
7: F' (2.. .Fre)
Concatenate block results
8: Return:
RSR++ (Step 2)
Sum
7
computing the permuted vector), we use Equation
SS,, (T+))
(5)
1311
28 28/22/23
J-b+tl--
j < Lel
1 18/28
28
SS,,,00; (ū)li)
E (k)
j = Ld
Figure 3: Visualizing Step 2 of RSR++ (Algorithm versus RSR at inference time.
4.2. RSR
We are now ready to describe our algorithm RSR for com- puting B.B at the inference time. Given the input vector o for each column block B,, in Step we use the permutation function B; and the full segmentation list L, compute the Segmented Sum L,,, (7) using Equation
not minimize the run-time of the algorithm.
The optimal value of can be found using Equation
kopt
argmin AE (E(lo
(n + k22*)
(6)
Then, we use Lemma 4.2 to calculate T. Bi. Lemma 4.2. T. B, SS (T) Bin
To find the optimal value of & based on Equation we apply binary search on l in the range [1, log(n) log( (log(n))) In Appendix F.I we run experiments to find the optimal value of k and evaluate the impact of varying it.
Following Lemma 4.2 as the final step in the inference time,
in Step 2 we calculate the product SS (ū) Bingy for each k-Column Block B, Algorithm shows pseudo- code of this algorithm.
4.2.1. COMPLEXITY ANALYSIS
4.3. RSR++
For each column block B,, step takes (n)) since makes pass each element of exactly once. Step computes the product of vector of size 2 with matrix of dimen- sions 2 x k, resulting in time complexity of O(k 2*).
Having presented RSR, we now present our faster algorithm RSR++ that focuses on improving Step of RSR. This step involves computing the product of vector ū of size 24 and the binary matrix Bingy of size 2* k (Line 2 of Algorithm 2 The standard vector-matrix multiplication. in this case, leads to O 2 time. However, the special structure of matrix Bingy allows us to reduce it to O(2*). Algorithm shows the pseudo-code for this multiplication. See Figure for a visualization this approach.
The entire process is applied to zh k-Collun Blocks. Con- sequently, the total query time is 0 (2 (n k 2*)). For any selection of 2² < n, the overall running time can written O
Specifically, setting l: = log( [ng(ns
results in time com-
Let denote the final result of this product, i Bin We build F starting from the k-th element the first one. (i) The k-th element can be calculated by summing up the elements in ū with odd indices. For example, in RSR++ visualization in Figure 3 the sum of odd-index elements (orange cells) in the top row 23. Then, (ii) we calculate a vector J of [ size 2 where we sum each two consecutive elements of i.. Now we can see that the (l: - 1)-th element of F can be calculated by doing the same process as (i), this time, on (see rows and RSR+ visualization Figure 3). We
plexity of O log Toxtns
log(n) (og(())
Theorem 4.3. The RSR algorithm solves Problem with the time complexity of
2
log(n) (ogln)-[gllog(m))
4.2.2. THE OPTIMAL
While we could prove Theorem 4.3 by choosing =
log( ) , this choice might not optimal, i.c., may
6

---

An Efficient Matrix Multiplication Algorithm for Accelerating Inference in Binary and Ternary Neural Networks
continue this process by repeating steps (i) and (ii) build all & elements of F.
5. Experiments
In this section, we evaluate our proposed algorithmss" time and memory performance in real-world scenarios. Our codes are publicly available in this repository, In addi- tion, some of our implementation details for CPU and GPU experiments are provided in Appendix F In the following, first in Section 5.1 we detail the native C++ implemen- tation of both RSR and RSR++ comparing their runtime performance under a fair setting to validate our theoretical guarantees. In Section 5.2 we implement and evaluate the algorithms using Python's NumPy package, providing in- sights into their performance in a more practical and widely used computational environment. Finally, in Sections 5.3 and 5.4 we conduct experiments on real 1.58-bit LLMs. Our extended experiments, including implementations in BitNet.cpp environment and per transformer module analy- sis, are provided in Appendix [F] Specifically, Appendix F.T explores the process of determining the optimal value of kt, identifying the best l: for each input size n. A performance comparison between RSR and RSR++ is provided in Ap- pendix F2 followed by extended run-time analysis of RSR on NumPy in Appendix F.3 A performance evaluation of our algorithm using GPU is also provided in Appendix F.4
4.3.1. 1. COMPLEXITY ANALYSIS
Step (i) is linear in terms of the size of E at each step (see Line 5 of Algorithm 3) As a result, the running time is Σ E ( = O ). Step (ii) also takes linear in size of S. Consequently, the overall time calculating it Bin(s) using this subroutine takes (22)).
We can follow the same process of analyzing RSR, but this time using RSR++ + subroutine for Line of Algorithm 2 Based on the same analysis in Section 4.2.1 the inference time would be O (n + )²)), for a k log(n) n) this would result in the running time of O (og(n)
Theorem 4.4. The RSR++ algorithu solves Problem 7 with a time complexity of 0
log(n)
4.3.2. THE OPTIMAL
The process for finding the optimal value of for RSR++ is the same as the one for RSR, except that the binary search is applied in the range [1, [og])) to optimize the following equation:
5.1. Native Implementation
In this section, we focus on verifying the theoretical foun- dation of our proposed methods, RSR and RSR++, using native implementations in C++, We selected C++ as the im- plementation language because, being a compiled language, it is less susceptible runtime noise, allowing inference time to better reflect the exact time complexity of the meth- ods, relatively. As baselines, we also implemented Standard Matrix Multiplication, which we will refer to as Standard throughout this section.
hopt
argmin " (n + 2
kE [[]oog(n]]
4.4. Generalization
Our algorithms naturally extend to vector multiplication with any bit matrix. Specifically, given a matrix A where each entry is encoded using q bits, we can decompose A into a weighted sum of binary matrices:
For input, we assume access to binary weight matrix Baxn where 2 S n S 2 during preprocessing. During infer- ence time, given input vector o of size n, our aim is to compute v B. with both B and ō values generated ran- domly. These parameters align with typical size of weight matrices and input vector patterns commonly encountered in deep learning and large language model (LLM) infer- ence tasks. We then measure inference time across varying values of for each method. We also utilized the optimal value of for each n, which is discussed in detail in Ap- pendix F.I Figure presents the inference times for these methods. Notably. our proposed algorithms achieve up to a 29x speedup over the Standard baseline when n = 26 representing a substantial improvement that could signifi- cantly impact DNN and LLM architectures, enabling them to utilize binary and ternary weights more effectively.
A
2 BN.
k=
where each Bg is a binary matrix in which the element Bx(t, :] is 1 if and only if the kth bit of A(i, j] is set. We then apply the RSR algorithm separately to each Bg, and combine the resulting products. This extension incurs only a linear overhead in runtime with respect to q.
4.5. Parallelization
Due to the independence of computations across column blocks, our algorithms are naturally parallelizable. We dis- cuss the parallelization of our algorithms on CPU and GPU in Appendix C.1
7

---

An Efficient Matrix Multiplication Algorithm for Accelerating Inference in Binary and Ternary Neural Networks
calculate the final weights. This preprocessing enables substantial compression. Figure illustrates the memory consumption in megabytes for NumPy and RSR. In the peak of preprocessing procedure, both the weight matrix A and the segment data are stored in memory (indicated by the green line); however, after computation, only the segmenta- tion lists and permutations are stored and will be cleared from memory. For matrix of size n 2 the storage required is reduced to less than 17% of the original matrix size (5.99x improvement), highlighting the benefits of this approach for large-scale storage and data transfer.
10a
Standard
RSR
2935x
RSR++
Time (logto scale, and)
106
15.07x
20.64X
10a
14,0x
10f
10.17x
9.33x
10
2
2
2
2
In summary, RSR provides practical advantages for deploy- ing large models. For instance, companies training new L.LMs could preprocess their weights to release only the final segments, permutations, and the optimal parameter k. This would result in up to 24x faster inference times and up to 5.99x memory reduction, significantly easing both storage and transfer demands.
(log> scale)
Figure 4: Comparison of RSR, RSR++ and Standard on native C++ implementation for Binary Matrix Multiplica- tion. The speedup values are between RSR++ and Standard. Each value the average of 10 different runs.
NumPy
5.3. LLM Inference on CPU
Memory Usage (logto scale, MB)
(fioal usage)
5.99%
10a
RSR (peak usage)
To further evaluate the practical performance of our algo- rithms, we examine their application to quantized large language models by replacing the matrix multiplications in the fully connected layers. Specifically, we run experiments using the 1.58-bit quantized versions of Llama3 and Fal- con3 The experiments were conducted on server with the following specifications: 16-core Intel Xeon CPU, an NVIDIA Tesla T4 GPU, 32 GB of RAM, and Debian 11 as the operating system. Our algorithms were implemented using the PyTorch library in Python. The details of the implementation is discussed in the Appendix
5.98x
10
5.96x
4.96x
10a
3.95x
3.90v
10a
2/
2
214
(logg scale)
In this experiment, we perform LLM inference on CPU to assess the speedup gain by our algorithms on a simple setting without parallalization. This setup simulates vironments with limited computational resources, such as personal devices. Subsequently, in the Section 5.4] we shall extend our implementation to GPU, using the parallelization techniques outlined in Section C.T
Figure 5: Memory consumption of RSR after the preprocess- ing is done. Compared to memory required for the Standard matrix multiplication (NumPy). In RSR, we only store per- mutations and segmentation lists the memory.
5.2. Matrix Multiplication Using NumPy
We utilized the 1.58-bit model implemented following the work in (M et al. 2024). Having downloaded the weights of the pre-trained model, we applied the pre-processing step of our algorithm the weight matrices (this step is done only once per model). During the inference time, for each fully connected layer (torch. nn. . Bi t (.Linear) we integrated and executed the inference step of RSR.
In this section, investigate the practical performance improvements achieved by RSR, extending beyond native simulation environments. To this end. we use NumPy, state-of-the-ar library for matrix multiplication upon which numerous high-performance computing libraries are based. implement RSR Python using NumPy's built-in func- tionalities and compare the inference time and memory consumption between RSR and NumPy's np. dot () func- tion (referred to as NumPy). We provide our Inference time evaluation in Appendix an up to 24x faster inference times by our algorithm.
To evaluate the performance, we conducted experiments on three datasets. First, generated synthetic dataset of short factual questions (ShortQuestions) with assistance
F3 where in summary, we observed
"Link to Llama3-8B-115580 Falcon3-3B-1.58hii. and Falcon3.
RSR requires a preprocessing step to compute permutations and segments, where only these two values need to be stored
[0B-1_58hit on Huggingface. hntps///pytorch.orr/
8

---

An Efficient Matrix Multiplication Algorithm for Accelerating Inference in Binary and Ternary Neural Networks
Average Inference Time for Liama3-8e 1-58-bit
Average Inference Time for Falcon3-35 1.58 bit
Average Inference Time for Falcon3 10B 1.58-ar
Standard
Standand
Standard
335.7 (4.92x)
526.4 (4.9Ps)
P5.9
101.4 14.8k
235.6 (4.91x)
326.4 15
Ruering Time (9
Rureing Time
Rurning
65.4
18.5
20.8
176
SPortQussions SimpleQuestion
TREC QA
Shortquestions
SimpleQuestion
TREC QA
Shortqucstions
SimpleOu cstión
TREC QA
Figure 6: Average inference time on CPU for different 1,58-bit models. The x-axis represents the three different datasets.
The other two datasets used were Simple- Questions Diefenbach al., 2017) and TREC QA (Wang et al. 2007). The matrix sizes in the Llama3 model ranged from 2 12 to 2 while for Falcon3 models, they ranged from 2 to 212 For each input, generated single token by running one feedforward pass through the LLM and verified the equality of responses with and without applying RSR.
from GPT-4
Model
Standard (ІS)
RSR (JSS)
Llama3-8B-11 1B--bbb
392 + 20
225 29
Falcon3-3B-1.55
560 +
206 21
Falcon3-10B-1 10B-1.58bit
364 82
210 24
Table I: Average inference time GPU, All values are in microseconds + standard deviation.
The average inference times are presented Figure [ Standard the baseline 1.58-bit model without any change and RSR is algorithm. As shown, the inference time of the LLM improves by up 5.24x. While the stan- dard method benefits from low-level PyTTorch optimizations for single to-oo--t--mtrixx multiplication:"" our algorithm operates solely at the application level without leveraging these optimizations. This introduces additional overhead, which reduces the observed speedup compared to experi- ments focused purely on matrix multiplication. However, the space usage of this implementation remains identical to the baseline, as the size of the segmentation matrix M is the same as the temarry weight matrix (See Appendix C.1 for the definition of segmentation matrix).
6. Conclusion
This paper presented algorithms that significantly improve inference time and memory efficiency for quantized neu- ral networks (like LLMs) with binary and ternary weights. By preprocessing weight matrices to create indices, our approach reduces storage complexity for maintaining the model weights by logarithmic factor. It enhances inference efficiency, achieving a time complexity of O log
Furthermore, our experiment results across various settings demonstrated the practical advantages of our methods, with observed reductions in inference time of up to 29x and memory usage of up 6x, underscoring the potential of our approach make LLMs more accessible and cost-effective.
5.4. LLM Inference on GPU
Using the implementation detailed in Appendix B33 we evaluated the inference time of the models with and with- out the RSR implementation on GPU, and the results are presented in Table [ Notably, we achieved nearly 2.5x speedup, despite our algorithm being implemented at the application level, compared to the optimized matrix multipli- cation of Py Porch. Our experiments naive vector-matrix multiplication on GPU is provided in Appendix F.4
A Acknowledgments
This work was supported part by the National Science Foundation, Grant No. 2348919 and 2107290. The authors would like thank the anonymous reviewers for their time and invaluable feedback.
Impact Statement
See Appendix E.I for more details.
"PyTorch default settings such as caching mechanisms, backend-speciee optimizations (e.g., cuBLAS, cuDNN), and ker- nel fusion, are fully enabled.
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences our work, none which we feel must be specifically highlighted here.
9

---

An Efficient Matrix Multiplication Algorithm for Accelerating Inference in Binary and Ternary Neural Networks
References
large language models. arXiv preprini arXiv21006006685 2021.
A121 Labs. Ai21 studio, 2024. URL https:// WWW
ai21 www.ccoccss...o...... cow/studio studio Accessed: 2024-11-09.
Hubara, I., Courbariaux, M., Soudry, D., El-Yaniv, R., and
Bengio, Y. Binarized neural networks. Advances in neural information processing systems, 29, 2016.
Arlazarov, V. L., Dinitz, Y. A., Kronrod, M., and Faradzhev, I. On economical construction of the transitive closure of oriented graph. In Doklady Akademii Nauk, volume 194, pp. 487-488. Russian Academy of Sciences, 1970.
Hubara, I., Courbariaux, M., Soudry, D., El-ianiv, R., and
Bengio, Y. Quantized neural networks: Training neu- ral networks with low precision weights and activations. Journal of Machine Learning Research, 18(187):1-30. 2018.
Brown, T. B. Language models are few-shot learners. arXiv preprint ar 200:20005.4165 2020.
Chen, M., Shao, W., Xu, P., Wang, J., Gao, P., Zhang, K., Qiao, Y., and Luo, P. Efficientqat: Efficient quantization- aware training for large language models. arXiv preprint 2mXi::240..11022 2024.
Hugging Face. Autotrain by hugging face. Accessed: 2024-11-09, 2023.
co/
autotrain
Liberty, E. and Zucker, S. W. The mailman algorithm: A note on matrix-vector multiplication. Information Pro- cessing Letters, 109(3): 179 2009.
Choi, S., Shim, K., Choi, J., Sung, W., and Shim, B. Terngemm: General matrix multiply library with ternary weights for fast dnn inference. In 2021 IEEE Workshop on Signal Processing Systems (SiPS), pp. 111-116, 2021. doi: 10.1 (099//iPS5292..2221.... 000088.
Ma, S., Wang, H., Ma, L.,, Wang, L., Wang, W., Huang, S., Dong, L., Wang, R., Xue, J., and Wei, F. The era of 1-bit llms: All large language models are 1.58 bits. arXiv preprint arXiv:2402.17766 2024.
Courbariaux, M., Bengio, Y., and David, J.-P. Binarycon- nect: Training deep neural networks with binary weights during propagations. Advances in nearal information processing systems, 28, 2015.
McKinstry, J. L., Esser, S. K., Appuswamy, R., Bablani, D., Arthur, J. V., Yildiz, I. B., and Modha, D. S. Dis- covering low- precision networks close to full-precision networks for efficient embedded inference. arXiv preprint 18Xi::1809.00
Dai, S., Venkatesan, R., Ren, M., Zimmer, B., Dally, W., and Khailany, B. Vs-quant: Per-vector scaled quantization for accurate low-precision neural network inference. Pro- ceedings of Machine Learning and Systems, 2021.
2018
Moons, B., Goetschalckx, K., Van Berckelaer, N., and Ver- helst, M. Minimum energy quantized neural networks. In 2017 51st Asilomar Conference on Signals, Systems, and Computers, pp. 1921-1925. IEEE, 2017.
Das. B. C., Amini, M. H., and Wu, Y. Security and privacy challenges of large language models: A survey, arXiv preprint arXiv:2402. 200800800000888 2024.
OpenAL. Models, 2024. URL
openaii.com com/ httpaaal.coo//cs//////// dwwp//odeloolloo 09.
Accessed: 2024-11-
Diefenbach, D., Tanon, T. P., Singh, K. D., and Maret, P. Question answering benchmarks for wikidata. In Proceedings of the 2017 Posters & Demonstrations and Industry Tracks co-located with 16th International Semantic Web Conference (ISWC 2017), Vienna, Austria, October 23rd 25th, 2017., 2017. URL http:// pdf
Park, H. and Choi, K. Cell division: weight bit-width re- duction technique for convolutional neural network hard- ware accelerators. Proceedings of the 24th Asia and South Pacific Design Automation Conference, pp. 286- 291, 2019.
Ceur ws. org Vol
Finlayson, M., Ren, X., and Swayamdipta, S. Logits of api-protected IIms leak proprietary information. arXiv preprint X4w.:24430005399 2024.
Pearce, H., Tan, B., Ahmad, B., Karri, R., and Dolan-Gavitt B. Examining zero-shot vulnerability repair with large language models. In 2023 IEEE Symposium on Security and Privacy (SP), pp. 2339-2356. IEEE, 2023.
Guo, H., Brandon, W., Cholakov, R., Bagan-Kellew J., Xing, E. P., and Kim, Y. Fast matrix multiplications for lookup table-quantized Ilms. arXiv preprint arXiv:2407.10966, 2024.
Tech W. G. The journey of openai gpt mod- els.
s..pee.....ppmmmmdd.d-227777777 2023. Accessed: 2024-11-03.
Hu, E. J.. Shen, Y. Wallis, P., Allen -Zln, Z., Li, Y., Wang, S., Wang, L., and Chen, W. Lora: Low-rank adaptation of
10

---

An Efficient Matrix Multiplication Algorithm for Accelerating Inference in Binary and Ternary Neural Networks
Trusov, A., Limonova, E.,, Nikolaev, D., and Arlazarov, V. V. Fast matrix multiplication for binary and ternary cnns arm cpu. In 2022 26th International Conference Pattern Recognition (ICPR), pp. 3176-3176111 3182, 2022. doi: 10.1 141109CPR56661 2022.99562...
18th USENIX Symposium Operating Systems Design and Implementation (OSDI 24), pp. 307-323, 2024b.
Wang. M., Smith, N. A., and Mitamura, What is the jeopardy model? quasi-synchronous grammar for qa. In Proceedings of the 2007 joint conference on empirical methods in natural language processing and compula- tional natural language learning (EMNLP-CoNLL), pp. 22-32, 2007.
Tsai, A. Explaining gpt-3 architecture and work- ing. httpps:/mmedium.comm com @ tsaiabhi. cea.iaabii.coollexplaiiiii gpt-
3--rchitecture-ani and working-d0222 (921992922 2020. Ac-
cessed: 2024-11-03.
Wu, J., Leng, C., Wang, Y., Hu, Q., and Cheng, Quantized convolutional neural networks for mobile devices. In Proceedings of the IEEE conference computer vision and pattern recognition, pp.
Wang, H., Ma, S., Dong, L., Huang, S., Wang, H., Ma, L., Yang, F., Wang, R., Wu, Y., and Wei, F. Bitnet: Scaling 1- bit transformers for large language models. arXiv preprint 2rXiv22310.11453 2023.
2016.
Yao, Y., Duan, J., Xu, K., Cai, Y., Sun, Z., and Zhang, A survey on large language model (Ilm) security and pri- vacy: The good, the bad, and the ugly. Cinf-CConf Computing, pp. 100211, 2024.
Wang, J., Zhou, H., Song, T., Mao, S., Ma, S., Wang, H., Xia, Y., and Wei, F. 1-bit ai infra: Part 1.1, fast and lossless bitnet b1. 58 inference on cpus. arXiv preprint 141144 2024a.
Yuan, Z., Zhou, R., Wang, H.. He, L., Ye. Y.. and Sun, Vit-1.58 b: Mobile vision transformers in the 1-bit era. arXiv preprint arXiv:2406. 18051, 2024.
Wang, L., Ma, L., Cao, S., Zhang, Q. Xue, Shi, Y., Zheng, N., Miao, Z., Yang. F., Cao, T., et al. Ladder: Enabling efficient (Low-Precision) deep learning com- puting through hardware-awar aware tensor transformation. In
Zhu, C., Han, S., Mao, H., and Dally, W. Trained ternary quantization. arXiv preprint arXiv:1612.01064 2016.

---

An Efficient Matrix Multiplication Algorithm for Accelerating Inference in Binary and Ternary Neural Networks
APPENDIX
Figure visualizes the bottleneck operation of the inference process: the multiplication of each activation vector a* to the weight matrix W to generate the vector 2*
W
W
F1
W
11.2
Wi.1
72.11
W
Building on this background, our work focuses on accel- erating the bottleneck operation, the vector-ternary-marre product. By improving the speed this operation, we proportionally accelerate the entire inference process of a quantized LLM (or, more generally, neural network), as each matrix product in the feedforward procedure is com- puted sequentially until the output layer. We reformulate this problem as a vector- vector-binary binaryinaatttt matrix multiplication, thereby enabling compatibility with both binary and ternary matri- ces.
W
y/
122
m22.2
:
Una
w
Fmn
722.22
Oütput
Wag.
Input
Layer
1
Layer
2
B. Related Work
Figure 7: A feedforward neural network with é = 3 layers and n; nodes per hidden layer.
In this paper, consider the quantized DNNs with binary and ternary weights (Dai et al. 2021 Wu et al. 2016 instry et al. 2018 Zhu et al. 2016 Courbariaux et al. 2015 Hubara et al. 2016).
McK
Examples of ternary DNNs include (Moons et al. 2017]
Hubara al. 2018 Yuan al.] (024) and 1.58-bit
W.2
W
W
1,3
W
L.MSs (Ma al. 2024). where the weights are limited to 11)
W
W
W
Previous research has explored enhancing matrix multiplica- tion through hardware-level accelerations (Guo et al. 2024
W
W
W3,3
Wa
Wang et al. 2024b; Park & Choi 2019; Trusov et al., 2022 Choi et al. 2021). contrast, our approach focuses on de- signing algorithm that provides guaranteed logarithmic improvement over naive matrix multiplication at the appli- cation layer, independent of specific hardware architectures.
W n.
W
W
Wik n...
The Four Russians Algorithm (Arlazarov et al. 1970) is a classical method for efficient Boolean matrix multiplica- tion. While the Four Russians Algorithm relies on tiling the matrix and computing the smaller products, our approach focuses on matrix column-blocks and extends both binary and ternary matrices. Additionally, their method is designed for matrix ma-rix-to-matrix multiplication, whereas our method is for vector-to-matrix operations where the vector is random R" vector.
Figure 8: Illustration of vector-to-man -ma-rix multiplication the core inference operation.
A. Background
A trained DNN model consists of collection of weights used for inference (Figure 7 The weights are learned during the training phase and are fixed during the inference time. During the inference time, given an input vector, the feedforward process can be viewed as a series of matrix multiplications applied to the input vector to produce the final output. For instance, consider the two consecutive layers shown in multi-layer perceptron in Figure 7 Each weight matrix W represents the edge weights between layers (i - 1) and i with layer 0 being the input vector. The feedforward step is a chain of matrix products and activation functions that maps input vector H to output vector ÿi it can be represented as follows (with 70 7), where / is the activation function (e.g., sigmoid or ReLU).
A related algorithm is the Mailman algorithm (Liberty Zucker 2009), which also reduces matrix-vector multipli- cation time by a logarithmic factor through preprocessing. However, its preprocessing differs from ours: the Mailman algorithm constructs matrix P by considering all possible binary-valued columns and expresses A = x P. enabling fast multiplication. In contrast, our approach constructs list of permutations and segment sums, allowing us to achieve an Olog n log log n) speedup even when multi- plying vector by the matrix P. Additionally, as discussed
* -
at f(*))
12

---

An Efficient Matrix Multiplication Algorithm for Accelerating Inference in Binary and Ternary Neural Networks
in Section we design segment matrix structurally
we know that the /th element of 7 is the /th segment sum of Top, (7). This segment is the sum of some consecutive elements of Te s, (7)) Based on Definition 3.2 this permuta- tion is designed such that similar rows of B; are positioned together. This means that all the elements of T that are in this segment (we denote this segment as St, in other words, St is the indices of U that lie in this segment) are multiplied to the same binary value in B Call this value as by. As a result, we can factor by out for each segment of T the dot product. We can rewrite the dot product as:
similar P and leverage it in parallel settings.
C. Proofs
Theorem 3.6, Representing a binary or ternary weight ma- trix as block indices requires a space complexity O and the preprocessing algorithm to generate the block in- dices has a time complexity of O(n²).
n²
[og(())
Proof. For Binary DNNs, let B = W be binary weight matrix. For Ternary DNNs, let a weight matrix A = W be expressed as A = B()) - ( using Proposition 2.1 Then represent A using the block indices of B(1) and B
(8. B.B.B) =
fqg] B
(8)
9=1
produced by Algorithm Let B3 be either (1)) or B(2)
2
2
Time Complexity:
During the preprocessing, we read all elements of the input matrix B, which requires O(²²) time. Blocking the matrix into k-Column Blocks has a time com- plexity linear to the number of blocks while determining the permutation corresponds to performing& a bucket sort on the rows to achieve the lexicographic ordering, which requires Onn). Consequently, the total preprocessing time is Onn)). Given that the input matrix size is O(n²). this complexity is asymptotically optimal, as any algorithm requires reading the matrix B in (n²))
J(e))
by
Σ
a by
1=1
cES
Where in the last line we used the fact that VI, a[[[]
Eess, [[]].
Each by is the single that in column j of B; corresponds to the segment St. Based on Definition 3.2 the applied per- mutation tries to sort all columns based the lexicographic order of rows. So, this means that Binna [1,5] = by and as a result,
The output of the preprocessing phase is a permutation and a segmentation list as each block in- dex. Recall that L |S(B.)] = 2*, where S logz (n). Therefore, storing each block index requires (nn) space. The total number of column blocks is f. Hence, the to- tal space complexity of the preprocessing output is (44)). Particularly, when &- = log(n), the space complexity is (oggin)) ). As explained in Section 4 the inference algo- rithms only require access to the block indices. Therefore, replacing the weight matrices with the block indices, we reduce the space complexity by a logarithmic factor. L
Space Complexity:
2
2²
Σ 1=1
c| by = Σ Jt Bingal4.1 [=1
(9)
= (it [ing(t.5])
(10)
n²
As a result, for all columns j. the dot products are equal (ø B, = (it II:.)) Consequently, the vector- matrix products are also equal.
C.1. Parallelization
In this section, we discuss two approaches for parallelizing our algorithms to handle high-performance workloads.
Lemma 4.2, T- B.B BB= = SS -Bing)-
Proof. Define ū = S5 (7). At first, we should show that |a]] = 2², and as a result, the product on the right- hand side is valid. We know that |SSt.. (T) = L, (see Definition 4. In addition, based on Definition 3.4 we know that in the Segmentation list, there is exactly one element for each possible binary value between 1 to 2*. So |L,| [S [B.) = 2*
I. Parallelization based on block independence: Our RSR and RSR++ algorithms conduct each block computa- tion in isolation, independent of the other block computa- tions. Consequently, the block productions can be executed concurrentyy during the inference time. As a result, utilizing e computation cores, the time complexities are further re- duced by a c factor, reducing the time complexities of RSR n
2*
n² and RSR++ O (oggigtn)) and O clgg(n) respectively. Additionally, further parallelization can be achieved by applying block production simultancously on different columns of the binary-encoded matrix Bin(x)-
Now, let us focus on single column of B, (jth column). We show that (7- 51) = {ū Bin l: jT), where () is the dot product of two vectors. Based on the Definition 4.1
13

---

An Efficient Matrix Multiplication Algorithm for Accelerating Inference in Binary and Ternary Neural Networks
Algorithm 3 + (Step 2 in Inference Time)
sonal computers, with limited memory and processing power.
1: Input: vector ū IR." and matrix Bin(M]
By processing one column block at a time, the algo- rithm only requires memory equivalent to the size of a single block, which is significantly less than that needed for full matrix multiplication.
2: Output: result F" = i7- BimM
3: Initialize I <- T
4: for from k to do
5: is - sum of odd indexed elements of
Last but not least, our method is deployable on top of any of the current or future binary or temary models, without requiring any fine-tuning
6: Initialize to a vector of size [n 2
7: for j from 1 to 2
E do
re-training of the LLM or DNN. Once model is trained, our preprocess- ing step can be applied once, allowing the preprocessed model to be utilized at any future point.
8: お 4 ø - -1 21]
9: end for
10: end for
II. Parallelization on GPU: Our second approach is based on the GPU implementation of our RSR algorithm discussed in Section 5.4 and Appendix E.3] and involves converting the segmentation and permutation steps during inference into single 3D tensor multiplication. For each column-block j, we define segmentation matrix Mj of size n x 2*, where each column is one-hot vector of size n indicating which element of the input vector belongs to that segment (with a total of 2 segments; see Section 4.1). Multiplying by this matrix produces the vector ıī (see Algorithm
D.2. Limitations
PyTorch's hardware-level optimizations on GPUs make single vector-to-matie multiplication extremely fast and efficient. The current implementation of our methods is at the application level and does not lever- age hardware-specific instructions, which limits the speedup achieved when applied to real LLMs.
Our approach demonstrates significant speedups when working with Python packages for matrices larger than 20 in size. For smaller matrices, hidden constants and implementation overheads tend to dominate, reducing the practical benefits despite the theoretical guaran- tees. However, in real-world models, matrix sizes are typically much larger than this threshold, as discussed earlier.
2 and Figure [). The result is then multiplied by Bi By stacking all M, matrices across all j, we construct a 3D tensor M. Precomputing M x Bin al- lows us to reduce the inference process to a single tensor multiplication, significantly enhancing parallelization.
Future work could explore leveraging specific hardware instructions, such as blocking, permutations, segmentations, and block productions, further optimize these steps at the hardware level in parallel.
E. Experiments Details
E.1. Synthetic Dataset
We built a synthetic dataset containing set of short factual questions (ShortQuestions). In order to build this dataset, we used GPT-4 to give us a list of questions. For example, one sampled question from this dataset looks like: "What is the capital of France?", and the responses of both St Standard and RSR models were "Paris". This because we limited each model to generate only one token through single feedforward pass.
D. Discussion
In this section, we discuss some of the advantages and lim- itations of our proposed algorithms and outline potential directions for future research in this area.
D.I. Advantages
Our RSR++ algorithm shows up 29x improvement in inference time and 6x reduction in memory usage, as observed in our experiments. Note that following our complexity analyses, these numbers get even larger by the size the network layers. This significant improvement indicates that the algorithm can support larger hidden layers and matrices to enhance model ac- curacy while requiring fewer computational resources.
E.2. Py Porch Implementation Details: CPU Experiments
To further optimize Algorithm 2. for each column-block j. we constructed a segmentation matrix M, of size n x 2 Each column of Mj is a one-hot vector of size n, representing the indices of elements in ő that belong to the corresponding segment before the permutation, with 2 segments in total (see Figure []. The inference process is then reduced to a matrix multiplication i x N, followed by reshaping the output, where N = M x Bingy and M is a
The efficiency of our algorithm leads to reduced en- ergy consumption, further contributing to the model's practicality and sustainability.
Our approach enables the deployment of more ad- vanced models on ordinary devices, such as per-
14

---

An Efficient Matrix Multiplication Algorithm for Accelerating Inference in Binary and Ternary Neural Networks
3D tensor containing all matrices M, corresponding to the z blocks. This approach takes advantage of the low-level optimizations already integrated into PyTorch. However, the baseline we compare against benefits from additional PyTorch-specific optimizations beyond this implementation.
An evaluation of single vector-matrix multiplication GPU based this implementations is provided in Ap- pendix F.4
F. Extended Experiment Results
The forward () function (BitLinear) uses single matrrxx multiplication in PyTorch:
baseline model
F.1. Parameter k Optimization
As outlined in Section 4.2.2 the optimal value of for RSR (reps. RSR++) determined through binary search over the interval [0, log( log(n))) (resp. [0, log(n))) Once the optimal identified for each 7,, is then applied in the subsequent experiments. Figures 9a and 9b show the running time with respect different k values. By increasing the optimum value of k also increases.
def forward (sclf, input):
= input self.ternary_matiix return y
Listing I: Simplified forward function in baseline
However, in the changed code, this function looks like this;
celf.rste prer_matrix <= segmentation matrix def forward (self, input):
F.2. RSR vs. RSR++ Native Implementation
y (imput self. rsr matrix) permute (1, 0, . reshape (input. size (1), -1)
In Section 5.1 we observed the performance gain of RSR and RSR+ in comparison with the standard vector-matris multiplication across different input sizes (n). In this section, we focus on the performance gain of RSR++ versus RSR across different settings. To do so, we use our native C++ implementation discussed in Section 5.1
return
Listing 2: Simplified RSR implementation
Figure Iiillustrates the difference between only RSR++ and RSR for in the inference time. In this figure, we 25% improvement when using RSR++ in the Step 2 of infer- ence time (See Algorithm 3 The improvement percentage is computed using the formula T(RR)) - (RSR++++ 100. T(R3R)
up
E.3. PyTorch Implementation Details: GPU Experiments
To optimize the runtime of the previously discussed CPU implementation on the GPU, we parallelized the vector- matrix multiplication. Using the segmentation matrix M, multiplication was parallelized along its second dimen- sion, corresponding k (see Section 4.2.2). To achieve this, first expanded the input vector to size le times larger:
Algorithm
-5.0%
-9.3%
Time scale, ms)
10a
input_expanded input. unsqueeze (1). expand (-1, k, -1)
-17
Listing 3: RSR implementation on GPU (step 1)
10a
77.7%
Then, single multiplication of i input expanded and the matrix and finally reshaped the result:
10a
expanded_resull
forch.bmm/ input_expanded, seg_matrix) (atttrixixxxuuueeee squeeze (1)
232
2
223
2.4
2
2
f
result torch. stack [[expanded i.:]
for j in range (k) dim=2) reshape v.size(0), -1) unsqueeze (0)
Figure 10: The comparison of RSR and RSR++. The per- centage shows how much improvement we get using RSR++ relative RSR. This a native C++ implementation.
Listing 4: RSR implementation on GPU (step 2)
This approach enables the computation of the product in parallel on the GPU. However, it does not utilize low-level optimized parallelization on the GPU, highlighting the need for future work on hardware-level optimizations for segmen- tation and permutation operations.
F.3. Matrix Multiplication Using NumPy: Inference Time
In this section, present the running time improvements achieved by RSR, on our implementation of RSR in Python
15

---

An Efficient Matrix Multiplication Algorithm for Accelerating Inference in Binary and Ternary Neural Networks
10"
n
0
24
-0
2
2 2
2
-0 2
2
10a
-0-
n 2
-0-
-
2
- 2
-
2
Time (logio scalo, ma)
Time (log1a scale, ms)
104
10a
10a
10a
10a
2.
10
k
(a) RSR
(b) RSR++
Figure 9: Finding the optimum for each The red dots show the best for each that results in the best running time. Once calculating the optimum & values, we use them for other experiments.
NumPy
NumPy RSB
RSR
1784x
96x
Time (logto scale, ms)
24.01x
Time (logia scale, ma)
12.76x
17.19x
7.42x
10a
10.38x
4.15x
1.38x
10a
2.68x
-600
0.77x
23
212
2
2:4
2
2
2
212
2
2
2
2
n (log, scale)
(logz scale)
(a) Binary
(b) Ternary
Figure 11: Comparison of Time required to perform a vector to weight Matrix multiplication for 11a Binary and (1lb) Ternary weights between NumPy and RSR. Each data point an average different runs.
using NumPy's built-in functionalities, discussed in Sec- tion 5.2
speedup over the NumPy baseline on binary matrices of size 2 illustrating that our algorithm only meets theoretical guarantees but also outperforms state-of-the-and practical methods.
As in previous sections, let X"*n denote weight matrix and i the input vector, where our goal is to compute क. A. We run the experiments on both Binary and Ternary matrices. This matrix available prior to inference time, so we can run preprocessing on that. For the parameter k. we use the previously determined optimal values in Section F.
E4. Performance evaluation GPU
Using GPU implementation in Appendix E.3 evalu- ated the performance of single vector-matrix multiplica- tion GPU. The results are provided in Figure 12 Here, we utilized matrices of size 211 to 214 and we can see up to 2x speedup. However, as long as the (size of matrix) increases, the overhead of application-leys
We initialize n at 21l and double its size in each experiment up to 25, Each multiplication is executed four times, with results averaged to mitigate noise. Figures TTa and [Tb present results for matrix multiplication using both the naive NumPy method and RSR for Binary and Ternary weight matrices, respectively. As shown, RSR achieves up to a 24x
optimization reducing the speedup compared the optimized Py Porch standard implementation of vector-matrix product.
16

---

An Efficient Matrix Multiplication Algorithm for Accelerating Inference in Binary and Ternary Neural Networks
RSR Bitiet Inforence Timee
F.5. BitNet.cpp Comparison
FSR: 1ins
[irten Time
In this section, we present additional experiment compare ternary vector-matrix multiplication method with the optimized CPU implementation provided in BitNet.cpp (Wang et al. 2024a). The BitNet.cpp focuses primarily on optimizing the packing and unpacking of ternary weights, For instance, uses the I2g kernel (Wang ctt al. 2024a 2023), where every four 2-bit teraayy values are packed into single uint8 value (Wang al. 2024a). In- ference is then performed directly these packed weights without unpacking, using an efficient custom kernel. We compare the performance of our matrix multiplication algo- rithm against this kernel across various matrix sizes. The results are shown in Figure 13
2394
1.8% 1607x
Figure 13: Time comparing RSR and original BitNet.cpp implementation.
Per-Module
Speedhp (Stansterd) (05R)
Despite not implementing hardware-specifie or low-level kemell optimizations in our implementation (RSR), we still observe significant speedup in ternary matrix multiplica- tion performance. We consider optimizing and utilizing kernel and hardware-speciffc instructions for RSR in fu- ture work, and we mainly focused on the algorithmic and application-level description this work.
Speedup
pet
F.6. Per Module Speedup
Figure 14: Per module speedup comparison of Standard and RSR augmented I.l ama3 9B-18 1...-...0 58 model.
In this section, we analyze the speedup obtained for each individual Porch module L. allama.. a1lama3-822 3--8-11555 .58. Fig- ure [4llltsttste the speedup achieved by our method across different modules. The corresponding module names along with their roles in the Transformer architecture summa- rized in Table 2
(Torch)
L33xx
Time (logra scale, ms)
A2x
2.52y
2.87x
2
212
(loga scale)
Figure 12: Comparison of time required to perform the vector-ternary-matty multiplication on GPU.
17

---

An Efficient Matrix Multiplication Algorithm for Accelerating Inference in Binary and Ternary Neural Networks
Module Name
Transformer Component
embed.tokens
Input Embedding Layer
rotary emb
Rotary Positional Embedding (RoPE)
input.layernorm
LayerNorm before Attention
q-proj
Query Projection (Attention)
k.proj
Key Projection (Attention)
v.proj
Value Projection (Attention)
o.proj
Output Projection (Attention)
post.attentionn.aayamomm
LayerNorm before MLP
gate proj
Gated Linear Unit (GLU) Projection (MLP)
act_fn
Activation Function (MLP)
up-proj
Upward Projection (MLP)
down.proj
Downward Projection (MLP)
norm
Final LayenNorm (Post Decoder Blocks)
Im.head
Output Linear Projection to Vocabulary
Table 2: Module names and their corresponding roles in the Transformer architecture.
18


Reviews:
[{"review_id": "w7WNzUpKAT", "reviewer": "Reviewer_HdLU", "summary": "The paper introduces two algorithms, RSR and RSR++, designed for accelerating matrix multiplication in binary/ternary LLMs during inference. By preprocessing weight matrices into column blocks, permuting rows lexicographically, and computing segmented sums to create optimized indices, the proposed methods reduce time complexity and memory usage by a logarithmic factor. Experiments have been conducted on both cpus and gpus, and demonstrate up to 29x faster inference, 6x memory reduction, and 5.24x speedup in 1.58-bit LLM inference.\n\n## update after rebuttal\nI thank the authors for the thorough rebuttal. My concerns regarding the implementation have been largely addressed (e.g., comparison with BitNet.cpp). However, I still do not understand why the authors only evaluated their method on the curated ShortQuestions dataset instead of providing results using a more commonly used evaluation dataset for the rebuttal. Therefore, I maintain my original rating of weak accept.", "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": "**Methods And Evaluation Criteria:**\n\nThank you for the helpful suggestion. We agree that performance evaluation in other settings—such as generating full sequences rather than single tokens—would also provide valuable insights. We will include additional experiments in the updated version to show the performance and speedup in individual components of the LLM (such as KV Cache, attention, etc).\n\nRegarding implementation, we currently replace all **nn.Linear** modules with our proposed RSR-based implementation. This module is the building block of any Fully Connected component in an LLM model, which contains all the vector-matrix multiplications applied during inference. We will clarify this detail in the updated Supplemental Material.\n\nAs a result, all the components, such as KV cache computations and attention mechanisms, are already running under the new algorithm in the reported statistics. As suggested, in the updated version, we will profile these components **individually** and report performance metrics and speedups for each (rather than just the end-to-end performance comparison).\n\n**Questions For Authors:**\n\n*How is the baseline 1.58-bit model implemented...*\n\nThat's a good question. For the baseline 1.58-bit model inference on CPU (Figure 6), we followed the standard implementation provided in [2], as well as the [official blog post](https://huggingface.co/blog/1_58_llm_extreme_quantization) by the authors of [2]. Specifically, we used the same inference process described in those sources. To ensure the model runs on the CPU, we explicitly configured PyTorch to use the CPU backend by disabling the CUDA environment. For the GPU experiments (Figure 12), we allowed PyTorch to utilize CUDA as expected. We will clarify these implementation details in the updated version.\n\n*Additional experiment on BitNet.cpp implementation...*\n\nThank you for pointing this out. We have conducted an *additional* experiment to compare our ternary vector-matrix multiplication method with the optimized CPU implementation provided in [bitnet.cpp](https://github.com/microsoft/BitNet). The bitnet.cpp implementation focuses primarily on optimizing the **packing and unpacking** of ternary weights. For instance, it uses the I2_S kernel [1], where every four 2-bit ternary values are packed into a single uint8 value [1]. Inference is then performed directly on these packed weights without unpacking, using an efficient custom kernel.\n\nWe have compared the performance of our matrix multiplication algorithm against this kernel across various matrix sizes. The results are shown in the following plot:\n[https://anonymous.4open.science/r/RSR-1566/bitnetcpp/figures/inference_time_plot.png](https://anonymous.4open.science/r/RSR-1566/bitnetcpp/figures/inference_time_plot.png)\n\nThese results are also documented in our updated anonymous repository:\n[https://anonymous.4open.science/r/RSR-1566/bitnetcpp/README.md](https://anonymous.4open.science/r/RSR-1566/bitnetcpp/README.md)\n\nDespite not implementing hardware-specific or low-level kernel optimizations in our implementation (RSR), we still observe a significant speedup in ternary matrix multiplication performance. We consider optimizing and utilizing kernel and hardware-specific instructions for RSR in the future work and we mainly focused on the algorithmic and application-level description in this work.\n\nRegarding the standard PyTorch-based implementation described in the original paper ([2]), we clarify that this implementation uses packed ternary weights for storage. However, during inference, the packed uint8 values are unpacked and converted into bfloat16, and the multiplication is performed in the unpacked domain. This applies to the experiments shown in Figures 11 and 12.\n\nWe will include this clarification and the bitnet.cpp comparison in the updated manuscript. Thank you again for your valuable suggestion.\n\n*References:*\n\n* [1] Wang, Jinheng, et al. \"1-bit AI Infra: Part 1.1, Fast and Lossless BitNet b1. 58 Inference on CPUs.\" arXiv preprint arXiv:2410.16144 (2024).\n\n* [2] Ma, Shuming, et al. \"The era of 1-bit llms: All large language models are in 1.58 bits.\" arXiv preprint arXiv:2402.17764 1 (2024).", "claims_and_evidence": "Yes, most claims made in the submission are supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "Most of them are standard that make sense. However, I am wondering why the authors only considered comparing the cases of limiting\neach model to generate only one token through a single feedforward pass and even created the ShortQuestions synthetic dataset for this purpose. The authors should also perform experiments that generate multiple tokens to present the impacts of the proposed algorithms during the auto-regressive generation stage of LLMs that include the usage of KV cache, which also has vector-matrix multiplication workloads. This stage is actually the main bottleneck in LLM inference. Moreover, for the case of only generating one token (which I assume it refers to the prefilling stage), the latency will only be a bottleneck in real-world applications when the context is very long, which is more similar to matrix-matrix multiplication instead of vector-matrix multiplication. The authors should explain their experimental designs in detail, performing the suggested additional experiments or providing a convincing explanation on why they are not performed.", "theoretical_claims": "I went over the theoretical claims and did not find noticeable issues.", "experimental_designs_or_analyses": "Yes. See \"Methods And Evaluation Criteria\" for issues.", "relation_to_broader_scientific_literature": "The work addresses a critical challenge (LLM inference efficiency) with a theoretically sound and empirically validated solution, which has high potential impact for deploying quantized LLMs on resource-constrained devices.", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "- The preprocessing and segmented sum approach effectively exploits the fixed structure of quantized weights. The logarithmic-factor improvements over naive multiplication are impressive.\n- A detailed theoretical complexity analysis, supported by proofs, supports the claimed efficiency gains.", "other_comments_or_suggestions": "Please provide breakdowns of latency comparison for different LLM components, including attentions, FFNs, and others.", "questions_for_authors": "How is the baseline 1.58-bit model implemented for LLM inference on CPU (Figure 6 results)? Please provide more details on the baseline CPU implementation. Specifically, the official implementation, bitnet.cpp (https://github.com/microsoft/BitNet), has already applied some optimizations for CPU inference. Is bitnet.cpp already applied in the \"torch\" implementation described in the paper? If not, please provide additional experimental results that compare with the bitnet.ccp baseline as well.", "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": "gO2CqB2MKS", "reviewer": "Reviewer_APww", "summary": "This work proposes an efficient algorithm for binary/ternary matrix multiplication, where the binary/ternary weights are known ahead of time. The algorithm first transforms the ternary matrix into a sum of binary matrices, and then compresses the binary matrices into a set of aggregate values which contribute to an entry in the result vector. This is done by segmenting the matrix into blocks, ordering the rows lexically, and storing counts for the number of occurrences of binary values across different rows. They also design an efficient multiplication algorithm that leverages this compressed format, which can achieve O(n^2/log(n)) runtime with respect to the matrix dimensions. This leads to practical speedups of >5x for matrix-vector multiplication.\n\n## Update after rebuttal\n\nThe authors addressed my concerns, and I am inclined to keep my score (accept).", "questions": "", "limitations": "", "rating": 4, "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": "**Weaknesses:**\n\n*While the GPU implementation attains speedups...*\n\nThank you for the insightful suggestion—this is indeed a valid point. In this work, our primary focus was on the algorithmic design and application-level evaluation of the RSR algorithm. We compared its performance across various settings using existing, standard matrix multiplication implementations in C++, NumPy, and PyTorch.\n\nFollowing Reviewer #1’s recommendation (Reviewer HdLU), we also included a kernel-level comparison between RSR and bitnet.cpp, which is specifically optimized for ternary matrix multiplication at this lower level [1]. Even in this setting, RSR demonstrates a notable speedup, highlighting its potential for further performance gains.\n\nThe code for this new experiment is available in the updated anonymous repository, which contains a low-level implementation of RSR as a PoC ([https://anonymous.4open.science/r/RSR-1566/bitnetcpp/README.md](https://anonymous.4open.science/r/RSR-1566/bitnetcpp/README.md)).\n\nThis observation suggests that RSR could benefit from additional system-level enhancements. As part of future work, we can explore low-level system optimizations, including custom kernel implementations and hardware-specific instructions tailored to RSR’s structure.\n\n**Questions For Authors:**\n\n*In Section 5.3, the performance was evaluated using 3 datasets...*\n\nYou are absolutely right—the performance should match the standard setting exactly, as our proposed matrix multiplication algorithm is an exact method for computing the product. The inclusion of multiple datasets is intended to show the generalizability of our approach across different scenarios and model architectures. It also emphasizes that the implementation is independent of the specific dataset, with only minor variations in speedup due to noise across different implementations.\n\n*The proposed algorithm requires the full matrix to be compressed together...*\n\nThank you for highlighting this important point. We agree that parallelism plays a key role in standard neural network implementations. In our work, we addressed this in Section C.1 of the Appendix, where we discuss how our algorithm supports parallelization.\n\nTo clarify, we assume full access to the weight matrices during the **preprocessing phase.** In this phase, we transform the original matrix $M$ into a new form by constructing a segmentation matrix $\\mathcal{M}$, then, in the inference, we just calculate the multiplication of vector to $\\mathcal{M}$. Any system-level parallelism (as discussed in Section C.1), is still applicable to the multiplication of the vector to the new tensor, similar to the standard multiplication. This transformation is for the case when we want to leverage from underlying parallelism. Otherwise, our standard inference procedure—as described in Algorithm 2—uses permutations and segmentation lists, which is not necessarily compatible with underlying parallelism (if any).\n\nIf there is existing parallelism in the underlying libraries (e.g., row- or column-wise parallelism applied during inference), our approach remains compatible. Since $\\mathcal{M}$ retains the same size as $M$, just with a different shape, the existing parallelism mechanisms can still be applied effectively. We can observe this fact in Figure 12 and Table 1, where the GPU parallelization exists, and we still have a notable speedup.\n\nThe transformation (from $M$ to $\\mathcal{M}$) happens once during preprocessing, when the full matrix is assumed to be available, while parallelism is typically applied at inference time, distributing matrix tiles across available GPU cores. Our method does not interfere with this process and remains fully compatible with standard parallel inference execution.\n\nIf there is a parallelism strategy applied in the preprocessing time (when storing and preprocessing the weights, i.e. not in the inference time), then our approach should be applied in any individual blocks (either row or column blocks, depending on the parallelism). Then, in the inference time, any individual block multiplication can be translated to RSR multiplication.\n\n*References:*\n\n* [1] Wang, Jinheng, et al. \"1-bit AI Infra: Part 1.1, Fast and Lossless BitNet b1. 58 Inference on CPUs.\" arXiv preprint arXiv:2410.16144 (2024).", "claims_and_evidence": "Yes - the measured runtime for the method clearly demonstrate the practical speedups which are attainable through their approach.", "methods_and_evaluation_criteria": "Yes - the included benchmarking is reasonable for both end-to-end latency and matrix-vector latency measurements (included for both GPU and CPU). For example, they included both native C++ benchmarking and numpy benchmarking (showing that they compare with high-performance kernels), as well as GPU-level benchmarking (at the application level, without custom kernel implementations).", "theoretical_claims": "I went through the outlined methodology and algorithms and did not identify any issues.", "experimental_designs_or_analyses": "The CPU benchmarking setup and GPU benchmarking setup both seem reasonable.", "relation_to_broader_scientific_literature": "The paper presents a fast algorithm for matrix-vector multiplication with binary/ternary weights. For the majority of binary/ternary quantization works, the weights are the matrix compressed in binary/ternary, and this would be available ahead of time, making this algorithm applicable. This work can therefore be used as a drop-in approach to accelerate inference with these techniques.", "essential_references_not_discussed": "I am not aware of any missing essential references.", "other_strengths_and_weaknesses": "Strengths:\n- The proposed algorithm attains complexity improvements relative to prior multiplication algorithms for binary/ternary weights.\n- The algorithm is fully parallelizable and can therefore be mapped to both CPU and GPU implementations.\n- The paper explains their method both through algorithms as well as clear visualizations.\n\nWeaknesses:\n- While the GPU implementation attains speedups while implemented only at the application level, a kernel-level implementation would be necessary for harnessing greater speedups from the algorithm.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "- In Section 5.3, the performance was evaluated using 3 datasets. However, unless I am missing something, the accuracy should be identical with and without this algorithm (aside from minor numerical differences). Is there a reason for evaluating using all 3 datasets?\n- The proposed algorithm requires the full matrix to be compressed together - is it therefore more challenging to employ particular tensor parallelism strategies which split along the column dimension (i.e. which allocate different rows to different GPUs)?", "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": "iOZlGIri1s", "reviewer": "Reviewer_xCtm", "summary": "This paper describes and complexity-analyzes an efficient algorithm (RSR/RSR++) for multiplication with binary (and by derivation, ternary) matrices. CPU and GPU implementations are provided, and inference with ternary-weight LLMs is demonstrated.", "questions": "", "limitations": "", "rating": 4, "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": "Thank you for your time and the careful review of our work. We appreciate it.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "I can follow the general logic but might not have spotted minor mistakes.", "experimental_designs_or_analyses": "Yes, they are fine.", "relation_to_broader_scientific_literature": "Though there exist efficient binary matrix multiplication algorithms, this study presents thorough complexity analysis and practical implementations, as well as real-world ternary LLM inference experiments.", "essential_references_not_discussed": "I believe the relevant prior studies on efficient binary matrix multiplication are discussed.", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "N/A", "questions_for_authors": "N/A", "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": "H6N4J49qWc", "reviewer": "Reviewer_czCs", "summary": "The paper proposes an efficient matrix multiplication algorithm for cases where one of the operands is binary or ternary. The binary weight matrices are partitioned into multiple blocks to exploit their intrinsic low-dimensional structure, leading to reduced storage and computation during inference. Within each partition, the rows are sorted lexicographically to form segments, enabling the storage of both the permutation and the segment row indices in the compressed binary matrix representation. During inference, the input is permuted and summed over each segment, with the exact output obtained by multiplying the binary matrix $Bin_{[k]}$. The proposed method achieves a memory and computation reduction of $\\log n$. Compared to standard binary matrix multiplication, the algorithm delivers a 4-5x improvement in CPU latency for LLM inference.", "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": "**Theoretical Claims:**\n\nThanks for bringing this to our attention. We explicitly include all the proofs in the updated version. The proof of Theorem 4.4 was removed due to its similarity to Theorem 4.3 (with a different value of $k$).\n\n**Weaknesses:**\n\n*RSR and RSR++ involve permutation of the input data...*\n\nThank you for raising this important concern regarding the memory overhead introduced by permutations. We would like to clarify that after applying RSR during the preprocessing phase, the inference stage does not require storing the full-weight matrix. Instead, we store only the segmentation and permutation information. This design leads to a logarithmic ($log n$) reduction in memory usage during inference, as illustrated in Figure 5. (for the parallel approach we store a new matrix $\\mathcal{M}$ as mentioned in the answer to Reviewer #2).\n\nMoreover, in an optimized implementation, we avoid explicitly permuting the input vector. Rather than generating a permuted copy, we perform **index-based lookups** to access the necessary vector elements on the fly. This avoids both memory overhead and unnecessary data movement.\n\nAs described in Section 4.1 (immediately before Section 4.2), we introduce an **in-place vector lookup** strategy that enables access to the indices of a permutation without reconstructing the permuted vector.\n\n**Other Comments or Suggestions:**\n\nThanks for the suggestions. We will change the organization of the proofs accordingly.\n\n**Questions For Authors:**\n\n*1:*\n\nWe kindly refer you to our response to Reviewer #1’s last suggestion for additional context on this point.\n\nIn standard PyTorch implementations for 1.58-bit LLMs (e.g., using formats like I2_S [1][2]), the weights are stored in a packed format—typically encoding four 2-bit values into a single uint8. However, during inference, these packed weights are unpacked and converted into bfloat16 format for computation (**nn.BitLinear** module).\n\nIn contrast, the more efficient bitnet.cpp implementation—which we included in our updated experiments (see the response to Reviewer #1’s suggestion)—performs matrix multiplication directly on the packed uint8 weights, avoiding the unpacking step. Even in this optimized setting, our RSR algorithm shows a significant speedup in matrix multiplication (a PoC of RSR is implemented alongside bitnet.cpp; please refer to the anonymous repository). This is evident in the inference time comparison plot available at:\n[https://anonymous.4open.science/r/RSR-1566/bitnetcpp/figures/inference_time_plot.png](https://anonymous.4open.science/r/RSR-1566/bitnetcpp/figures/inference_time_plot.png)\n\n*2:*\n\nThank you for pointing this out, and we apologize for the lack of clarity. The reference was intended to describe the segmentation matrix $\\mathcal{M}$, which is introduced to support parallelism, as discussed in Appendix C.1. To enable compatibility with underlying parallelism, we transform the original matrix $M$ into a tensor $\\mathcal{M}$, reducing the vector-matrix multiplication to a vector-tensor multiplication (see also our response to Reviewer #2).\n\nWe will revise the main text to explicitly define the segmentation matrix and clarify its role. Importantly, $\\mathcal{M}$ occupies the same amount of memory as the original matrix $M$, since it contains the same number of elements—only its shape differs.\nIn more detail, the tensor $\\mathcal{M}$ is generated by stacking $n / k$ smaller matrices of shape $n * 2^k$ (Appendix C.1). The size of this tensor is: $n * 2^k * n / k$. After multiplying this 3D tensor to the $Bin_{[k]}$ matrix (which has the size $2^k * k$), we create a matrix of size: $n * n/k * k = n^2$ which is stored in the preprocessing phase and used in the inference as a replacement for original matrix $M$.\n\n*3:*\n\nPlease also refer to our final response to Reviewer #2 for a discussion on how RSR supports parallelization across different phases of the algorithm.\n\nAs described in Appendix C.1, during the preprocessing phase—where we have full access to the weight matrices—we construct a segmentation matrix $\\mathcal{M}$. This tensor is then stored and used for inference. During inference, any parallelization strategies that applies to standard vector-matrix multiplication (e.g., tiling in GEMM) remain fully applicable. That is, the same tiling mechanisms can now be applied to $\\mathcal{M}$ instead of the original matrix $M$.\n\nImportantly, $\\mathcal{M}$ has the same total size as the original matrix $M$, but a different shape. In fact, for the experiments in Section 5.4 (LLM on GPU), the PyTorch’s default parallelization mechanisms are already being applied on top of the RSR-transformed matrices.\n\n*References:*\n\n* [1] Wang, Jinheng, et al. \"1-bit AI Infra: Part 1.1, Fast and Lossless BitNet b1. 58 Inference on CPUs.\" arXiv preprint arXiv:2410.16144 (2024).\n* [2] Ma, Shuming, et al. \"The era of 1-bit llms: All large language models are in 1.58 bits.\" arXiv preprint arXiv:2402.17764 1 (2024).", "claims_and_evidence": "The claims are supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria make sense. The RSR and RSR++ algorithms seem to improve efficiency. The runtime of RSR and RSR++ is reported in the paper.", "theoretical_claims": "I checked the correctness of Theorem 3.6 and Lemma 4.2 and they seem correct. However, the proof of Theorem 4.4 is missing and I think it should be formally introduced.", "experimental_designs_or_analyses": "The experimental designs and analyses are generally sound and valid. However, the baseline implementation in the GPU runtime comparison section is somewhat unclear. I am curious whether the standard ternary matrix multiplication in Table 1 and Figure 12 was performed by casting the ternary weights to 16-bit or 32-bit floating point values.", "relation_to_broader_scientific_literature": "The proposed method could potentially be applied to graph processing or graph-related applications, such as Graph Neural Networks [Zhou et al., 2020] and Low-Density Parity Check (LDPC) decoding [Gallager, 1962].\n\n[Zhou et al., 2020] Zhou, Jie, et al. \"Graph neural networks: A review of methods and applications.\" *AI Open*, 2020.\n\n[Gallager, 1962] Gallager, Robert. \"Low-density parity-check codes.\" *IRE Transactions on Information Theory* 8.1 (1962): 21-28.", "essential_references_not_discussed": "The related works are addressed well.", "other_strengths_and_weaknesses": "**Strengths**\n\n- The paper is clearly written and easy to follow, with examples that effectively illustrate the concept of the proposed method.\n- The proposed method demonstrates a meaningful reduction in CPU latency for LLM inference, which could have a substantial impact on running LLMs efficiently on edge devices such as laptops or mobile phones.\n\n**Weaknesses**\n\n- RSR and RSR++ involve permutation of the input data, which may result in additional memory I/O overhead.\n- It is unclear whether the proposed method is applicable to tiled matrix multiplication, a common GEMM implementation for multicore CPUs or GPUs.", "other_comments_or_suggestions": "Propositions 2.1 and 3.5, as well as Theorem 4.4, are missing proofs. While the proofs are straightforward, I believe each claim should be accompanied by its proof for completeness. Additionally, the proof of Theorem 4.3 appears before the theorem itself. It might be more appropriate to place the theorem at the beginning of Section 4.2.1, followed by its proof.", "questions_for_authors": "1. Was the standard ternary matrix multiplication in PyTorch performed by casting the ternary weights to 16-bit or 32-bit floating point, or was a custom kernel used for ternary weights?\n2. In the last sentence of Section 5.3, it is stated that the size of the segmentation matrix is identical to that of the ternary weight matrix in the PyTorch implementation. Could the authors provide more clarification on why this is the case?\n3. Does the algorithm require any modifications to be adapted for tiled GEMM?", "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: All reviewers advocated acceptance of the work, with two weak accepts and two accepts following the rebuttal. Reviewers consistently found the work well written and explained, including with diagrams. Reviewers generally found the empirical results and evaluation metrics presented as convincing as to practical speedups being demonstrable with the proposed methodology, on both CPU and GPU. In fact better results would be expected with low-level implementation as discussed by the reviewers and authors. Reviewers did have some concerns including the practical usage with KV cache for multiple tokens, the lack of clarity on GPU baselines, and comparisons to other implementation, but these appear to have been addressed by the authors. With the topic of LLM inference acceleration being of great interest in the research community, the clearly written paper, and the extensive analysis and results I believe this paper is a solid contribution to ICML.
Decision: Accept (poster)