SS1: Accelerating Inference with Fast and Expressive Sketch Structured Transform
Authors: Aditya Desai
Kimia Saedi
Apoorv Walia
Jihyeong Lee
Keren Zhou
Anshumali Shrivastava
Venue: NeurIPS 2024 poster (2024)
Keywords: fast linear transform
parameter sharing
latency improvement
deployment
Primary area: other
TL;DR: Linear transform with latency benefits ,better parameter-quality tradeoff

Abstract: Tensor multiplication with learned weight matrices is the fundamental building block in deep learning models. These matrices can often be sparsified, decomposed, quantized, or subjected to random parameter sharing without losing accuracy, suggesting the possibility of more efficient transforms. Although many variants of weight matrices exist, unstructured ones are incompatible with modern hardware, slowing inference and training. On the other hand, structured variants often limit expressivity or fail to deliver the promised latency benefits. We present Sketch Structured Transform (SS1), an expressive and GPU-friendly operator that accelerates inference. SS1 leverages parameter sharing in a random yet structured manner to reduce computation while retraining the rich expressive nature of parameter sharing. We confirm empirically that SS1 offers better quality-efficiency tradeoffs than competing variants. Interestingly SS1 can be combined with Quantization to achieve gains unattainable by either method alone, a finding we justify via theoretical analysis. The analysis may be of independent interest.
Moreover, existing pre-trained models can be projected onto SS1 and finetuned for efficient deployment. Surprisingly, these projected models can perform reasonably well even without finetuning. Our experiments highlight various applications of the SS1:
(a) Training GPT2 and DLRM models from scratch for faster inference. (b) Finetuning projected BERT models for 1.31× faster inference while maintaining GLUE scores. (c) Proof of concept with Llama-3-8b, showing 1.11× faster wall clock inference using projected SS1 layers without finetuning. We open source our code :https://github.com/apd10/Sketch-Structured-Linear/

SS1: Accelerating Inference with Fast and Expressive Sketch Structured Transform
Kimia Saedi
Aditya Desai
Apoorv Walia'
Jibyeong Lee² f
Keren Zhou²
Anshumali Shrivastava 1.3
Rice University George Mason University
Ken Kennedy Institute, ThirdAI Corp., Xmad.ai (ks152, apd10, aw82, as 143) @rice. .dduuduu {j {jlee436, kzhou6) 0gmuu.)gmmmummmmmmmm edu
Abstract
Tensor multiplication with learned weight matrices is the fundamental building block in deep learning models. These matrices can often be sparsified, decomposed, quantized, subjected to random parameter sharing without losing accuracy, sug- gesting the possibility of more efficient transforms. Although many variants weight matrices exist, unstructured ones incompatible with modern hardware, slowing inference and training. On the other hand, structured variants often limit expressivity or fail to deliver the promised latency benefits. We present Sketch Structured Transform(SS1) an expressive and GPU-friendLy operator that acceler- ates inference. SS1 leverages parameter sharing random yet structured manner to reduce computation while retraining the rich expressive nature of parameter sharing. We confirm empirically that S$1 offers better quality--fficiency tradcoff's than competing variants. Interestingly SS can be combined with Quantization to achieve gains unattainable by either method alone, a finding we justify via theo- retical analysis. The analysis may be of independent interest. Moreover, existing pre-trained models can be projected onto S$I and finetuned for efficient deploy- ment. Surprisingly, these projected models can perform reasonably well even without finetuning. Our experiments highlight various applications of the SS1: (a) Training GPT2 and DLRM models from scratch for faster inference. (b) Finetuning projected BERT models for 1.31x faster inference while maintaining GLUE scores. (c) Proof of concept with Llama-3-8b. showing 1. faster wall clock inference using projected SSI layers without finetuning. Our code is open-source)
1 Introduction
Tensor-matrix multiplication is one of the fundamental operations in deep learning models across various domains. Linear transformation are especially crucial in transformer architectures, which form the backbone of foundational models responsible for the advanced capabilities of Large Language Models (LLMs). A significant portion of the computational load in LLMs comes from linear layers. For example, with batch size of 4 at full sequence length, the MLP workload of even the smallest Llama-3-8B model [[] involves (32768 x 4096 4096) operations in attention and (32768 x 4096 x 14336) in the MLP. Larger models have even larger workloads. Given these demands, finding efficient and expressive alternatives to standard linear layers is crucial research direction.
Deep learning models often have significant redundancies that can removed using various tech- niques. Popular approaches include Sparsification 2 3
6
Quantization 2 Randomized
"Equal contribution; order chosen by flip of coin
Work done in sole affiliation with George Mason University "https://ittuu..om//// com/apd
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

Parameter Sharing (RPS) 8 9 10, and Low-rank decomposition [1 3 Unstructured sparsity, while expressive, is inefficient on modern hardware. Structured sparsity 12 1 and low-rank are efficient but often compromise quality. Recently, it was shown in [1] that sparsity is theoretically weaker than RPS methods regarding the quality of learned models under compression. However, traditional RPS methods only focus on reducing the parameter memory footprint and do not affect FLOPs or latency. This paper proposes Sketch Structured Transform (SSI), an RPS scheme that reduces FLOPs while maintaining quality and improving wall-clock inference for machine learning models.
Randomized parameter sharing (RPS) reduces the model's memory footprint by randomly tying parameters across the model. While these methods offer a superior memory-qualit tradeoff, they do not alter the computational graph, resulting in similar FLOPs and latency. Addressing this issue reducing computation and latency while retaining the memory-qualit challenge with RPS methods. In this paper, we propose a random yet structured sarameter-sharins method that maintains superior quality, reduces the number of FL,PPs, and improves the wall-clock latency of linear layers which are compute bound in most workloads.
tradeoff has been a key
The key idea in SS1 is tie parameters inside a single neuron weight. This weight-tying can be equivalently implemented as the input being reduced in dimension first and then multiplied with the compressed weight vector which reduces FLOPs and memory movement in neuron computation. We show how to devise this tying in a GPU-friendly manner using what we call K- and N- coalescing. Additionally, SSI can be integrated with existing RPS methods to obtain independent control of parameter memory and computation during training and inference. While SS1 layers can be used to build a model itself, we can also obtain S$1 models from pre-trained models. This is especially important since many useful models are pre-trained once, and weights are open-sourced for public usage. For this purpose, we provide a projection function to project full matrices onto SSI matrices, which can transfer knowledge from pre-trained models. Moreover, we demonstrate that SSI can be effectively combined with post-training quantization to harness the advantages of both approaches. Additionally, we present theoretical insights explaining why the integration of SS I and quantization leads to performance improvements that neither method can achieve independently.
We evaluate SSI layers on broad set of settings and use cases. A summary of our findings is below.
SS1 has better quality-efficiency tradeoff than competing methods like Monarch[16] (state-of-the. art structured sparsity) and LowRank[2] across various domains. With SS1, we can build better models at lower parameter counts while delivering superior inference latency. For example, achieve up to a 1.30x improvement in GPT2 [17] model inference throughput.
Pretrained models can be projected onto SSI and further finetuned deploy fast models. We show
that we can maintain the [8 score of BERT while speeding up inference by 1.31 x. SS1 projected models can be used even without finetuning with reasonable accuracies. We show proof-of- benefits in the Llama-3-8B model[[] with 1.11x x faster inference.
Quantization
21 is a highly effective technique for improving efficiency that can be combined with SS1. Not only do we see this empirically, but we can also see it in theory.
SS1 also impacts CPU ML workloads significantly. For instance, we reduce the MLP workload of DLRM 20) MLPerf Model, which contributes over 70% inference latency, by approximately 2x using SS1 layers without compromising model quality.
2 Related Work and Background
Unstructured Sparsity:
The redundancy in the deep learning model can be removed by sparsifying
the model using iterative procedure [2] 3 4. Another related line of work is that of Lottery ticket hypothesis 6 6 211, which tries to find a sparse model at the start of training. Apart from expensive procedures to find these subnetworks, the unstructured sparsity still needs to deliver on the promise of latency improvements for inference.
Structured Sparsity: Linear transformations that are efficient and expressive has been an active line of research for over a decade. The general direction here is to create combination of sparse, diagonal,
permutation, and sub-linean transformations such as FFT, DCT, and Hadamard [14] [2 [3] 23 24]. Some of them also used fixed random sparse/diagonal matrices. Structured matrices proposed in this line of research for transformation of size K x K have O(K) parameters and O K)) FL.OPs. The actual speed-up obtained on modern hardware using these methods is limited. More importantly, the expressivity of these matrices is severely restricted due to very few learnable parameters. A
2

---

recent line of work exploits butterfly matrices [25] 16 and their variations, such as Monarch to obtain expressive transformations. These matrices also fit the general recipe of structured matrices specified above. However, a critical distinction in Monarch matrices is the presence of many more parameters. Specifically, the pure monarch matrices are supposed to contain O / K parameters and FLOPs when using v K blocks or factors (more blocks imply fewer parameters). However, practically, the matrices that have enough representative power in deep learning context generally use two or four blocks (16), i.c. (K²)) parameters and FLOPs. Nevertheless, Monarch shows great latency benefits for training with scheduled different-sine -izzd monarch decomposition. However, to our knowledge, the inference benefits for these matrices are limited. Our paper compares SSI against Monarch since it is the SOTA representative for this class of matrices.
Post training quantization [2] is currently one of the most successful tools for improving large models' efficiency. The basic idea to reduce the precision of the weights and activations to reduce the memory footprint of the model and also exploit integer arithmetic [ for better compute throughput. The literature on quantization vast, and more details can be found the survey 26). In this paper, we show that improve latency. We also explore the theory of combining quantization with SSI approximation in section 4 which can be of independent interest.
Quantization:
combine SSI with quantization techniques to further
Randomized parameter sharing was first introduced in g as a general model compression tool. RPS is primarily used to reduce the parameter memory footprint of models. The parameter memory is separated from the model's actual computational graph. Each model's weight is mapped to the parameter memory using random hash function. The value of the weight is then the value from the parameter accessed via hash functions. Essentially, if two weights are mapped to the same value in parameter memory, they are tied together and share a single learnable parameter.
Randomized Parameter Sharing:
The randomness of weight tying that leads to theoretical guarantees concerning projection quality was also the reason behind the extremely slow systemic performance of the proposal. The systemic performance was fixed using block-based hash mappings showing practical applications in various projections [O] leading to a strictly superior RPS system. RPS quality was further enhanced using global parameter sharing (parameter sharing across modules) which is superior to -pouuee-peccific parameter sharing (9. This, however, leads to additional challenges regarding the stability of training the model. These challenges were resolved in [T5]. This work also proved a missing link in the theoretical analysis of RPS methods- it showed that the quality of dimensionality reduction (alt. projection quality) directly correlates with the quality of models learned under projection for linear models. Further, it was shown that random dense projections (which underlie RPS) are superior to random sparse projections (which underlie Pruning) which justifies why RPS methods convincingly outperform pruning methods, especially at high compressions in [15]. Interestingly, most of the RPS literature is strictly focused on reducing the memory footprint and does not affect the computational workload. In this work, we further improve the utility of RPS techniques by deploying them to reduce computation.
domains [10 g 27). Surprisingly, the projection quality improves with
2.1 Background on Randomized Parameter Sharing required for SS1
Tying of parameters using hash functions (1,,g): Under RPS, there is a single parameter memory M. MM| = m. and each weight inside the model is mapped to one of the parameters in the memory using hash functions. Let the flattened weight vector of the entire model be 0, (0) = A weight, say 0 0 is uniquely identified using a set of integers (module number, location inside the module, etc.),
say id(i) E N for some k. and then the value of the weight is
011 g(id(i)) M(((d())
h: N + [m].9: No {+1)
where [m] = {0, m-1}
Sketch representation of recovery: We can write the entire recovery of the vector 0 as linear projection from M using a sketch matrix S E Raxm which is defined as
Vj + hid((i)) S[i 0 Then the weight f and the parameter memory M is related by, = SM
Vi [m). S(i Mid((i)) = g(id(i)),
(1)
Dimensionality reduction problem: Traditionally, random projections are used as a dimensionality reduction technique for data points. The projection is considered better if it can maintain the structure of the dataset poin distances equivalently inner products between points). The
3

---

W K x X
2D super group
Rotation of weights in group using hash function
K-coalescing:
0
share parameter chunks
Bg
10 super group
1
2
0
3
Bx
4
N-coalescing share the same hash function (denoted by rotation offset position
Figure 1: Illustration of weight tying in SS1. Same colored weights imply that they are tied to the same parameter in memory
standard theoretical setup is follows. Consider two arbitrary vectors v, E R", Consider projection function PROJ (or compression technique in general), then ă, ÿ are projected vectors, PR)J(x)) 9 PROJ(y). Then, the quality of the projection measured by
MSE(( ú)) E (z,, (i, 7)
where the expectation is over the randomization scheme the projection. This problem is of interest to evaluate RPS- based learning since the quality of the learned model under projection f(SM) correlates with the quality of data projection S for the standard dimensionality reduction problem with = S x and i = S [15].
3 Sketch Structured Transform(SSI)
The SSI layer falls into the category of RPS methods. We will use small case letters for scalars, boldface small cases for vectors, and boldface capitals for matrices. We use numpy notation of indexing. For instance z[(r z[(range(r)) + 5]% : first rotates the vector z by 5 places and then selects subarray from to j.
3.1 Parameter sharing in SS1
In standard RPS, where the weights are mapped into single memory M, with high probability, weights corresponding to a single neuron are not tied together. While this seems advantageous for expressivity, it is also the reason why RPS methods cannot reduce computation since we need to a single neuron. In SS1, we perform restricted parameter sharing where parameters are tied inside single neuron only. Consider linear transform y where X E RK E IN and W R KNN matrix.
perform (K)) multiplications
W
Let consider single neuron x TTw. w. Under SS1, the weights TR.K come from compressed parameter vector KR// where is the compression factor. We use / //t to denote integer division. For simplicity, we assume throughout the section that e an integer and e K. Each neuron has its own Weights recovered from using standard RPS. i.e.,
Single Neuron RPS:
(f)))(
(3)
Equivalently, can be represented
w Sz
(4)
where S K K//cis sparse matrix according to Equation manner, the computation can be reduced.
When parameters shared in this
T w = x
(Sz) = (x S)
(5)
Thus computing y needs only K//c multiplications since T S, sketch of input x, can be im- plemented using only additions and subtractions. As is, this randomized mapping will not be cache-efficient and thus not GPU-friendly. We show how make GPU-friendly using K and N cocallescnng in the subsequent parts of this section.
K coalescing: The single-neuron computation shown above is not GPU-friendly for arbitrary choice of RPS mapping hash function h. We now explain the hash function h used in SSI.

---

The parameter tying is illustrated in Figurel 1 We first divide the weight vector w into chunks or groups of size Bx, hyper-parameter The chunk-id and offset inside the chunk of weight can be written as,
C(i) = i//Bk
(i) = 1%BK
(6)
Then e recall that is the integral compression factor) ) chunks are grouped together into ID supergroups. The ID super group ID of the weight can be written as,
(i) = /(i)//c
(7)
We want to restrict the hash function in SS1 to ensure the following,
1. Each chunk of size Bk is contiguously located in and do not share weights. chunks that belong to the same ID supergroup share weights among each other.
We use the following mapping h' [K] - /c/cc| to satisfy both conditions. Let h N N N be a universal hash function. Then,
(i( = 9 (0)Bx +
(8)
Note that many hash functions which follow the two conditions exist. However, we will stick with this hash function since this is the function we implement. With this hash function, the jth chunk of ith 1D super group in w can written as,
w w[(ic + j)Bk (ic + j + 1)Bk] = z(iBk (i 1)BRI((R(O Bk) + h(t,)))%Bkk
(9)
where R(0 n) (0, 1..1...., n 1) is the range function. In matrix form using Equation 1 let
Stj Bg B& be the matrix representation of above hash function restricted to jth chunk of nd supergroup. Then,
1D
w[lic + j)Bk: (ic + j + 1)Bx] StgzliBk : (i + 1)Bk]
(10)
Then, we can write the single neuron computation as,
(K//BR//o)-1
c-1
Σ
x Σ
[[ic + +J)Bk: (ic + 1)Bx]S,,) z/iBk: : (11)
y = x
1=0
We can implement the above computation as follows: Bring in one chunk of z; then bring in e chunks belonging to the ID super group of x one at time and aggregate them into a single chunk of size Bk using sketch matrices S; perform the dot product on the chunk of z and aggregated chunk of and move on to the next chunk of z and ID supergroup of x. Note that we can perform this operation block manner and using exactly one read of z and x due to the nature of the hash function.
N coallescing: Now let us move our discussion from single neuron computation in SS1 to computing all the neurons, i.e. the entire matrix multiplication. In this case we have the complete weight matrix W K x N which is derived from a compressed matrix Z K//c x N. Apart from K- coalescing further restrict parameter sharing
specific each neuron, fully utilize the GPU capabilities, along the N dimension. The weight mapping is illustrated in Figure I We divide the weights along the N dimension in column blocks of size By. Each neuron that belongs to the same block will have the same set of hash functions. This allows us to do block- computation as,
y|: Bx] = x W(::: BN]=
(K//Bx//o0-1
(12)
Σ
Σ x (((c++))B +ic+ + 1)k]S Sa., 7=0
Z(iBk: (i 1)BK; BN]
Note that each neuron has its own parameter space in Z. The complete algorithm is presented in Algorithm [ It considers batched multiplication and uses BM hyper-parameter, which is standard in matrix multiplication. Also, it uses a slightly different notation for ease of expression. However, it maintains the principles introduced in this section. The kernel implementation and optimization details are deferred to Appendix D for lack of space.
3.2
SS1 projection from the pre-trained model
pre-trained model can be projected into SSI and fine-tuned for downstream tasks. The complete model projection boils down to projecting each full matrix in linear layer, say W K x N into parameter tied SSI matrix (K//c) x N. Recall that SSI has parameter sharing independent in each neuron. Thus, just have to find the projection for each neuron's 's weight. Consider the neuron
5

---

Algorithm SSI(Z, X)
Require: X E RM data matrix, e N: integral compression factor, Z R(K//O)NN weight matrix, BM.. BK, By: coalescing parameters, h: No + {0..... .....,BK- BR - 11, N {+1)
Require: cBxl K
Ensure: Y E I MxN SS1(X, Z)
T T,=TILE(By, Bx): T,,TTILEBB, Bg) Allocate 2D tiles. Tg will store the intermediate input sketch and Ty will store intermediate result
2: for E [[M//B /B | do
3: for [[ BAN/BN// BN(]]]] do
4:
Ty :=
b reset output tile
5:
for l: E [[K/c]]] do
6:
To ==
D reset input tile Iterate over blocks create input sketch Bring in one chunk of input a= و k. l) (R(0: B:00:xk)-hhpp -hj [)]%BR] Rotate input by random offset Aggregate the sketch
7:
for 1 E [c] do
8:
a= X iiBM : (i 1)
9:
10:
T
11:
end for
12:
Ty T TMMM( Bx b Fetch block of Z, perform
MM with sketched input and aggregate in tile T,
13:
end for
15: end for
end for
y x w and corresponding compressed with and recovery sketch matrix S. Given w, want to find z that minimizes
z = argmin ||w Sz|12
(13)
The solution is that of linear regression, z" -S w. Note that (STS) is a diagonal matrix with non zero diagonal elements. Once we solve for the value of z for each neuron in each weight matrix, we have our overall projection onto SS1. The algorithm for projection can also be implemented in a blocked manner and given Algo Appendix G
3.3
SS1 combined with standard RPS.
SS1, which reduces the computation of the linear layers, can be combined with RPS methods, which reduce the parameter memory to create a holistic efficiency system one that lets you control both memory and computation independently. The only change to Algo in where we read the weight tile. the current algorithm, we maintain Z K//e x N, the compressed weight matrix, row-major format. Under RPS, we can locate the tile Z[kBK= (k + 1)BK, (]BK.jBa jBx (ī + 1)Bx] in the RPS memory, say M, using another hash function, say h1, MM j) Bx Bx).
Theoretical aspects of SS1
Quantization + SS1 can beat the individual methods: In this section, we analyze combination of quantization and SS1 (i.e., projection) in the standard dimensionality reduction setup. We consider stochastic integer quantization for our analysis. Con- sider two vectors x, y E IR". We aim to reduce the memory by a factor of c. In case of quantization, assuming initial precision as F, b/ F if we are using b-bit quantization. Similarly, for projection, e m/n if projecting the data Rm, In case of projection the compressed vector can be represented:
Figure 2: Upper bound on variance
0.5
Molline of mnt. vecturs
Projection Vanaane
[ Σ ((()(1))))))x(
(14)
Quantizaton varlance
Quanczation Projection
Let the component values restricted to (-D/2 D/2) for some D. The compressed vector in case of stochastic quanti-
Compression

---

zation can be written as,
1 with prob p (x[1] [x(:],.)
x [
[x 1 where
D/2
(15)
0 with prob (1
The range is divided into 2 buckets and L.Ig rounds the value down in the buckets. The variance of the inner product between (&, y) for projection, quantization, and combination that first performs b-bit quantization followed by projection is given below.
Theorem Consider two arbitrary vectors x, y E R such that ||x|| S 1, |yll & in F precision. For some fixed value k in [1,
2
n
k
Q(c)
P(c)
(16)
2 The variance of quantization (((, projection (V 9)p)) with compression e, can be lightly bounded by
24c
en
Q((c) v((x5))) S P(c)
(17)
The variance of combination with compression e = CpCy with quantization with compression Cy followed by projection with Cp is bounded by
9) S Q((g) (1+ 1 (p)
+ P(e)
(18)
The best way to understand this theorem is to plot the variance a function of compression as shown in the Figure 2 In the plot, we use Gg = 0.3, = 128 and = 1.5 for illustration. As we can see with the combination, the variance is better than individual methods in certain regions. The reason that both methods do quite well in the low compression regime, and explode steeply at very high compression. Thus, when we combine the two methods, we can remain in relatively low error zones for both methods while obtaining greater overall compression.
Analyzing parameters of SS1: This section discusses the new aspects of SS1 and how it affects the quality of SS1. Specifically, we discuss the effect parameters Bą and By. From a latency viewpoint, it is natural that these parameters should be autotuned optimize for latency, which is standard for matrix multiplication. However, since these parameters affect the weight tying, it is important to investigate their effect the quality of models. We consider the standard dimensionality reduction setup to evaluate the changes in mapping performed by S$1. We find that Bę is a pure latency parameter with no impact on learning quality. We present this as the following result.
Theorem Consider two vectors x,y E R" in higher dimensional space. Also, let and g be the SSI hash functions used to project these vectors to & E R" (m < n)) Let By be the K-coalescing factor of h. Then, under compression e = n/m and assuming cBıc mmmm, the inner product estimation is unbiased and hus variance,
V((
Σ
Σ
Σ T(i,5) (1iU) + (.05319)
(19)
BR 1.j=1
where [ii,j) is a Kronecker delta function indicating if and j belong to the different groups in the super group of size cBg. Under permutation of elements of x and y before projection.
(c (c-1) (<-)))))((-)))>))))))-) Σ Σ (oi1) ( x
Ep (V - -x,)))
(20)
(n i= j=ijj
In the above theorem, we find that the quality of projection is unaffected by the parameter Bg. This can be understood by considering a specific element in x. The number other elements with which it can interact under projection depends only on the compression factor = n/m and not on Bg. We know from [15]. that the quality of projection is directly related to the quality of learned linear models under compression. Thus, Bg does not have any impact learning quality well. We analyse the effect of Bx as well. But the analysis is deferred to the appendix (see section F2) for lack of space.
7

---

Table 1: This table presents the quality and latency of NLP and vision experiments. Overall across both the domains, SSI gives best quality models under similar parameters and better quality per unit compute. terms of inference latency, we see upto 1.3x increase throughput. Exact experimental details are present in Appendix
PPL (GPT2-S)
loss (GPT2-S)
Model Latency
Model Latency (GPT2-M)
Model Latency (GPT2-L)
Model
#params
(GPT2-S)
b=16
b=32
b=
b=32
b=8
b=
Original Model
124M
20.43
3.004
80.4
160
181
00m
190
376
SSI-2x
96M
19,458
2.957
78.5
154.9
172.4
342.7
169.9
334.2
SS1-4x
81M
19.998
2.991
75.1
148.6
163.3
330
157.6
310.4
SS1-8x
74M
20.68
3.025
74.3
145.6
153
309.3
147.9
291
Monarch (nb=2)
103M
19,606
2.964
90
178.2
201.8
401.6
194.8
386.5
Monarch (nb=4)
85M
20.611
3.022
88.2
174.2
186.9
371
178
363.77
Monarch (nh=8)
76M
22.839
3.119
85.5
169.4
181.1
359.4
173.6
342.8
Lowrank~2x
19.756
2.979
99
195.2
231.5
456.3
150
295.3
Lowrank~4x
8IM
20.152
2.993
84.8
165.6
159.1
314.2
137
266.6
Lowrank-8x
74M
21.211
3.05
72.2
141.4
147.3
290.7
131
259
GPT models wikitext-103 (standard deviation around 0.2PPI. measured for baseline model)
Accuracy (C100)
Accuracy (C10)
Model Latency (MM-S)
Model Latency
Model Latency
Model
#params
(MM-M)
(MM-L)
b=512
b=IK
b=512
b= IK
b=512
b=lK
Original Model
1.1M
0.6751
0.9083
7.9
15.4
38.1
75.4
122.5
246.1
SS1-2x
613K
0.6692
0.8918
8.3
14.7
36.2
71.7
114.3
227.3
SSI-4x
347K
0.6463
0.8695
8.2
14.7
66.7
100.4
199.2
SS1-8x
282K
0.6068
0.8554
8.2
14.5
65.5
95.0
188.1
Monarch (nb=2)
750K
0.6738
0.8729
12.5
20.8
47.7
94.4
135.9
272.9
Monarch (nb=4)
422K
0.6261
0,8491
12.9
21.3
46.2
91.7
119.9
2399.
Monarch (nb=8)
259K
0.5731
0.8282
14.2
23.4
46.0
91.4
115.3
229.8
Lowrank~22 2x
750K
0.6628
0.8907
9.7
18.4
38.6
78.1
114.6
231.7
Lowrank~<4x
422K
0.6299
0.8639
9.5
18.1
35.9
72.0
100.6
204.2
Lowrank~88x
259K
0.5353
0.8034
9.4
17.9
35.6
71.3
94.9
191.1
(b) MLPMixer models CIFAR datasets (Stdev: 0.001 (2x), 0.002 (4x), 0.02 (8x))
Table 2: PPL((oss) for [Left]: Applying quantization some saved checkpoints of original and SS1 models. The effect of quantization on SS1 similar to that on full model. [Right]: SSI models can outperform standard models. The std-deviation is around 0.2PPL for these experiments.
Quantization + SS1 Before Quantization
SSI vs. Small
After Quantization
Model
#param
Model
#param
Quality
21.228
21.25
GPT2-S
19.71
GPT-S
124M
81M
(3.013)
(3.014)
(Small-4x)
(2.977)
GPT-S
20.497
20.53
GPT2-S
22.14
81M
76M
(SS1-4x)
(2.986)
(2.988)
(Small-6x)
(3.087)
GPT-S
21,228
21.26
GPT-S
20,50
74M
74M
(SS1-8x)
(3.023)
(3.025)
(Small-4x-SS1-2x)
(3.01)
Experiments
5.1
Accuracy Latency evaluation of SS1
We first evaluate the expressiveness and latency of SSI against popular baselines of Monarch, SOTA structured -basetty-based transformation, and LowRank transformation. We benchmark various shapes for the "nn. Linear.. Monarch, LowRank, and SS1 kernels evaluate the standalone kernel latency. We use the official Monarch implementation by the authors with number of blocks (nb) as the compression controlling factor. The results are deferred to the appendix due to space constraints. We also measure end-to-end model latency improvement for various sizes of GPT2 and MLPMixer (MM) 28 models. We show the latency of three sizes of models (small: medium:M.
httpr//ghhhhnnoiiaeeee////////oe linear.p

---

Table 3: [Left:]BERT pretrained model projected onto SSI and finetuned on GLUE benchmark. Due to the descripancy, we report both online and our local results of full model. The SSI model is 1.31x faster for higher batch sizes. Details are available in 1.2 [Right:] Proof of concept of applications in Llama-3-8B. We obtain 1.11x speed up in latency by compressing selective layers, without any form of retraining or finetuning. Details of the experiment are in I.3
SS1 projection followed by finetuning
SSI projection without finetuning
BERT-LARGE
BERT-BASE
LLAMA-3-8B
#par
GLUE score
#par
GLUE score
#par
MMLU
WINO
baseline
335M
80.4
109M
78.6
(reported)
baseline
baseline (our run)
65.05
76.1
335M
82.2
109M
82.16
8B
(our run)
(d: 0.0038)
(= 0.011)
79.6
79.9
61.26
69.93
SSI
181M
66M
SSI
6B
( [1: 0.203)
(# 0.066)
(#: 0.0039
(= 0.012)
Table 4: The time spent by 100GB sized DLRM MLperf benchmark model in various components. Specifically 70% latency is spent in Top MLP. We can reduce MLP workload by factor of 2x by training SSI layers without compromising quality of the model. (Statistical significance: multiple runs gives 0.8032)
Bottom MLP
Embedding Lookup
Top MLP
Top MLP params
Interaction
Quality
DERM DLRM-MLPerf x SS1-2x
6.63%
12.3%
9.7%
71.3%
1.7M
0.8032
needs CPU kernel implementation
0.9M
0.8032
and large:I.)for both architectures. Exact details are provided in appendix [T Additionally, we perform quality experiments in end-to-ent training using these matrices for two domains: (a) NLP: GPT2-S model on wikitext- 103 dataset [29] using test perplexity (PPL) and loss as the metric (b) Vision: MLPMixer on CIFAR (C10, C100) and Tiny-Imagenet datasets [3]] using accuracy the metric. The results are presented in Table The details of these experiments can found in the Appendix We make the following observations.
our kernel latency evaluation, SS1 consistently outperforms Monarch and LowRank under similar parameter budgets (Table 4 in appendix). Monarch is generally worse than full multiplication except larger shapes. LowRank is competitive with S$1 for higher compression.
The kernel-level latency benefits also translate to end-to-end model latency (Table and Table Tbp. This can be seen across both Transformer and ML.Mrieer architectures, two of the SOTA architec- tures for deep learning. Although, at times, LowRankLineaa gives better performance at higher compression, the quality of the model obtained is inferior to SSI. With larger models, we see an increase of around 1.3 in end-to-end throughput with SS1. It also enables us to run larger batches. In terms of quality, SSI consistently outperforms Monarch and Low Rank across NLP and Vision domains GPT and MLPMixer architectures under similar parameter budgets.
Overall, we see that SS1 allows better quality per unit compute than its structured competitors.
Building expressive and faster models: Should we build and train models with SS1 layers instead of standard linear layers? Although answering this question requires broader evaluation, we cautiously believe that the answer might be yes. We can indeed obtain better quality models by using SS1 layers instead Linear" layer. This demonstrated in Table The quality of the SSI model with 74M parameters is better than that of standard models with similar more parameters.
5.2 SS1 + Quantization
Quantization is an important efficiency technique to improve inference time memory and latency. Although SS1 already reduces the memory footprint and improves inference latency. it can be combined with quantization to obtain further inference benefits. One might wonder if combining two approximations (SS1 and quantization) can lead to worse-quality models. We show that S$1 can be combined with quantization without significantly impacting quality (also supported by theory) In fact, the effect of guantization on SSI is similar to the full standard model. The quality details before

---

Table PPL(latency) for GPT-2(124M) model trained with different compressions SSI and ROAST PPL(Latency)
2x
4x
8x
SS1
19.45(154)
19.99(148)
20.68(145)
ROAST 19.87(238)
20.20(237)
20.94(222)
To measure the latency benefits, we would have to implement quantized SSI kernels, which out the scope of this paper.
and after quantization are in Table 2
5.3 Dense-to-structured finetuning of pre-trained models for efficiency
We show that pre-trained models can be projected onto SS1-structured space and finetuned for downstream tasks. We demonstrate this by projecting selected linear transformations in BERT SS1 and training the resulting model on the GLUE Benchmark. We obtain a 1.31 x faster model which gives similar GLUE score in downstream tasks. More details mentioned in [ The results summarized in Table 3
We find that we can improve inference of Alama-3-8BB model for downstream tasks if we project carefully selected layers onto SS1. The selection is done on a calibration dataset that corresponds to the task at hand. We show that, even without finetuming, can reduce the computation involved in the model while maintaining reasonable accuracy. Results can potentially improve if we finetune post- post-projection as we see in BERT. The results are summarized in Table
5.4 Improving CPU workloads e.g. DLRM MI.Prrf Benchmark
While this paper focuses on providing GPU kernel for SS1, the algorithm can also be utilized to improve the inference performance of CPU deployments. Specifically, recommendation workloads of models such the Deep learning recommendation model (DLRM) often run CPUs due to humungous embedding tables. We consider the DLRM MI.erf Benchmark, which has 100GB embedding tables and 10MB MLP layers. Nevertheless, on CPUs, the latency bottleneck is that of matrix multiplications. Specifically, 71.3% of the time is spent in the top MLP component (see Table 4p. We show that we can train from scratch SSI version of DLRM, which has half the parameters in MLP and maintains the quality of the full model. While CPU-kernel implementation of SS1 is out of the scope of this paper, we expect that benefits shown on GPUs will also translate to CPUs, and thus, with SS1, we can improve the throughput of DLRM MLPerf Benchmark on CPUs without compromising the quality of the model.
5.5 Comparison with standard RPS method
We also compare SSI with standard RPS method. Since SSI focuses on compressing linear layers, we compare it with ROAST-MM compression with each matrix having its individual separate memory. The results are presented Table As expected, RPS methods do not improve the latency.
Limitations: Our work is mainly limited on two aspects. On the theoretical side, our analysis of parameters and the combination of quantization with SS1 conducted mainly over linear models, which is reasonable starting point. However, these results may not necessarily extend to deep learning models, and we plan to explore this in future research. Additionally, regarding our S$1 proposal, the efficiency gains are marginal beyond an 8x compression of parameters. In future work, we aim to develop efficient structures where the efficiency gains are more closely aligned with the degree of parameter reduction.
Conclusion
In this paper, we introduce an efficient structured linear transformation termed SS1. We demonstrate that SSI outperforms state-of-the fe-thhe-rt art structured baselines in terms of quality per unit of computation. Additionally, we show that SSI provides immediate benefits across diverse applications, including language understanding, generative AI, and recommendations. Furthermore, we illustrate how SS1 can be combined with the popular quantization approach to achieve further improvements. We also thcoretically explain the underlying reasons that may be of independent interest.
10

---

7 Acknowledgments
This work was supported by National Science Foundation SHF-2211815 and grants from Adobe, Intel, Total, and VMware.
References
[1] Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timo- thée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al. Llama: Open and efficient foundation language models. arXiv preprint arXiv:2302.13977 2023.
[2] Song Han, Huizi Mao, and William Dally. Deep compression: Compressing deep neural networks with pruning, trained quantization and huffmmn coding. ICLR, 2016.
[3] Song Han, Jeff Pool, John Tran, and William Dally. Learning both weights and connections for efficient neural network. Advances in neural information processing systems, 28, 2015.
[4] Song Han, Jeff Pool, Sharan Narang, Huizi Mao, Enhao Gong, Shijian Tang, Erich Elsen, Peter Vajda, Manohar Paluri, John Tran, al. Dsd: Dense-sparse-dense training for deep neural networks. arXiv preprint arXiv:1607.0438/ 2016.
[5] Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. arXiv preprint vrXiv:180303363; 2018.
[6] Jonathan Frankle, Gintare Karolina Dziugaite, Daniel M Roy, and Michael Carbin. Stabilizing the lottery ticket hypothesis. arXiv preprint arXiv:1903.0166 2019.
[7] Benoit Jacob, Skirmantas Kligys, Bo Chen, Menglong Zhu, Matthew Tang, Andrew Howard, Hartwig Adam, and Dmitry Kalenichenko. Quantization and training of neural networks for efficient integer-rrihmmeti-only inference. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 2704-2713, 2018
[8] Wenlin Chen, James Wilson, Stephen Tyree, Kilian Weinberger, and Yixin Chen. Compressing neural networks with the hashing trick. In International conference on machine learning, pages 2285-2294, PMLR, 2015.
[9] Aditya Desai, Keren Zhou, and Anshumali Shrivastava. Hardware-Aware Compression with Random Operation Access Specific Tile (ROAST) Hashing. In International Conference on Machine Learning, pages 7732-7749. PMLR, 2023.
[10] Aditya Desai, Li Chou, and Anshumali Shrivastava. Random Offset Block Embedding (ROBE) for compressed embedding tables in deep learning recommendation systems. In D. Marculescu, Y. Chi, and C. Wu, editors, Proceedings of Machine Learning and Systems, volume 4, pages 762-778, 2022.
[11] Tara N Sainath, Brian Kingsbury, Vikas Sindhwani, Ebru Arisoy, and Bhuvana Ramabhadran. Low-rank matrix factorization for deep neural network training with high-dimensional output targets. In 2013 IEEE international conference on acoustics, speech and signal processing, pages 6655-6653 IEEE, 2013.
[12] Trevor Gale, Erich Elsen, and Sara Hooker. The state of sparsity in deep neural networks. arXiv preprint arXiv: 19Xiv:1902.09.. 0955744 2019.
[13] Marcin Moczulski, Misha Denil, Jeremy Appleyard, and Nando de Freitas. Acde: A structured efficient linear layer. arXiv preprint arXiv:1511.05946 2015.
[14] Quoe Viet Le, Tamás Sarlós, and Alexander Johannes Smola. Fastfood: Approximate kernel expansions in loglinear time. arXiv preprint arXiv:1408.3060 2014.
[15] Aditya Desai and Anshumali Shrivastava. defense of parameter sharing for model compres- sion. In The Twelfth International Conference on Learning Representations, 2024.
11

---

[16] Tri Dao, Beidi Chen, Nimit S Sohoni, Arjun Desai, Michael Poli, Jessica Grogan, Alexander Liu, Aniruddh Rao, Atri Rudra, and Christopher Ré. Monarch: Expressive structured matrices for efficient and accurate training. In International Conference on Machine Learning, pages 4690-4721, PMIRR 2022.
[17] Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. Language models are unsupervised multitask learners. 2019.
[18] Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel R Bowman. Glue: A multi-task benchmark and analysis platform for natural language understanding. arXiv preprint arXiv:1804.00 074661 2018.
[19] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. arXiv preprint 180.04810004805, 2018.
[20] Maxim Naumov, Dheevatsa Mudigere, Hao-Jun Michael Shi, Jianyu Huang, Narayanan Sun- daraman, Jongsoo Park, Xiaodong Wang. Udit Gupta, Carolc-Jcan Wu, Alisson G Azzolini, al. Deep learning recommendation model for personalization and recommendation systems. arXiv preprint /9Xiv01906.00091,, 2019.
[21] Jonathan Frankle, Gintare Karolina Dziugaite, Daniel Roy, and Michael Carbin. Linear mode connectivity and the lottery ticket hypothesis. International Conference on Machine Learning, pages 3259-3269. PMLR, 2020.
[22] Yu Cheng, Felix X Yu, Rogerio S Feris, Sanjiv Kumar, Alok Choudhary, and Shi-Fu Chang. An exploration of parameter redundancy in deep networks with circulant projections. In Proceedings of the IEEE international conference computer vision, pages 2857-2865, 2015.
[23] Vikas Sindhwani, Tara Sainath, and Sanjiv Kumar. Structured transforms for small mootpintt deep learning. Advances in Neural Information Processing Systems, 28, 2015.
[24] Zichao Yang, Marcin Moczulski, Misha Denil, Nando De Freitas, Alex Smola, Le Song, and Ziyu Wang. Deep fried convnets. In Proceedings of the IEEE international conference on computer vision, pages 1476-1483, 2015.
[25] Tri Dao, Beidi Chen, Kaizhao Liang, Jiaming Yang, Zhao Song, Atri Rudra, and Christopher Re. Pixelated butterfly: Simple and efficient sparse training for neural network models. arXiv preprint arXiv:21 12, 12.00099, 2021.
[26] Amir Gholami, Sehoon Kim, Zhen Dong, Zhewei Yao, Michael W Mahoney, and Kurt Keutzer. survey of quantization methods for efficient neural network inference. In Low-Power Com- puter Vision, pages 291-326. Chapman and Hal//CRC, 2022.
[27] Aditya Desai and Anshumali Shrivastava. The trade-offs of model size in large recommendation models: 100GB to 10MB Criteo-tb DLRM model. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 33961-33972 Curran Associates, Inc., 2022.
[28] Ilya Tolstikhin, Neil Houlsby, Alexander Kolesnikov, Lucas Beyer, Xiaohua Zhai, Thomas Unterthiner, Jessica Yung, Andreas Steiner, Daniel Keysers, Jakob Uszkoreit, Mario Lucie, and Alexey Dosovitskiy. Mip-mixer: An all-mip architecture for vision, 2021.
[29] Stephen Merity, Caiming Xiong, James Bradbury, and Richard Socher. Pointer sentinel mixture models, 2016.
[30] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[31] Ya Le and Xuan S. Yang. Tiny imagenet visual recognition challenge. 2015.
[32] Guangxuan Xiao, Ji Lin, Mickael Seznec, Hao Wu, Julien Demouth, and Song Han. Smoothquant: Aceurate and efficient post-training quantization for large language models. In International Conference on Machine Learning, pages 38087-38099, PMLR, 2023.
12

---

[33] Thomas Wolf. Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue. Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, et al. Huggingface's 's transform- ers: State-of-the-art natural language processing. arXiv preprini arXiv: 190.03771 2019.
[34]
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang. Zachary Vitioo, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high- performance deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché- Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019.
[35] Philippe Tillet, Hsiang-Tsung Kung, and David Cox. Triton: an intermediate language and compiler for tiled neural network computations. In Proceedings of the 3rd ACM SIGPLAN International Workshop on Machine Learning and Programming Languages, pages 10-19, 2019.
[36] Paulius Micikevicius, Sharan Narang, Jonah Alben, Gregory Diamos, Erich Elsen, David Garcia, Boris Ginsburg, Michael Houston, Oleksii Kuchaiev, Ganesh Venkatesh, al, Mixed precision training. arXiv preprint arXiv: 17 170.033740 2017.
[37] Tri Dao, Dan Fu, Stefano Ermon, Atri Rudra, and Christopher Ré. Flashattention: Fast and memory-efficient exact attention with io-awareness. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 16344-16359. Curran Associates, Inc., 2022.
[38] Dan Hendrycks, Collin Burns, Steven Basart, Andy Zou, Mantas Mazeika, Dawn Song, and Jacob Steinhardt. Measuring massive multitask language understanding, 2021.
[39] Keisuke Sakaguchi, Ronan Le Bras, Chandra Bhagavatula, and Yejin Choi. Winogrande: adversarial winograd schema challenge at scale, 2019.
[40] Leo Gao, Jonathan Tow, Baber Abbasi, Stella Biderman, Sid Black, Anthony DiPofi, Charles Foster, Laurence Golding, Jeffrey Hsu, Alain Le Noac'h, Haonan Li, Kyle McDonell, Niklas Muennighoff, Chris Ociepa, Jason Phang, Laria Reynolds, Hailey Schoelkopf. Aviya Skowron, Lintang Sutawika, Eric Tang, Anish Thite, Ben Wang, Kevin Wang, and Andy Zou. A framework for few-shot language model evaluation, 12 2023.
[41] Felipe Maia Polo, Lucas Weber, Leshem Choshen, Yuekai Sun, Gongjun Xu, and Mikhail Yurochkin. únnbenchmarrs: evaluating llms with fewer examples, 2024.
13

---

A
Additional Details for checklist
Resource Details:
MLPMixer experiments: Each run takes hours on a single RTX Quadro 8000 machine
GPT2-Small experiments: Each run takes around 13 hours on four 32-GB V100 GPUs
BERT experiments: QQP, the largest dataset for finetuning with BERT-Large, takes
around 7-8 hours on RTX-8000 Quadro.
Llama experiments: on MMLU takes hour on 40GB A100
2. License details:
MLPMixer Experiments uses: CIFAR-10, CIFAR-100 datasets (30 (license: could not find) with MLPMixer GitHub https//gihhbb.com/mmmbbb77//// M-
(MIT License)
GPT2 Experiments uses: Wikitext-103 dataset [29] (Creative Commons Attribution- ShareAlike License (CC BY-SA 4.0) License) the code is obtained from fly GitHub repo: https://gthhub.com wwwpgihuu...ooHaaaaee www/ Research/yy presented in [16] (Apache-2..) license), the quantization experiments GPT2 uses the quantization method employed in 32) with GitHub repo: https://github.com/// generally obtained from the HuggingFace Transformers library 33 including GPT2 to- kenzier the repo is at
(MIT License) Codes are
with Apache-2.0 Li- cense. The backend of experiments is Pytorch [4] at https:/giitubbccom/oooorc//ppppp
Llama3 [ pre-trained weights and code are obtained from https://gituub.com//nee llama/llama3 (META LLAMA 3 COMMUNITY LICENSE AGREEMENT)
The kernels
implemented with Triton
35
with
GitHub
repo:
https://gitub..co/rrrooonnntiitt
(MIT License)
Massive Multitask Language Understanding Dataset MIT License.
Obtained via
HuggingFace Dataset library.
Winogrande Dataset Apache 2.0 License. Obtained via HuggingFace Dataset library.
The Microsoft Research Paraphrase Corpus License unknown. Obtained via Hugging-
Face Dataset library.
The Multi-Genre Natural Language Inference Corpus MIT License. Obtained via HuggingFace Dataset library.
The Quora Question
Licensed by Quora. www.quuor..commaouutttsss Obtained via HuggingFace Dataset library.
Pairs2 dataset
The Corpus of Linguistic Acceptability Obtained via HuggingFace Dataset library.
The Recognizing Textual Entailment (RTE) datasets Unknown license. Obtained via
HuggingFace Dataset library.
The Stanford Sentiment Treebank CCO: Public Domain license. Obtained via Hug-
gingFace Dataset library.
The Semantic Textual Similarity Benchmark Unknown license. Obtained via Hug-
gingFace Dataset library.
The Winograd Schema Challenge Unknown license. Obtained via HuggingFace
Dataset library.
anwweing NLI dataset CC BY-SA 4.0 license. Obtained via HuggingFace
Dataset library.
B Predicted Common Questions (PCQ)
Q: How do you choose datasets?
We begin with what Monarch evaluated w.r.t deep learning train GPT and finetune BERT. Additionally, we wanted to do a quality tradeoff analysis on wider data. So, we chose the vision datasets that LTH uses. Apart from that, choose the DLRM MLPerf benchmark as a representative of recommendation models.
2. Q: Do you see any training latency benefits? The computation in the backward pass is not reduced in SS1. So, in general, the backward
14

---

pass costs the same as the full model. In this sense, SSI is geared towards inference benefits. We might see some improvements due the lower overall memory footprint and metadata that the optimizer stores. But beyond that, we do not expect to see training latency benefits. Under the assumption that inference is more costly than training, this seems to be an okay thing.
3. Q: Why have you not measured latency with Quantization?
To measure latency with Quantization, we would have to write a quantized SSL kernel. For this paper, we want to restrict our code development to single kernel. Thus, we only show the quality preservation with SS1 + Quantization. Having said that, we expect the gains from Quantization to be present in SS1 + Quantization.
4. Q: Does this mean standard linear layers should always be replaced by the SS1 ? We would like to believe there an "additional" representative value in SS1 layers that can push the boundary of quality per unit compute. However, we want to be cautious while making this claim, and we will be rigorously evaluating SSI in the future.
5. Q: Why not block-sparse as a baseline?
Most of our experiments were done in FP16. Also, our kernels are optimized for FP16. Pytorch block sparse does not have a stable implementation when it comes to FP16. We see segmentation faults. Thus, we skip Block sparse bascline. Additionally, with recent work on sparsity vs. RPS, we believe that RPS should beat Block sparsity in quality per unit parameters.
6. Q: Monarch performance seems lower than what was reported in the original paper. We were surprised as well. We expected Monarch to do better. However, the paper also spoke only about the training times. In our paper, measure inference times. Additionally, we confirmed with the authors that we were benchmarking the correct code.
7. Q: Why was expressivity of SS1 not analyzed the way it has been done for other methods such as Monarch? While the analysis of Monarch is interesting and valuable piece of knowledge, it is debatable if the expressivity analysis is representative of deep learning requirements. Indeed, we show that SS1 beats Monarch in quality vs. parameters ( and compute), emphasizing that deep learning may not align with the notion of common transformations.
8. Q: Will the results GPT translate to bigger models such Llama? It is hard to say. But we believe that whenever the model is at capacity with the information it can learn, having these layers in slightly bigger model ( so it has similar computation smaller model) can help boost the quality.
9. Q: Where is the code? Visit our landing page: https://githbb.cco///d//////ssse Strruuurrdd Linear for all the details.
10. Q: What care needs to be taken for densu-to-struccuree finetuning? Different layers have different sensitivity to compression, especially when we want to preserve the accuracy of the pre-trained model. Thus, we have identify layers that cannot withstand the approximation. This can be done using some calibration data.
11. Q: Isn't 't this just feature hashing? No. Feature hashing (followed by linear transformation) is low-rank operation, with the first matrix being the fixed sketch matrix. Also, feature hashing is not GPU-aware and has bad latency performance. SSI applies feature hashing but for each neuron separately. The independence makes SSI full rank with high probability. Also, due to the coalescing factors, we make SS1 GPU aware and efficient.
C How does learning rate tuning affect the quality?
In our experiments, we always use the hyperparameters that are optimal for the original model. However, these hyperparameters are not optimal for different methods. We perform learning rate tuning for Monarch, a competitive baseline, and find that, while the perplexity improves for all methods with finetuning, the findings remain unchanged. The results are shown in 6
15

---

Table 6: Learning tuning on Monarch.
Method
Learning Rate
Loss
PPL
Monarch-8x
6c-4
3.119
22.83
9c-4
3.135
23.23
2c-3
3.107
20.65
8e-3
NA
NA
SS1-8x
2e-3
2.99
20.13
Low Rank-8x
2e-3
3.161
23.67
200
Nonerch
Lowflant
Lasono (ma) Howarr la botees)
D220 made
120
170
320
150
340
12.5
20.0
22.0
22.0
22.5
Perplexily [Jownr beller)
Figure 3: Latency vs. Perplexity Plot for GPT-S
D Different representation of latency quality results
The plot of latency vs. quality for GPT-2 is presented in figure 3
E Latency Parameters and Kernel Details
We have implemented three kernels for SS1, including forward, seodwward-weighh-gruteee and buckward-input gradient. Our implementations can be used on GPUs with or without tensor cores and support multiple precisions, such float16 and float32 (TF32).
We implemented permutation by adjusting the addresses load instead of permuting the data in shared memory. If permuting is done in shared memory, we have to permute the data again to adjust the value distribution fit the tensor core operands, thus wasting instructions on shared memory accesses and time in synchronizing threads within CTA (Cooperative Thread Array).
In the forward kernel, we launch [M/Ba] [N/Bx] CTAs. Each CTA, while accumulating along the K dimension, permutes the input block (i.e., X) with each data load. In the backward-input gradient kernel, each CTA permutes the weight block while accumulating along the N dimension. In the backward-weit weight-gradient kernel, each CTA only permutes the result before storing it in DRAM using atomi cAdd.
We have introduced the following optimizations to improve the performance of SSI kernels:
1. Vectorized Memory Load. Rather than permuting individual elements, we permute larger chunks of VCC elements along the K dimension maximize the GPU's memory band- width efficiency. The size of EC' can be selected from 1, 2, 4, or 8.
2. Pipelining. Utilizing asynchronous memory load instructions supported by the GPU archi- tecture, we preload Natages blocks prior the main accumulation loop to overlap compute and memory transactions.
3. Autotuning. To optimize performance across different tensor shapes, we implemented an autotuner select the ideal BM, Bx, BR, and Nstages- We also prune configurations that exceed the GPU's shared memory capacity before compilation and benchmarking.
16

---

4. Fusion. We have fused bias computation directly into the forward kernel to reduce kernel launch and memory access overhead.
SSI's forward kernel reduces the number of load instructions and computational overhead compared full matrix multiplications. However, the backward kernels of SS1 maintain the same level of load instructions and computational demand as those of full matrix multiplications, leading to similar performance outcomes.
Shape (12290, 768, 2304)
Shape (12289, 768 50256)
viree
Lowfanii wat Monsct
D3L
Lowtariiiea
Maraet
02.
6A000
1409)
24090
2300
04090
Shape (38884, 788, 3072)
Shape (38864, 3072, 769)
viru
LowRoae
1.593
32093
3000
3000
Figure Latency(ms) vs. Parameters for instance of workload in GPT2
F
Theoretical Results
F1
Claim: Bg a pure latency parameter
We will evaluate this under the standard dimensionality reduction setup (which related to learned model quality). Consider two vectors x and y in IR" space. Also, consider the smaller dimension to which these vectors being projected using hash functions defined in section with K-coalescing factor Bg. Let the final mapping be h. The inner product can be written as,
know is
(Σ (()1(()) = t)us
(x. )) Σ Σ (0))((()) 1),,,
(21)
Assume that By m// for simplicity. Then, the inner product can be written as,
(x,5) = (x, + Σ (M)))))
(22)
$
The estimator is unbiased since E(g(i)) = 0. The variance is,
n
v(( E (((* (x. y)) E
Σ (00G))(())))))))
(23)
V((
(24)
E
Σ
(25)
17

---

Nonzero terms appear if either of the two cases holds:
(i = ig and ji = =j2)
(i1 f/2 and i2 ji)
() - (x,, v)) E
1(h(0)=(())27
+E
Σ
1(h(1)=h()))
(Øj=1
(26)
"
Σ
P(1()=M())200}
Σ
P(k(i))()))
(27)
Σ Σ
P(h())-(()) (1/0) =.0:o,1)))
(28)
Note that
ij belong to different groups inside same ID super group
P(h(1)=(())
Bk
otherwise
Let j(i,j) be the delta function that j belong to different groups inside same ID supergroup
V( 9) - (x, -x,
I(i.j) (2?0) + x. BK i=1 j=l.j
Σ
(29)
Under a permutation p of the initial input a and y, the following is the probability since every element interact with all the elements from other groups inside the same supergroup.
Pp(I(i.5)) (c - 1)Bx
Thus, under permutation,
(c 1)BK
n
Ep (V(())))) (x,y)))
(x + 2.y.,,1)
(30)
(n 1)BK
im f=1,f
Ep (V(()))) - (x,y)))
c c-1 ΣΣ
Σ
(R? + ,.b
(31)
(n
Thus, BK is pure latency parameter and should be chosen for optimizing shared memory usage.
F2 How does Bn affect the quality?
To investigate the effect of Bx, let us consider how neurons in the same 2D super group and different 2D super groups affect each other. We present the result in the following theorem,
Theorem Consider two neurons y1, 92 E R output from a linear transformation under SSI. Let hn, l2, 91.92 92 be the hash functions used for the neurons. Let the weights for these two neurons be p. q Rm Let the input be x. E R Then, under the assumption that each signal x. D is independent, the Covariance between the values of neurons can be written as,
m
Coup(y1,y2)
Σ
Ph. 9i291 (i.99 (1)
12)
(32)
oz (1
if h1 h2s 91 92 91 + 92
E .n 02 (CouD(y), v2),
(33)
18

---

The above theorem points out that if two neurons belong to the same group, i.e., they share the hash functions, then the neuron outputs have unintended correlations and, thus, mutual information. So the larger value of By implies more neurons having interdependency and, consequently, lesser expressivity. Fortunately, in our experiments, we find that larger values of Bx also work well, and we optimize it for latency.
details: Intuitively, sharing the mapping functions across neurons will restrict the representative power of neurons since they will sketch the same parts of the input vector x with the same hash functions. We verify this intuition here. Consider the following two neurons under SS1 with weight
vectors
Σ Ps
Σ 91 (1) (1)
11
i=1
1/2
92 (12))
Consider the mutual information between y/1 and y2. Since we are dealing with linear computations, we measure the Covariance of the two neurons,
m Σ 1=1
a
Coup(yi. = Cov
Σ Pi
S ())
j=1
(34)
Coup(y),
Cov (pa, (M)
(35)
CouD(1i,
Σ
Σ
Σ
Σ Cov (pr, (1 (1xz))
(36)
Coup(yi, U2)
Σ
Ps nu.r (iaaaa66661lt101-------001441-11
(37)
Assuming independent signals in
Coup(y1.12)
ΣΣΣ Pt, P. 10 ==
(38)
Case 1: 1/1 and y/2 belong the same 2D super group
(Con(CCo)()) =
Σ MV
Pr h,
(39)
En.g (CouD 822
Σ
ΣΣX
Ps. 9r, 110))E)))(()=)1)((0==))11
(40)
19

---

Only non zero terms when i1 ig since h(s) can only have one value
g (CooD(L1 =
p.q. P.q.E (1(h))(()))
(41)
5=1
En. (Co,(CooUDyyy (yr,
=
m 1|1111 (p.9)
(42)
π
Case 2: y/1 and y2 belong to the different 2D super group
Eng (y1. 92)) = 0
(43)
Thus, if two neurons are in the same 2D group, the structure imposes the two neurons to be correlated and thus reduces the expressive power of the model.
F.3 Quantization + SS1: How combining them results in a better method for compression.
Analysing quantization under standard dimensionality reduction Consider two vectors 2, y with values from the range |- DD/2, D/2]. Under stochastic Quantization for b bits, we will have
x x + A
(44)
where A|i] = ([x] - xi) + (Lx] - (1 - (i)) where
with prob p (x- 1z))
1(1)
D/22"
(45)
0 with prob (1 (-pp)
the inner product
(k. (x, y) (I, m + (An. B) + (Az. A,)
(46)
The estimator is unbiased.
(x (x.y) >
(2, + , + -,DIA,
(47)
j=l
v((x = Σ
V(r44,01 + MA + AD1A,
(48)
j=1
V((x)))) = Σ
+ (49)
V)(
(50)
+Cov( (Coo(z,A,IJ), (ort
(51)
Convince yourself that covariance terms are O.
v((. $)) = +o,,
(52)
v({,))) = Σ
2500 + 0 + 0
(53)
j=l
2 = V([[} 11) + ([x) - (1)))
(54)
D 2
(D)
1)
(x [x]) (D/2*- - (x- - [x)1)
2 =
v((())
(55)
26
26
D/2b
D/2b
o (x xx) (D/2*- (x (=|)) w² Paj (1 Paa)) S w²
(56)
4
20

---

Note that the inequality is tight and occurs when all the values of x are exactly at the midpoint of the bin.
where w = 12/20
o St w²
w
V)(
Σ j=1
2z 20 uj
(11=|2+ +1bb1?)
(57)
16
follows that this inequality also tight.
The equation for projection
(x)
Σ iデj
(ntv) + m.0),,0))
(58)
V2((8,)) = 1
(|,|||2||||1 - (5,, v)² - 2| y11))
||y||
(59)
|||||| & 1, 1, S 1
V, 91) S
w²
nw
S
2
n
Q(b)
(60)
2
16
226
24b
Se k
2
(8, 81)
P(m) S
(61)
m
m71
we use St to show that it is tight. The tight upper bound can be represented using some S k S 2 F where F = 32 or F = 16. for whatever precision width we are using
Under same budget m mb for the original vectors.
kF nb
()(( S
(62)
F33.1 Combined
Let us consider and with norm 1. Let us consider the procedure where we first apply projections to get x and Y1, and then Quantization applied to obtain X₂ and yz. Let us assume that the bit width for Quantization is b and the projection is into
Let's apply Quantization and then projection. The resulting estimator can be written as
( = A A.) +
Σ -( == -- h()) A A,Di)) i
(63)
The estimator is unbiased. Now let look the variance w.r.t all stochastic elements.
Σ
(0s())((1) (0)
(64)
8) (z, ( 1 A Σ
(000))((()) = (70
(65)
Note that each of the term on the right side has covariance with each other since E(AB) E E(A)E(B) 0, Cov(A, B) 0 Hence.
=
21

---

V((K,)))
(,)) Σ
(0)()) - 10)
$
(66)
V)) (x,
(67)
Eg
Σ ((2 A.l + ++12 + + 1 + A + +
m (
(68)
1 "(( (10 o + + + )0
((( = Vz(o,v)+ -v(oy)) +
(69)
V)( = V2( + 13((,))) +
(170 + u + o2 o
(70)
m izj
1
w
(2(n 1)) + n 1)
w
(x7o + +3 + 22)
(71)
7T (F)
4
16
Thus.
nw
1 2
1 n(n
1) w
(xx
S
+
+
+
((n 1))
(72)
2
16
m 2
m
16
where w D/22 2/22
((x S Q(b) ( [+ ( + P(m)
(73)
effective bits per element is B =
c.cuF.
[+"--
+ P(m) ~ Q(c.)( + - + P(cp)
Ve (1) < Q(b)
1
(74)
cp
2
2
((1g)
+
(75)
225
24b
220, F
24c F
2
2
Q(cy)
+
(76)
225
24b
22
24c
P(c))
(77)
cpm
R(cgeg Rlcp, c2) = Q(cr) (1+1) + P(c))
(78)
22

---

G
Projection Details
Firstly, note that parameter sharing SSI is only inside single neuron. So, there are independent RPS instances for each neuron. Thus, the projection of the K N weight matrix is independently projecting each neuron. Consider single neuron under RPS y solution to get best z which minimizes |/me- S2 12 is nothing but solution of linear regression, i.e. (S SS w. Also, since is sparse matrix with exactly one non-zero in each row, S is diagonal matrix. The hash function defined in the paper ensures that all elements of the diagonal are non-zero. Thus, it is invertible. In fact, if you view S as mapping matrix that maps each element of w (i.e., range to some element of range K/c), /c). then the value of is just an aggregation of all those elements from that map this element in = computed via S w) and then normalized by the total number elements from w that map to this element
and w Sz. Given w the
computed via S) ). This is straightforward implement and can be done in blocked manner for the entire matrix Z. This is presented in the Algo
Algorithm 2 SS1 -project(())
Require: e e N compression factor, W E RRKN full weight matrix, BM, Bk, By: coalescing parameters.h No + (o...., 1).9: :: N3 + {+1}, cBRlK
Ensure: = argmin 2 W (x))
1: Z -Zero-Matrix K/ N)
2: =w-TILE(BB; K Bx)
3: for j [[N/ BN do
4: for l E [K///]]
5:
[:.::.]
6: for 7 [c] do
7:
a=T un [ko++ () (ko++++ 11))k
jBx BN
8:
a= a=a( (RG((BB)BB)) h(j %),
9:
T T= k, l)a
end for
11:
T
Z (AN
13: end for
end for
H Backward kernel algorithms
We implement both the forward and backward kernels with Triton [35]. The backward pass computes the compressed weight gradients and also the input gradients with respect the hash functions used in the forward pass. It includes two kernels to output the SS1 weight gradients and input gradients.
The algorithms used in the backward kernels are presented in Algo 3 and Algo
23

---

Algorithm 3 SS1-backward: weight grad
Require: c C N compression factor
Require: O R RMxx output gradient
Require: X E IR MxN, data matrix
Require: Bи. Bk, By: coalescing parameters
Require: h: 143 + {O...., Bx - 1}
Require: g N3 {+1}
Require: cBx|K
Ensure: Wg R (K//o)
w-TILE(BN. Bx)
2: for m E [[K] / Bx do
3:
for j E [
4:
w[::: = 0
5:
for i [[M] do
6:
(x (B ( mBr: (m::::m++))))))) (m+1))B]])
7:
end for
8:
m// /c
Index block in SSImatrix Offset of block in full matrix used for hashing Scaling down gradients by compression factor
9:
1 = k%cc
W w=w/e
11:
W Wy BB Wgl. 1Bx:(k+1)BBk)
hij, k [)k
g k. 1)w
12: end for
13: end for
Algorithm 4 SS1-backward: input grad
Require: c E N: compression factor
Require: O R RMxN output gradient
Require: W K//xxN SS Imtrrix
Require: BM. BK, Bx: coalescing parameters
Require: h N3 + {0, ... Bx 1}
Require: g N: > {+1}
Require: cB
Ensure: X, E IR M
1: x-TILEEBMr, Bk)
2: for E [c] do
3: for [[K] /c/ B do [[M/BM]] do
4: for i
5:
x[t,:]
6:
for j E [[N/BN]] do I MM
7:
g k. (jx: (RG
8:
end for X, (iB (k + l)BK + ((k + / 1)B
9:
end for
11: end for
end for
I Experiment settings
I.1 GPT experiment settings
We follow standard GPT2-Small implementation of monarch paper (16) from the HazyResearch group at fly repo hhtts://gihub..com/Hary Reserr/rryyeeeer//ttty.y..ll To optimize training the GPT model on our GPUs, we replaced Huggingface's transformers
'Cony ID' layers with Py Torch (34 'in.ar in the feedforward blocks, the transformation

---

remains the same. The architecture of the GPT2 models used in these experiments is detailed in All models are trained using prreissoontraining [6]] with FP16 precision and implemented using PyTorch 34 AMP. We use V100-32GB GPUs to train the models from scratch.
Table 7
Architecture
#Layers
#Heads
Dimension
GPT2 Small
12
12
768
GPT2 Medium
24
16
1024
GPT2 Large
36
20
1280
Hyperparameters: For training use the AdamW optimizer with 4, 01 82 =0.99.
<= -e 08 and trright_deaap. = 0.1 we employ a linear schedule and wramup 1 % of steps. The effective batch size is 512, which is not achievable gradient accumulation every 32 step to reach that. All models are trained for 100 epochs. The hyperparameters are adopted from the Monarch paper [16)
hardware memory; thus, we perform
Dataset: We use wikitext-103 [29] to train, evaluate, and test the model. The reported perplexity numbers are based evaluation of the test dataset. The length of the generated sequence is 1024.
L1.1 Baselines
To build SSI models, we substitute the transformer's feedforward linear layers with our SS1 layer. We use fixed block size of Block_Size_K 32, Block_Size__ = 32, and Block_Size 64 for both the forward and backward kernels across all layers during training and testing. Additionally, each SSI layer is assigned a different seed to ensure reproducibility of the hash functions used. In addition to the coalescing parameters, the vectorization parameter EC is set to 4.
SS1:
Monarch: For Monarch baseline, we convert the same layers as SS1 from the original Monarch implementation [16] and change the number of blocks to achieve different compression rates.
Lowrank: To implement the Lowrank layer, we take the linear layer matrix and parameterize into two consecutive smaller matrices (linear layers) with reduced intermediate dimensions. The intermediate dimension in the replaced layer will be:
Kir = (K, x Ns)//(K,+NN.) x
Where K, and N₂ the input and output channels of the original matrix respectively, c N is the compression factor, and Ki, is the intermediate dimension of Lowrank matrices. Afterward, like the other baselines, we swapped the linear layers of feedforward and replaced them with the Lowrank layer.
Smallmodel:
The Smallmodel baseline aims to assess if the mlp layers of feedforward blocks of Large Language Models (LLM) are overparameterized and the impact on model quality by choosing smaller matrices for those layers. To achieve this, take the same modules of the standard model and adjust the iomer_dimessiee We surprised find that the smaller version of the model had moderate accuracy degradation. We also experimented with combining the small model and SS1 by training the small model with SSI matrices for the FFN layers. We observed improved performance with the same number of parameters for "Smallmode4Ax-S1122 compared to "SmallmodelSx: The conversion process is the same as what did in SS1-conversion.
of the linear layers by a compression factor e where E N.
BlockSparse: A pruning baseline that we sought to conduct the same experiment for was pytorch block sparse" However, pytorch block sparse is constrained to fp32 precision training, and for the large models such as GPT2, it does not fit our available GPU memory space.
FlashAttention 37 suggests significant latency of the inference phase lies in applying the softmax function on attention scores, which is a memory-bound operation. Using FlashAttention kernels shifts the workload from memory-boune to compute-bound we know from the (37] that linear transformations are compute-bound because of the extensive matrix multiply operations. Considering all that, the performance contribution of SSI is in the compute-bound setting because of reducing
https://hypiioo///pppeetttoohhcp sparss
25

---

the inner dimension of the linear matrices. Thus, in GPT2 latency measurement experiments, we use the Pytorch kernel abstraction of FlashAttention, the scaled-dot-produee product-attention (SDPA). As the FlashAttention kernels are yet to be released for older GPUs such as V100, we were not able to apply them in the training phase on V100 GPUs; thus, we only replaced them in the latency measurement experiments for all the baselines above. For the latency measurement, we employ single A100-40GB GPU.
I.1.2 Quantization
To unravel the potential of SS1 in the quantization domain, we utilize uniform post-training Quantiza- tion. The method is as follows:
= max [Xa]
S
S = 2n -
X
X
3
Where is a floating point tensor, and X is its quantized version to an integer with n number of bits. S is the scale and S is the quantization level. [-] denotes rounding to the nearest integer. We have chosen the scale to be max [XX 1) suggested by (32 due to its effectiveness in mitigating the impact of large activations LLMs.
In our application, we implement the proposed method to reduce the precision of activation and weight tensors from 16 bits during the inference mode. For weight quantization, we apply the per-channel activation, meaning the scale is computed based on values of the tensor for each output channel; for activation quantization, we do per-token Quantization based on [32]. The quantization
process is dynamic in our case. The results are obtained from testing the pre-trained GPT2-standan and S$1 models that we trained.
1.2 BERT finetuning settings
We conducted experiments to show that pre-trained linear layers can projected onto SS1 layers while retaining previous knowledge. To validate this, project the encoder layers of BERT-base and BERT-large models 19 onto SSI. BERT (Bidirectional Encoder Representations from Transformers) consists of a stack of Transformer encoder layers, each containing self-attention mechanism and a feedforward neural network. In this work, we focus on two BERT model sizes: BERT-base (12 encoder layers, 768 hidden size, 12 attention heads, 10M parameters) and BERT-large (24 encoder layers, 1024 hidden size, 16 attention heads, 340M parameters). We then finetune these models on the GLUE (General Language Understanding Evaluation) benchmark [18]. Hyperparameters used during the finetuning stage are provided in Tables and TT GLUEE consists of collection of diverse natural language understanding tasks, such as textual entailment, question answering, and sentiment anal- ysis. For our experiments, we utilize the GLUE dataset provided by the Hugging Face Datasets library.
The results are presented in Tables and 9 We are able to achieve 50% compression of the encoder layers on both BERT-base and BERT-large models, with only a minimal drop in model quality across the GLUE tasks. This reduction in parameters is not achieved by uniformly compressing all layers in the encoder. Instead, we only project layers 1, 6, 8, 9, 15, 16, 17, 18, 19, 20. 21, 22, 23, 24 (14 out of 24) for BERT-large and layers 1, 7, 8, 9, 10, 11, 12 (7 out of 12) for
BERT-base 8x compression. This leads to net compression ratio of 14/8+10 0.51 for 12
BERT-large and 1 - 7/8+5 0.51 for BERT-base, approximately 50% compression for both models.
12
These specific layers are selected using the RTE (Recognizing Textual Entailment) task from GLUE as calibration data. We treat RTE as a development set to determine which layers are less sensitive to compression. Layer sensitivity is measured by the degree of performance degradation on RTE when applying SS1 compression to individual layers in the model. The layers chosen by this method are able to generalize well to all other GLUE tasks, achieving evaluation metrics that closely match those of the full-sized BERT models with linear layers.
26

---

In addition to parameter reduction, BERT models with SSI layers are able to achieve up to 1.3lx increase inference throughput. Detailed latency measurements are provided Table On the GLUE task, our BERT-large model with SSI compression attains an accuracy of 79.76 (2.6 drop compared to the full model), while our compressed BERT-base model reaches 79.9 accuracy (2.2 drop) demonstrating that our SS1 projection method can maintain strong performance with significantly reduced parameters and runtime.
Table 8: Fine-tuning results for Bert Large
Table 9: Fine-tuning results for Bert Base
BERT-L
BERT-L x SS1
BERT-L
BERT-L x SS1
#param
335M
18IM
#param
110M
66M
COLA
69
70.8
COLA
83.6
76.2
STSB
89.3
87.1
STSB
88.8
87.5
RTE
76.1
65.9
RTE
67.5
67.5
MRPC
88.5
87.1
MRPC
89.9
87.7
WNLI
56.3
56.3
WNLI
53.5
56.3
QNLI
92
88
QNLI
90.2
86.5
QQP
90
88.3
QQP
89.2
88.5
SST2
92.9
90.8
SST2
92.4
89.5
MNLI
86
81.9
MNLI
84.4
80.5
Average
82.2
79.6 + 0.203
Average
82.1
79.9 + 0.066
Table 10: Hyper parameters for Bert(SS1) Large
Table 11: Hyper parameters for Bert(SS1) Base
Task
Batch Size
Learning rate Epochs
Task
Batch Size
Learning rate
Epochs
cola
16
2.5e-05
5
cola
16
2.5e-05
5
mnli
16
Ic-05
3
mnli
16
Ic-05
3
qnli
lc-05
3
qnli
16
2.5e-05
3
sst2
32
1.5e-05
3
sst2
16
1.5e-05
3
wnli
8
2e-05
5
wnli
32
1.5e-05
5
stsb
32
1.5e-05
3
stsb
32
2.5e-05
3
rtc
8
lc-05
7
rtc
16
2.5e-05
7
mrpc
16
1.5e-05
5
mppc
32
2.5e-05
5
qqp
32
1e-05
3
16
2.5e-05
3
Table 12: Latency results for Bert Models
Latency ms (median) Model
batch
16
32
64
128
BERT-Large BERT-Large SS1 Throughput Increase for SS1
12.68755198 18.04614353
20.73288059
40.77404976
79.60927963
158.8201599
17.61041546
31.79167938
60.99251175
120.5512314
0.7030616792
1.177307863
1.282538405
1.305230386
1.317449503
1.3 Llama experiments
of the most powerful open-source Large Language Models. They are designed to be powerful and efficient models for various natural language processing tasks. In this work, we focus on the Llama3-8B model, which has 32 decoder layers, hidden size of 4096. and 32 attention heads, resulting in approximately billion parameters.
Meta's Llama family has emerged
We conduct experiments to demonstrate that the pre-trained linear layers in Llama can be directly projected onto SS1 layers without any finetuning while maintaining model performance. This is a significant finding, as it highlights the effectiveness of our SS1 compression method in preserving the knowledge captured by the pre-trained model. By avoiding the need for finetuning, our approach offers substantial computational savings and facilitates more efficient deployment of compressed models. validate our approach, we project the transformer layers of the Llama3-8B model onto SSI layers. Specifically, we use the mmeta-llama/Medt Metaa Saaaa--lmaa----- model provided by
27

---

the Hugging Face Transformers library. We then evaluate the compressed model on the MMLU (Massive Multitask Language Understanding) [38] and Winogrande [39 tasks without any further
training or finetuning using Language Model Evaluation Harness 40
For calibration purposes, we utilize two small datasets: tinyMMLU and tinyWinogrande [4]] These datasets consist of 100 curated examples from the original MMLU and Winogrande datasets, respectively. By using these tiny datasets, we aim to identify the layers that are less sensitive to compression while minimizing the computational overhead of the calibration process. The results of our experiments presented in Table 9. We achieve 25% compression ratio of the decoder layers Llama3-8B without any finetuning. This compression is obtained by projecting layers 18. 19,20, 21, 22, 23, 24, 25, 26, 27 in the case of MMLU and layers 18, 19, 20, 21, 22, 23, 24, 25, 26, 30 in the case of Winogrande onto SS1 at 8x compression, resulting in a net compression ratio of approximately 0.25. The selection of layers for compression is based their sensitivity compression, as determined by the performance on the tinyMMLU and tiny Winogrande datasets. The layers chosen using the tiny calibration datasets generalize well to the full MMLU and Winogrande datasets. This observation suggests that the compressed model retains the essential knowledge captured by the pre-trained Llama model, enabling to perform competitively the complete datasets without any finetuning.
Table 9 presents the evaluation metrics of the compressed Llama model on the full MMLU and Winogrande datasets. On MMLU, our compressed model achieves an accuracy 61.26%. which is only slight decrease from the 65.05% accuracy of the original Llama3-8B model. Similarly, on Winogrande, the compressed model obtains an accuracy of 69.93%, compared to the 76.1% accuracy of the uncompressed model. These results demonstrate the effectiveness of our SS1 compression method in maintaining the performance of the Llama model while significantly reducing its parameter count. Furthermore, the compressed Llama model exhibits improved inference speed, achieving up to 1.1x increase in throughput compared to the original model.
The ability to compress large language models like Llama without finetuning opens up new possibilities for efficient deployment and utilization of these models in various upplications. Our SSI compression method offers a practical solution for reducing the computational and memory requirements of large models while preserving their performance downstream tasks.
Table 13:
Llama Projection Results
Model
#param
MMLU
Wingogrande
Speedup
LLAMA-3-8h
8.03B
65.05 + 4e-3
76.1 1e-2
1x
SSI
6.12B
61.26 + 4e-3
69.93 le-2
1.1x
1.4 Vision
We use the following MLPMixer models We use the repository:
https//gtthhbbcom/mmmmm//7////
MLPMixer-S
MLPMixer-M
MLPMixer-L
#layers
8
8
8
hidden-size
128
512
1024
hidden-c
512
2048
4096
hidden-s
64
256
512
Mixer-CIFAR with default settings for all runs. We do not use hyperparameter tuning for compression methods.
28

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation as long is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification. asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low images are taken in low lighting. Or speech-to-text system might be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question:
For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]

---

Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced
statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We give our main kernel implementation. (link in PCQs in appendix) The experiment section created using set of patched github repositories forked from original implementations. We will release our experimentation repository after acceptance. We detail our experiment methodology appendix
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
30

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (kttps://nips.cm cc/
Seniidde//odeSummisses
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
7 /pips.cccpublic//uu.dde issp://gggueeee/eeeeussmiiaiiaaa ssinisolicyyyy for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/eetails
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emror bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
31

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative enror rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We have added resource details to the appendix section A
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics http:p/pw...aaop.oooo/ooo//ooaaa
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: To the best of our knowledge there is no specific societal impact of our work apart from that we are contributing to faster AI.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
32

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We have provided all the information at see A
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
33

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
34


Reviews:
[{"review_id": "vvoITnpTI3", "reviewer": "Reviewer_AurA", "summary": "This paper introduces the sketch structured transform (SS1) method for fast inference. SS1 is a form of randomized parameter sharing (RPS) with connections to low-rank/dimensionality-reduction methods. Theory is used to elucidate SS1’s compatibility with quantization -- it is also compatible with other RPS methods. In empirical experiments with popular NLP and CV setups, relative to competing methods, SS1 can preserve performance better as it reduces parameter count and inference latency. SS1 is also shown to have flexibility in the stage it is applied at -- it is applicable to models without any finetuning, before finetuning, and during training.", "questions": "Line 285: this seems incorrect. The quality with SS1 seems worse in Table 2 (right).\n\nWould the benefits of SS1 over other approaches hold at larger model sizes (1B+)?\n\nLine 123: I think this equivalence only holds for points with unit length.\n\nLine 155: Can you please rewrite this sentence to better clarify why the input would have to be read multiple times?  \n\nLine 153: should this be “$N \\times K$” instead of “$K \\times N$”? The latter notation is used on this line, which is inconsistent with the output dimension appearing first in the weight matrix notation on line 139.\n\nIs equation 9 missing the inner product notation?\n\nLine 202: why is $B_KB_N$ subtracted in the indexing?\n\nLine 263: this is a figure, not a table.", "limitations": "The limitations are well articulated.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Originality: The RPS method SS1 is introduced, and it is shown to reduce parameters, FLOPs, and latency. The method is made complementary with tiled matrix multiplication via schemes to coalesce values along multiple axes. Theorems are introduced to helpfully demonstrate SS1’s compatibility with quantization and its hyperparameter flexibility.\n\nQuality: The overall approach is straightforward and intuitive, and it is tested in a range of scenarios that vary the model, dataset domain, and application timing (before or after training). It is compared against strong benchmark methods.\n\nClarity: The SS1 method is clearly explained and positioned relative to prior work. The figures, equations, and algorithms motivate design choices and illustrate implementation details. The paper is mostly well written.\n\nSignificance: This paper addresses efficient inference for matrix-multiplication-focused models (e.g., LLMs), a crucially important topic. The proposed method is applicable to pretrained models, giving it broad relevance.", "weaknesses": "The paper doesn't have any major weaknesses. I address some minor weaknesses below (see Questions). These mostly deal with improving the presentation. I would be happy to raise my score if some of them are addressed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the support of our paper. We have made writing changes to improve the manuscript and additional experiments as suggested by other reviewers. They are listed in common rebuttal. \n\nPlease find the clarifications requested below:\n\n**Line 285**: In table 2 (right), we can see that the SS1 model with 74M parameters has better (lower) perplexity than GPT-S-6x with 76M parameters. Thus SS1 models with less parameters can outperform standard model.\n\n**Would the benefits of SS1 over other approaches hold at larger model sizes (1B+)?**\nWe believe so. While we do not have the computing power to train 1B+ LLM models, our rigorous tests on different domains, model architectures, and settings encourage us to believe that the results we see are indeed general and will translate even to bigger models. \n\n**Line 123**:  The equivalence is due to the relation between inner products and norms.\nInner product => norms.  Since ||x||^2 = <x, x> norms are just inner product with itself.\nNorms => inner products. Since  2<x, y> = ||x - y ||^2 - ||x||^2 -  ||y||^2\nThus, if norms are preserved, then inner products will also be preserved and vice versa. More discussion can be found in the book[1] (Page 12, first paragraph).\n\n[1] Woodruff, D.P., 2014. Sketching as a tool for numerical linear algebra. Foundations and Trends® in Theoretical Computer Science, 10(1–2), pp.1-157.\n\n\n**Line 155**: Let us clarify the line here. \nClaim: If we do not perform K-coalescing, then we might end up requiring to load input multiple times to compute the value of the single neuron. \nArgument: Consider a neuron that is computed as <z, Sx>, where the dimensions of z and x are large enough so that they cannot be cached or stored on shared memory. In such a case, under certain hash functions that generate S, x[i] and x[i+1] ( for any i) can get multiplied with z[j] and z[k] where j and k are far apart ( In fact under the randomness of the hash function, this event is highly likely). In such a case, if we take a single pass on z, we will have to read the cache line containing x[i] and x[i+1] at least twice.\n\nTaking cue from the need for clarification along with notation and presentation issues pointed out, we have refactored our explanation in section 3 in manuscript while standardizing the notation. We believe the current version is clearer and will help the readers.\n\n**Line 153**, Equation 9. Thanks for pointing out the inconsistency in handling W. We have fixed the presentation such that we always use W as a K x N matrix and all expressions are written as vector and matrix multiplications (We have removed the inner product notation) for clarity. \n\n**Line 202** : B_K B_N is subtracted in the indexing in accordance with the hash function treatment of the ROAST[2] -- recent RPS method. It is a simple solution used to avoid overflows when reading a block of size B_K x B_N from the indexed location.\n\n[2] Desai, A., Zhou, K. and Shrivastava, A., 2023, July. Hardware-aware compression with random operation access specific tile (ROAST) hashing. In the International Conference on Machine Learning (pp. 7732-7749). PMLR.\n\n**Line 263**: fixed.\n\nWe hope to have addressed your clarifications and incorporated your suggestions to your satisfaction. We kindly ask you to consider giving us an updated score as per your indication in the review. We are happy to provide additional clarifications if needed.\n\nThanks again for the support of our paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "Df3UYMVzPd", "reviewer": "Reviewer_983k", "summary": "This paper introduces Sketch Structured Transform (SS1), a hardware-efficient structured matrix for improving the latency of linear layers in neural networks. The paper theoretically analyzes the effectiveness of SS1 in random projections, optionally combined with quantization. Experiments show favorable performance compared to alternatives such as Monarch and low-rank structures, as the compression ratio is varied.", "questions": "1. At a conceptual level, SS1 seems similar to a banded matrix with $N/c$ bands, which also have hardware efficient implementations. How does its performance compare to a banded matrix?\n2. Have you tried either tuning the learning rates for each model in the GPT-2 experiments? Alternatively, you can use the structure-aware learning rate rescaling introduced in [1] to ensure a good value is used for each model without having to tune it.\n\n[1] Qiu et al. 2024. Compute Better Spent: Replacing Dense Layers with Structured Matrices", "limitations": "The authors discussed some limitations of their work.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. Due to its use of the sketch matrix, SS1 is conceptually novel and distinct compared to other popular and performant structures such as Monarch and Low Rank, which only use batched matrix multiplies.\n2. SS1 show promising performance relative to Monarch and low rank.\n3. SS1 is designed to be hardware efficient, so that runtime overhead is low and latency improvements can be realized even at fairly small scale like GPT-2 Small.", "weaknesses": "The experiment section does not convincingly demonstrate the superiority of SS1 over Monarch and Low Rank for the following reasons:\n1. The presentation of the results makes it hard to parse how SS1 compares to alternatives **as a function of latency**, which is the metric the paper aims to optimize for. For example, in Table 1, it would be much better to plot perplexity or loss as a function of latency for each structure. It would only be fair to claim SS1 outperforms alternatives if its loss vs latency curve stays below those of others.\n2. It does not make sense to control for the model's hidden dimension and only vary the compression ratio, as is done in the experiments. For example, one can increase the compression ratio (number of blocks) in Monarch or decrease the rank in low rank **while scaling up the hidden dimension and achieve the same latency**. It's possible this is a favorable trade off for the other structures, but the experiment section does not investigate this possibility. Indeed, recent work [1] has shown Monarch with more blocks can perform better for the number same parameters or FLOPs by simultaneously scaling up the hidden dimension. **The truly meaningful comparison would be a scaling law plot of loss vs latency with one curve for each pair (structure, compression ratio)**. \n3. I strongly suspect the learning rate is not well-tuned in the GPT experiments, making it difficult to trust the results. The learning rate used was $6e-4$ for all models. This value is well-tuned for the original dense GPT-2 model, but it is suboptimal for structured models as shown in [1]: Monarch with more blocks and low rank with lower ranks would generally require higher learning rates, otherwise their performance can be significantly underestimated.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer rating our paper well on counts of soundness and contribution. We have made writing changes to improve the manuscript and additional experiments as suggested by other reviewers. They are listed in the common rebuttal.\n\n**Plots of latency vs. perplexity**: Thanks for the suggestion. We plot latency vs. perplexity for the GPT experiment in figure 3 ( page 15) and we can see that indeed SS1 curve is the best lying below other curves. We do not use such plots in the main paper since we want to show more latency results for larger models for which we do not have quality numbers in the table in the main paper. \n\n**About changing dimensions along with compression rates**\n\nThe direction of increasing hidden dimension is definitely meaningful not just for baselines such as lowrank, monarch etc. but also our proposed SS1. It makes the experimental space of models explode. Our choice of experimental setup is primarily to set up a practical and fair experimental setting to compare different alternatives. In fact, sticking to base model dimensions and evaluating various compression methods is quite standard in papers that try to fundamentally compare different methods. Some examples being [1,2,3]. \n\n[1] Tanaka, H., Kunin, D., Yamins, D.L. and Ganguli, S., 2020. Pruning neural networks without any data by iteratively conserving synaptic flow. Advances in neural information processing systems, 33, pp.6377-6389.\n\n[2]Frankle, J., Dziugaite, G.K., Roy, D.M. and Carbin, M., 2020. Pruning neural networks at initialization: Why are we missing the mark?. arXiv preprint arXiv:2009.08576.\n\n[3] Desai, A. and Shrivastava, A.. In defense of parameter sharing for model-compression. International conference on learning representations 2024\n\n**Learning rate tuning**\nYou are correct. Our learning rate is tuned for base models and used across structured models. This again is a commonplace way to compare against different methods [1,2,3]. While it is not optimal for different methods, it avoids entering into hyperparameter tuning for each method x setting. Having said that, we understand the concern. We quickly tested if learning rate tuning would change the findings. We find that learning rate tuning improves results for Monarch and SS1 and does not change the relative ordering.\n\n| Method       | learning rate | loss  | perplexity |\n|--------------|---------------|-------|------------|\n| Monarch - 8x | 6e-4          | 3.119 | 22.83      |\n|              | 9e-4          | 3.135 | 23.23      |\n|              | 2e-3          | 3.017 | 20.65      |\n|              | 8e-3          | NA    | NA         |\n| SS1-8x       | 2e-3          | 2.99  | 20.13      |\n| Lowrank-8x   | 2e-3          | 3.161 | 23.67      |\n\nThe findings do not change with learning rate tuning. \n\n**suggestion on structure aware tuning** The work cited Qui et. al. is indeed interesting work and will be useful for our future research. Thanks for pointing it out.\n\n**Banded Matrix Comparison**\nWe would love to compare against a banded matrix. However, as mentioned in our official comment, we did not find a good implementation of a banded matrix that multiplies with a full matrix. Please let us know if you have any references.  We would be happy to include comparative study in our camera ready.\nConceptually, SS1 and the banded matrix are very different. Banded matrix is motivated via “sparsity” which drops the input signals for neuron computation whereas SS1 is motivated via parameter sharing which sketches the input to reduce dimensionality. In previous literature we have seen that sketching generally is superior in quality than sparsity. [1]\n\n[1] Desai, A. and Shrivastava, A.. In defense of parameter sharing for model-compression. International conference on learning representations 2024\n\nWe hope to have addressed your clarifications and incorporated your suggestions to your satisfaction. we kindly ask you to consider giving us an updated score.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "Q4f1zOxoTk", "reviewer": "Reviewer_KgD7", "summary": "the authors propose the Sketch Structured Transform (SS1), a randomized parameter-sharing method that reduces FLOPs and latency while maintaining model quality. SS1 ties parameters within a single neuron weight and can be implemented to reduce input dimensions before multiplying with a compressed weight vector. This method is GPU-friendly and can be integrated with existing RPS methods, providing control over parameter memory and computation. SS1 can also be applied to pre-trained models using a projection function, preserving the benefits of existing models and enabling fast deployment.", "questions": "1. Can you explain section 4 in high level. What are you trying to prove and why? Specifically to the best of my understanding, you compressed\\quantize only the weights  and activation undergo reduction. So why should we care about the variance of dot product of compressed unit norm vectors. \n\n2. Same goes to theorem 2 – can you explain, in what sense you mean unbiased? Is it under permutation of the hash function? If so, I am not sure I understand why it is important if we pick one permutation and use that for the entire ( I mean the weight are tied once)", "limitations": "The paper show promising results on small scale models. For llama3-8b the results are less promising as only 1.1x speedup was achieved by applying ss1 only on some of the layers (selected based on calibration set). The limitations are partially discussed.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 1, "contribution": 3, "strengths": "1. The authors created a kernel that can work on available HW and reduce workload latency. Moreover, they open source the kernel!\n\n2. The basic idea is clear as described in section 3.1, the rest is kind of messy.", "weaknesses": "1. Very hard to follow. They abused notations many time (c is compression rate, size of super group etc.)\n\n2. The algorithms are unclear. For instance, algorithm 2. If we wish to find Z that minimize the frobenius norm between the compressed weight and the original weight we somehow need to search the different options to do it. If you are simply using brute force then just say it and push the algorithm to the appendix. Note that using only w and not checking the activation value when defining compression scheme will be sub-optimal as you might reduce the MSE of ||W-SS1(Z,I(k)||| but ||WX-SS1(Z,I(k))X|| (where x is the input to the linear layer) can be further reduced. \n\n3. Generally the paper is just poorly written and it is a shame as it seems is contains have very interesting ideas", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their support of our paper. We apologize for writing issues and assure the reviewer that we have taken due care to fix them both in the main paper and appendix. The list of changes made are presented in the common rebuttal. We clarify some specific concerns below\n\n\n**Notation overload of c** The $c$ in the text always refers to the compression factor ( a factor of c=4 means compression of 4x). In the text we have said that the supergroup contains “c” groups.  Having said that we have refactored the section 3 with standardized notations and explanations to improve the readability of the section and to avoid confusions.\n\n**Algorithm 2** We do not need to perform brute force to find the solution to equation ||WX-SS1(Z,I(k))X||. The solution of the equation is exactly shown in algorithm 2. We found a easier way to explain the projection mechanism and have updated the manuscript accordingly. We hope that alleviates the concerns regarding algorithm 2. We also explain it here,\n\nFirstly, note that parameter sharing in SS1 is only inside a single neuron. So, there are independent RPS instances for each neuron. Thus, the projection of the $K \\times N$ weight matrix is independently projecting each neuron. Consider a single neuron under RPS $y^\\top = x^\\top w$ and $w = S z$. Given $w$ , the solution to get best $z$ which minimizes $|| w - Sz||_2$ is nothing but solution of linear regression, i.e. \n$z^* = (S^\\top S)^{-1}) S^\\top w$. Also, since S is a sparse matrix with exactly one non-zero in each row, $S^\\top S$ is a diagonal matrix. The hash function defined in the paper ensures that all elements of the diagonal are non-zero. Thus, it is invertible. In fact, if you view S as a mapping matrix that \nmaps each element of $w$ (i.e., range K) to some element of $z$  ( range $ K /c$), then the value of $z^*$ is just an aggregation of all those elements from $w$ that map to this element in $z$ ( computed via $S^\\top w$)  and then normalized by the total number of elements from $w$ that map to this element in $z$ ( computed via $S^\\top S)^{-1}$ ). This is straightforward to implement and can be done in a blocked manner for the entire matrix $Z$. This is presented in the Algo 2.\n\n\n**Other presentation issues**  We have refactored section 3, added detailed comments in algorithm 1, simplified the projection explanation, and made the notation clear and consistent. We hope the reviewer finds the new version friendlier.\n\n\n**Section 4 explanation** \n\nRecent literature on RPS shows that the quality of the learned linear model under compression is directly related to the quality of inner product preservation under compression. Thus, inner product preservation is an important problem to analyze in this regard. [1]\n\nThe goal in section 4 Theorem 1 is to understand whether projection ( which is the basis for RPS) and quantization ( basis for quantization based compression) can be combined together to obtain better compression rates while preserving quality. While there is general consensus from empirical observations that compression methods can be combined, theorem 1, to our knowledge, is the first theoretical exposition on this topic which also provide guideline as how much compression to perform from individual methods.\n\nThe goal of section 4 theorem 2 is to understand the impact of the coalescing-factors have on the “inner product preservation” ( and hence quality of the learned model). \n\nThe unbiasedness and variance is under the randomness of permutations ( implemented via hash functions). It is true that we fix these permutations at the start, the randomness is still important to guarantee that we do not choose a “bad” permutation that will compromise the quality of the learned model with a high probability.\n\n[1] Desai, A. and Shrivastava, A.. In defense of parameter sharing for model-compression. International conference on learning representations 2024\n\nWe hope to have addressed your clarifications and incorporated your suggestions to your satisfaction. We are happy to provide further clarifications if needed.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "22PejKVdbn", "reviewer": "Reviewer_xFDi", "summary": "The paper introduces the Sketch Structured Transform (SS1), a novel approach designed to enhance the efficiency of tensor multiplication in deep learning models. SS1 leverages structured yet random parameter sharing to reduce computational load while maintaining the expressive power of the models. The authors provide empirical evidence demonstrating SS1's superior quality-efficiency tradeoffs compared to existing methods like Monarch and LowRank. Key findings include significant improvements in inference speed for models such as GPT2, BERT, and Llama-3-8B, even without finetuning. The combination of SS1 with quantization further enhances efficiency, and SS1 also proves effective in reducing inference latency in CPU workloads, such as the DLRM MLPerf Model.", "questions": "None", "limitations": "None", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- SS1 introduces a unique method of structured yet random parameter sharing that effectively reduces computational requirements while preserving model expressivity.\n- Extensive experiments demonstrate SS1's superior performance across a variety of models and applications, including significant improvements in inference throughput for GPT2, BERT, and Llama-3-8B.\n- SS1 can be applied to pre-trained models, allowing them to be projected onto SS1 and finetuned for faster deployment, which is highly practical for real-world applications.", "weaknesses": "- The details of GPU optimization, such as K- and N-coalescing, add complexity to the implementation, which might limit widespread adoption.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the support of our paper. We have made writing changes to improve the manuscript and additional experiments as suggested by other reviewers. They are listed in common rebuttal. Specific clarifications are answered below,\n\n**K- and N-coalescing, add complexity to the implementation**\n\nAll CUDA kernels optimize block parameters for performance. The K and N coalescing is similar to block size choosing generally required for matrix multiplication. Libraries such as CUBLAS do this optimization and cache the parameters for use, hiding the complexity of the kernels from the end user. Similarly, we do the optimizations in the code and the end user does not need to worry about these parameters. \n\nWe hope to have addressed your concerns to your satisfaction. We are happy to provide further clarifications if needed.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "16Jexr440W", "reviewer": "Reviewer_ZoDN", "summary": "The paper introduces a structured randomized parameter sharing scheme (SS1) for computational complexity reduction. A couple of coalescing techniques are suggested, where the chunk size does not affect the approximation error. The proposed method is easy to combine with the quantization method to achieve further gain. Experimental results demonstrate that SS1 improves the throughput of GPT-2.", "questions": "Major questions\n- How does Algorithm 2 guarantee the minimization of the Frobenius norm error in Equation 10? More details should be provided. \n- How are $K$- and $L$-coalescing used in the actual SS1 implementation?\n- What are the latency and accuracy of Llama-3-8b with low-rank or Monarch matrices?\n- How much is SS1 better/worse than the existing RPS methods in terms of accuracy and latency?\n\nMinor questions\n- In Equation 10, I suggest denoting the Forbenius norm by $\\|\\|\\cdot\\|\\|_F$, not $\\|\\|\\cdot\\|\\|_2$, where the latter is usually reserved for the operator 2-norm induced by the vector 2-norm.\n- Do the hyperparameters $B_K$ and $B_N$ vary from GPU to GPU? How does the inference throughput change over those parameters?\n- Typo in Line 220 “[1,2])”\n- I suppose “SSL” in Table 1 is a typo and should be SS1.", "limitations": "SS1 requires a specialized kernel to be effectively utilized on GPUs. Different types of layers (e.g., convolution layer) may require different kernel implementations.", "rating": 5, "confidence": 5, "soundness": 2, "presentation": 1, "contribution": 2, "strengths": "Overall, the paper suggests good additional features to Random Parameter Sharing (RPS).\n- The idea of reducing the computational complexity with RPS is interesting and adequately tackles a limitation of RPS.\n- The proposed method achieves actual latency improvement in some cases.\n- The paper focuses also on the GPU kernel implementation. The details about Forward and Backward Kernels are discussed well.", "weaknesses": "However, a few points should be addressed to improve the presentation. \n- Experimental results lack an important baseline--the comparison between SS1 and the existing RPS methods should be considered since SS1 is built upon RPS. \n- The latency and accuracy comparison of SS1 with other structured matrices is limited to small-sized models. Hence, the performance of SS1 compared to other methods on large models like LLM is unclear. \n- Writing quality needs to be improved, especially for the mathematical expressions and algorithms. I am willing to increase the score if the presentation of the algorithms, theorems, and proofs meet the quality of the top-tier ML conference.\n  - Some mathematical expressions are confusing, e.g., a vector and its element are sometimes denoted by the same alphabet $x$. \n  - Algorithms 1 and 2 are hard to follow. Adding comments to each important line or block might help readers understand what they are for. \n  - The abbreviations used in Table 1 are not properly introduced in the text. \n  - Proofs in Appendix contain typos in many places and should be written with a more professional nuisance.\n  - It is hard to follow how Algorithm 2 finds the solution of Equation 10. More details regarding Algorithm 2 should be followed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for the suggestions to improve the paper. Incorporating the suggestions, we have made several writing changes to the paper that are listed in the common rebuttal. We hope to have addressed your concerns and incorporated your suggestions to your satisfaction. Specific concerns are addressed below,\n\n **Comparison with RPS**:\n\nExisting RPS methods focus on reducing the parameter memory but not the FLOPs. Thus the latency of RPS methods generally is slightly worse than full model latency no matter the amount of compression. Even so, we perform RPS experiments using ROAST for matrix compression. The results are as follows and as expected. We will add these results to the final paper.\n\n|    | SS1- Quality | SS1-Latency | ROAST-Quality | ROAST-Latency |\n|----|--------------|-------------|---------------|---------------|\n| 2x | 19.45        | 154         | 19.87         | 238           |\n| 4x | 19.99        | 148         | 20.2          | 237           |\n| 8x | 20.68        | 145         | 20.94         | 222           |\n\n**the performance of SS1 compared to other methods on large models like LLM is unclear.**\n\nWhile we do not have the computing power to train 1B+ LLM models, our rigorous tests on different domains, model architectures, and settings encourage us to believe that the results we see are indeed general and will translate even to bigger models. \n\n**Writing quality improvements** \nWe apologize for the issues with our presentation. We have fixed all the issues listed here and more. The detailed summary of major changes is presented in the common rebuttal. \n\n**How does Algorithm 2 guarantee the minimization of the Frobenius norm error in Equation 10?**\nWe have improved our explanation of projection from full matrix to SS1 compressed matrix. It should help avoid a lot of confusion. We will provide a brief explanation here. ( we have also added this explanation to appendix and have moved algorithm 2 to appendix)\n\nFirstly, note that parameter sharing in SS1 is only inside a single neuron. So, there are independent RPS instances for each neuron. Thus, the projection of the $K \\times N$ weight matrix is independently projecting each neuron. Consider a single neuron under RPS $y^\\top = x^\\top w$ and $w = S z$. Given $w$ , the solution to get best $z$ which minimizes $|| w - Sz||_2$ is nothing but solution of linear regression, i.e. \n$z^* = (S^\\top S)^{-1}) S^\\top w$. Also, since S is a sparse matrix with exactly one non-zero in each row, $S^\\top S$ is a diagonal matrix. The hash function defined in the paper ensures that all elements of the diagonal are non-zero. Thus, it is invertible. In fact, if you view S as a mapping matrix that \nmaps each element of $w$ (i.e., range K) to some element of $z$  ( range $ K /c$), then the value of $z^*$ is just an aggregation of all those elements from $w$ that map to this element in $z$ ( computed via $S^\\top w$)  and then normalized by the total number of elements from $w$ that map to this element in $z$ ( computed via $S^\\top S)^{-1}$ ). This is straightforward to implement and can be done in a blocked manner for the entire matrix $Z$. This is presented in the Algo 2.\n\n **B_K and B_N parameters : implementation, do they vary with GPU, does it affect throughput**\nThe GEMM operation has three block parameters $B_M, B_K, B_N$. In the implementation of SS1, our coalescing parameters B_K and B_N behave like standard GEMM block parameters. i.e. they determine what block sizes to bring into shared memory for performing matrix multiplication. What is interesting is that algorithmically, they also determine how the hash function and SS1 recipe in general should behave, which is the novelty in SS1 that ensures that the algorithm is hardware-friendly. \nThese parameters are specific to each GPU and need GPU-specific optimization. Also, the choice of these parameters has a huge impact on throughput, as is true for GEMM operations. \n\n \n**Llama-3-8b experiments**\nWe were able to run quality experiments for lowrank. We could not find a ready implementation for monarch projection in original repository for rectangular matrices. We will add complete results in the final paper. The results are very similar across different methods. \n\n|   Model  | #param  |  MMLU | Wingogrande | Latency |\n|:--------:|:-------:|:-----:|:-----------:|:-------:|\n| Original |    8B   | 65.05 |     76.1    |  378.29 |\n|    SS1   |   6.1B  | 61.26 |    69.93    |  341.59 |\n|  Monarch |   6.2B  |   NA  |      NA     |  346.8  |\n|  LowRank |   6.1B  | 62.01 |    68.98    |  339.42 |\n\nWe want to note that this is just a proof of concept in support of the fact that SS1 can be used in the era of pretrained models as well. The main experiment still is when we train SS1 from scratch to evaluate quality vs. latency. \n\nWe hope to have addressed your clarifications and incorporated your suggestions to your satisfaction. If you are satisfied with our changes, please consider giving us an updated score.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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:
While the paper's scores are borderline, the consensus of reviewers on its good soundness and contribution of the paper is encouraging. 
 Several suggestions on improving the presentation of the paper were made, which we have incorporated in our updated manuscript. Reviewers AurA and ZoDN are willing to increase their scores if the presentation is improved. We hope they find the changes satisfactory.

Presentation Changes: (Major text changes are marked in blue in uploaded pdf)
1. We have standardized the notation used, i.e., using small-case letters for scalars, small-case boldface for vectors, and upper-case boldface for matrices throughout the paper and appendix.
2. we have removed the inner product notation and stuck to matrix notation in most cases to avoid confusion. Also, some inconsistencies w.r.t shape of W have been corrected. 
3. We have simplified the discussion on projection of matrices on SS1 and moved the algorithm to the appendix, where additional details are presented.
4. We have fixed the typos in the appendix and main text.
5. The condition in theorem 1 on norms of vectors x and y has been corrected. It is ||x|| <= 1 and ||y|| <= 1. 
6. Table 1 abbreviations are introduced in the preceding paragraph. 
7. A latency vs. perplexity plot for GPT2-S with SS1, Monarch and Lowrank is added to the appendix. ( attached as pdf to this rebuttal)

We think the proposed changes have improved our paper and thank the reviewers for their careful review and suggestions. 

We also provide additional experiments as requested by a few reviewers. 
1. SS1 vs. RPS : As expected we find that RPS does not reduce latency of the model no matter the compression. Thus SS1 has a better quality-latency tradeoff. 
2. Does learning rate tuning change the results? : We perform learning rate tuning for Monarch as suggested by the reviewer and find that it does improve the quality for monarch models. However, the same is also true for SS1 and the relative ordering of the methods does not change due to learning rate tuning. 

The additional experiments support the superiority of SS1 over alternatives.  We will add these results to the final manuscript.

Overall, we thank the reviewers for their time and careful consideration of our paper. We urge them to reconsider their scores if their concerns have been reasonably alleviated.

UPDATE: We just found that we do not have an option to upload the updated manuscript. Since some of the changes requested by the reviewers relate to presentation, and their scores are contingent on that (e.g., reviewer ZoDN), is it possible to share the updated manuscript?

Meta-review: The authors present a method for accelerating inference in ML models using sketching, called Structured Sketch Transform (SS1). The method balances the efficiency benefits of randomized parameter sharing via sketching with structured transformations that can be efficiently implemented on modern hardware. The method can be flexibly applied – it is applicable to models without any finetuning, before finetuning, and during training – and it combines with other approaches to efficient inference, e.g. quantization. The authors present theoretical analysis justifying the gains in combination with quantization, and experiments show favorable performance compared to alternatives such as Monarch and low-rank structures, as the compression ratio is varied.

Initial reviews of the paper were appreciative of the authors’ method’s generality and novelty, but most reviewers noted issues with presentation, notation, etc. that made it challenging to read the work in parts. After the rebuttal and discussion, reviewers uniformly raised their scores to weak accept, conditional on the authors making significant promised improvements to the presentation. Reviewers also highlighted an unresolved concern about lack of convincing empirical demonstration on LLMs beyond small-scale, especially relative to Monarch’s evaluation at GPT2-M scale, in light of new experiments for the rebuttal on GPT2-S. However, on balance, reviewers advocate for acceptance based on the novelty of the authors' approach and its flexibility, and the AC concurs with this judgment and recommends acceptance. The authors should incorporate all feedback from reviewers into the final revision in order to improve the presentation and readability of the work, and add the experiments that were presented during the rebuttal.
Decision: Accept (poster)