Shapeshifter: a Parameter-efficient Transformer using Factorized Reshaped Matrices
Authors: Aliakbar Panahi
Seyran Saeedi
Tom Arodz
Venue: NeurIPS 2021 Poster (2021)
Keywords: Transformer
matrix factorization
Kronecker product
compact models

Abstract: Language models employ a very large number of trainable parameters. Despite being highly overparameterized, these networks often achieve good out-of-sample test performance on the original task and easily fine-tune to related tasks. Recent observations involving, for example, intrinsic dimension of the objective landscape and  the lottery ticket hypothesis, indicate that often training actively involves only a small fraction of the parameter space. Thus, a question remains how large a parameter space needs to be in the first place –- the evidence from recent work on model compression, parameter sharing, factorized representations, and knowledge distillation increasingly shows that models can be made much smaller and still perform well. Here, we focus on factorized representations of matrices that underpin dense, embedding, and self-attention layers. We use low-rank factorized representation of a reshaped and rearranged original matrix to achieve space efficient and expressive linear layers. We prove that stacking such low-rank layers increases their expressiveness, providing theoretical understanding for their effectiveness in deep networks. In Transformer models, our approach leads to more than ten-fold reduction in the number of total trainable parameters, including embedding, attention, and feed-forward layers, with little degradation in on-task performance. The approach operates out-of-the-box,  replacing each parameter matrix with its compact equivalent while maintaining the architecture of the network.

Shapeshifter: a Parameter-efficint Transformer using Factorized Reshaped Matrices
Aliakbar Panahi 2,2
Seyran Saeedi 13,+
Tom Arodz
Department of Computer Science, Virginia Commonwealth University, Richmond, VA
2 C3 AI, Redwood City, CA
3 Dept. of Electrical and Computer Engineering, University California, Santa Barbara, CA
ali www.laaaaahn....
seyranfucsb.edd tarodz@vcu.edi
Abstract
Language models employ a very large number of trainable parameters. Despite being highly overparameterized, these networks often achieve good out-of-sample test performance on the original task and easily fine-tune to related tasks. Recent observations involving, for example, intrinsic dimension of the objective landscape and the lottery ticket hypothesis, indicate that often training actively involves only small fraction of the parameter space. Thus, a question remains how large parameter space needs to be in the first place - the evidence from recent work on model compression, parameter sharing. factorized representations, and knowledge distillation increasingly shows that models can made much smaller and still per- form well. Here, foeus factorized representations of matrices that underpin dense, embedding, and self-attention layers. We use low-rank factorized represen- tation of reshaped and rearranged original matrix to achieve space efficient and expressive linear layers. We prove that stacking such low-rank layers increases their expressiveness, providing theoretical understanding for their effectiveness in deep networks. In Transformer models, our approach leads to more than ten- fold reduction in the number of total trainable parameters, including embedding, attention, and feed-forwar layers, with little degradation in on-task performance. The approach operates
replacing each parameter matrix with its compact equivalent while maintaining the architecture of the network.
Introduction
Natural language models involve large number of parameters. A single encoder-decoder Transformer [ in its base variant has about 44 million parameters, not counting the word embedding matrix, which adds another 10 million more, depending the chosen vocabulary or tokenization scheme. Base variant encoder-only BERT [2], including the embedding, has about 108 million parameters. GPT-3 3 has about 175 billion parameters, and the largest of the Switch Transformer [ models has 1.5 trillion. This explosion the model size has led to increased interest in approaches for reducing the number of parameters in the model.
Models with digh-dimensional parameter space have much lower intrinsic dimension (5) that is, training trajectory can be successfully restricted to random, smaller-dimensional subspace, even
Work performed while at Virginia Commonwealth University.
Corresponding author.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

though training small- parammetrr architecture is often less successful. These observations have been recently extended to the fine-tuning trajectories of language models [6. Lottery ticket hypothesis 78, recently demonstrated to hold also for language model fine-tuning (9 10, shows that smaller subnetworks can be selected from a large model, re-trained in isolation, and perform as well as the large model; what those subnetworks are is not known a prior, in absence of the trained large model, though. Some approaches for reducing model size build on this observation to train a smaller model based on existing large model, for example 66 million parameter DistillBERT ( student has been distilled from 108 million parameter BERT-base [2] teacher with little loss in quality. Alternatively, distillation has been used, for example in the context of machine translation, to increase the quality of the models while maintaining their size [12] Other approaches train a reduced- parameter reduced-parameter model de novo, without relying Degh [4] uses an alternative parameterization of the multi-headed self-attention based on group linear transform to reduce 62 million parameter Transformer to 22 million.
already trained large model. For example,
One simple way to reduce model size involves factorized matrix representations. ALBERT L5
employs rank r decomposition of a d X Docbab embedding matrix storing d-dimensional embedding vectors for each of the Reocad tokens by using a stack of two linear layers, x r on top of r X Nyocab. Similar low-rank decomposition is also used implicitly in the multi-headed self-attention in the generic Transformer []] with hidden dimension d and /eadd self-attention heads. In each Transformer head, d/ a/nheads-- rrank factorized representation involving d x d/Riheds key (K) and query (Q) matrices are used, with the pairwise self-attention scores for sequence x calculated using x" K"TQx, instead of x x x involving a full general attention d x d trainable matrix W originally considered in trainable-attention encoder-decooder LSTM models [6). In both cases, the models are trained from random initialization of the factorized parameter space, instead of attempting to find the lowest-error factorized representation of an already trained original model.
We explore here a Transformer model that uses an alternative way to decompose a matrix into two smaller matrices. Instead of standard low-rank factorization as above, it involves reshaping and reordering matrix dimensions prior to the decomposition, and is equivalent to sum of Kronecker products with an efficient implementation. The compact model based on the smaller matrices is trained de novo, and matrices in the compact model are not aimed to be approximations of the matrices in the original model. For non-square model matrices, the approach allows for increased reduction in parameters for the same decomposition rank. For square matrices, the benefits come from increased expressiveness of the decomposition for the same rank, allowing for reducing the rank needed to preserve model accuracy, and thus reducing the model size. Our main contribution is proving that stacking multiple linear layers decomposed this way increases the expressiveness of the network, unlike stacking multiple low-rank layers factorized in the standard way, which can only map into a subspace of dimensionality equal to the rank. Empirically, we show that the decomposition can reduce the size of a simple encoder- decoddr Transformer to as little as million parameters, including 2 million for the model and 2 million for the embeddings. The technique can be employed automatically to any matrix, including embedding, dense, attention, and output layers. without requiring any modification of the model architecture.
2
Related Work
The two approaches most closely related ours are word2ket embeddings [17] and parameterized hypercomplex multiplication (PHM) linear layers [18]. Word2ket represents input embedding matrix in language models via sum of Kronecker products, each involving two smaller matrices. It achieves above 100-fold reduction in the number of trainable embedding parameters; however, their approach relies on lazy tensors to efficiently extract embeddings for limited number of words in the input sequence, and does not extend to output embedding matrix or other model matrices that perform general linear transformations of their input vectors. PHM linear layers [T8] arise from generalizing hypercomplex number layers [99 to arbitrary dimensionality r. with the arithmetic over the numbers learned during training. For given dimensionality т. the arithmetic takes form of sum of r Kronecker products. Irrespective of the original matrix size X m, each Kronecker product involves a small r X r matrix and larger n/r x m/r matrix, which together have n3 + wm/rr trainable parameters. For used in practice, the second term dominates, resulting in r-fold reduction in size. PHM layers with r as large as 16 have been demonstrated to be effective, leading to a reduction of a 44 million parameter Transformer to a 2.9 million parameter PHM- Traa--orooremer These numbers do

---

not include the embedding matrix for token embeddings which is not reduced in size by the PHM approach; and which for example for 32, 000 BPE tokens requires about 16 million parameters.
Both of the Kronecker- based compact language model approaches [1 18 as well as Kronecker- based convolutional (00 and recurrent networks (2T), demonstrate that of Kronecker products leads to very compact representations. Here, we advance theoretical understanding of why this low-rank representation has advantages in terms of expressivity compared a standard matrix factorization with the same rank. We also provide a more efficient, more general Kronecker- based representation. Unlike word2ket, it can be used in linear transformations anywhere in the model, an unlike PHM it also applies to embedding matrices. To represent an n X m matrix, our approach requires 2r / /mn instead of ,3 + nm/r parameters required by PHM. For example, for 16, the highest used by PHM, for a Transformer with hidden dimension of 512, each 512 x 2048 matrix in the self-attention head would be reduced from million parameters to 69,632 parameters by PHM, but to 16,384 by our approach.
Kronecker product of two matrices is concrete- representation of a finite-dimensional linear operator defined by tensor product of two underlying linear operators. Thus, Kronecker-product based representations, including PHM layers and ours, can be seen as special case of a more general representations. Kronecker-based representation unfolds
family of higher-order censor-product-beee a n m matrix from two smaller matrices, n1 X my and n2 X m22, with m mymg and n n2 In rensor-based representations, this is generalized to m [[ m, and n = ]= n2 for some tensor order o, leading to unfolding the n X m matrix from an o-way tensor that is then decomposed using low rank leading to reduction in parameters. For example, the tensor-train representation [22] represents a matrix using a series of core tensors with matching ranks. Tensor decomposition has been used successfully in convolutional networks 23 24 and recurrent networks (25.. the context of language models, tensor-train representation has been used to construct tensorised embeddings (26), which use order-three tensor representation to obtain 60-fold reduction in embedding in sequence- to oo-sequence Transformer, and also use order-six tensors to achieve almost 400-fold reduction in an LSTM model for sentiment analysis. Similarly, word2ket 17 uses order-four tensor representation to achieve more than 90,000-fold reduction in the embedding size for guestion-answering LSTTM model. Beyond embeddings, Tensorized Transformer (27) uses block-term tensor decomposition combination of CP and Tucker decompositions to reduce the multi-headed sell-attention layer with Rheads by a factor 1 L/Theads. leaving other layers intact; this allowed for reducing a 52M Transformer down to 21M trainable parameters, with little drop in BLEU scores on WMT' 16 En-De translation task compared to original Transformer. So far, none of the Kronecker- or tensor tensor-product- based approaches have been applied comprehensively to all components of Transformer model embeddings, attention, and feed-forward layers.
3 Limitations of Factorized Matrices in Deep Networks
A simple approach for reducing the size and complexity of a model involves replacing each linear transformation
matrix W with its factorized, low-rank representation involving A and an r x m matrix B, with the rank r < m, n. During training and inference, the product AB used instead of W, essentially replacing W with a two linear layers, A stacked on B. In this way, the number of parameters reduces from nm needed to represent W to r(n + m) needed to represent A and B.
matrix
One potential approach to use the factorized representation is to take an already trained model, and factorize each matrix W, into its low-rank approximation W, = Ay B, using a method such as SVD. However, analyzing an idealized deep model with linear activations shows that errors from the layers I|W,- - W,ll- Instead, a typical approach, used also here, is to
add up 28 III, W II, train a model de novo in its factorized form, using randomly initialized matrices A, and Bj. without attempting to approximate individual linear transformations of the non-factorized model.
Representing an n x m matrix W as low-rank product AB limits the linear transformation the output is constrained to be a www-dimeniional subspace of R". Stacking rank-r factorized linear transformations into an idealized deep network with linear activations does not improve the expressiveness, the dimensionality of the space of possible outputs is still constrained by the smallest of the decomposed layers rank. While this may have regularizing effect for medium values of the rank, it may prevent from using very small ranks and thus from creating compact models.
3

---

4 Stacked Kronecker Product-based Representations
For n m, the standard factorized (n x r) (r X m) + n x m representation is optimal among pairwise-pren cesss--rodutt-bssee representations in the sense that all elements of a column of A are multiplied with each element of row of B. For non-square matrices, for example matrix A is smaller than B, a more efficient all all-pairs product representation can be made by increasing the size of A and decreasing the size of B.
In Shapeshifter, instead of the standard (n x r) (r x m) + x m factorized representation, we rearrange the mn parameters of the original matrix W into ymn vmn matrix W", and then use a factorized representation of W" as a vmn x r matrix A and an r x ymn matrix B:
(Vmm r) (r Vmm)
multiply
num X VTm
reshape
VT X
V
m x V X vm
transpose
Vn X VT vm x vm
reshape
12 X
This representation uses 2r /mm parameters instead of nm..
We apply this representation to all matrices in attention and feed-forward layers in all multi-head attention blocks, and to the embedding matrices. For non-square matrices, the representation results in parameter saving compared to standard factorization with the same rank r. For square matrices, no parameter saving is achieved. However, as we show below, the way the matrix is decomposed allows for increased expressive power.
For r = 1, the n X m matrix W arises from taking products of each element from Vnm x matrix A with each element from 1 X vrm matrix B. known to be equivalent (2] to a Kronecker product A @ B involving v x VI matrices A, B resulting from reshaping the single-column and single-row matrices, respectively. Beyond r == the representation is equivalent to representing W as sum of r Kronecker products, W = Eド=ı Aj @ By. Compared to the equivalent sum of Kronecker- productss representation using the matrix factorization representation avoids the explicit summation of terms. In current libraries, results in a simpler implementation involving only matrix multiplication, reshaping and transposing, and is more efficient compared to performing individual Kronecker products followed by an explicit summation along the rank dimension.
4.1 Expressiveness of stacked Kronecker-product Layers
Certain types of matrices can easily be expressed as a sum of Kronecker products, but not in a r-rank factorized matrix form. For example, identity mapping on RD does not admit low-rank factorization, but can be decomposed as a single Kronecker product of two smaller identity matrices. More broadly, the output of sum of Kronecker products layer is not limited to r-dimensional subspace; Kronecker product of two orthogonal matrices is an orthogonal matrix [30], thus even a single A @ B term can model isomorphisms R" R.. The converse not true, most matrices require Kronecker representation with a high rank, and the question of approximating various types of matrices with a sum of Kronecker products has received ample attention B1 32 30 33
Here, we focus on a different question how does the expressive power of a stack of layers, each involving sum of Kronecker products instead of generie linear transformation, grow with the network depth. We analyze an idealized network formed by a stack of Kronecker layers with linear activations. Given high-enough rank, single layer is enough to represent any matrix. We first analyze what the depth needs to be if rank is restricted to two, and then investigate how quickly the depth can be reduced as the rank increases.
Below, we use the following notation. Support supp(z) of vector x a set of indices at which x is not null. We use [n] {1, ...,, n1.. (1). I is identity matrix. 1 is matrix with unity at row j and column & and null elsewhere; 1 is a shorthand for 1st- To avoid ambiguity, we use square brackets for individual entries of matrix
vector, thus A[j. :] represents j-th row of matrix A, while A, represents j-th matrix out of a series, as used above. For index set Z of cardinality l and a square matrix A, by A A[Z] we represent a l submatrix of A obtained by taking the intersection of columns and rows from set Z.
We first define variant matrices, which will be a tool in exploring stacked layers.
If' /mn is not integer, round it up, and use submatrix as representation of W.

---

Definition 1 (k-variant matrix). For an nt x nt o matrix U and an index set Z C [n], by writing U we indicate that both U and its inverse U act as identity on all the dimensions not in set 7. That is, for each x E IR", supp(Ux= - x) C 7 and supp(U' x x)) S Z. If Z has cardinality at most we call U a k-variant matrix.
The notion of k-variant matrices generalizes Givens rotation matrices 34 used for example in QR decomposition. A Givens rotation in n dimensions is any rotation that acts on plane spanned by two of the coordinate axes it is thus 2-variant. QR decomposition can be represented as product of 2-variant matrices. We will then show that 2-variant matrices, or more broadly, k-variant matrices for k S Vn. can be represented using sum of Kronecker products.
be used to show that each matrix
Theorem 2 (Decomposition into layers involving Kronecker products). Let m2 for some E N. Any orthogonal n x n matrix U can be represented as
L
U
Aij 00 Bij.
Elj=1
where Aij and Big are vn x vn matrices, and L O (n²²).
Proof. QR decomposition using Givens matrices will result in Q being product of up to nınn - 1)/2 Givens rotations, which are 2-variant, and R upper triangular matrix which for orthogonal matrices a diagonal matrix with +1 and - elements. The sign of any pair of -1 diagonal entries can be negated by 2-variant matrix; most n/2 such matrices are needed convert the diagonal into identity, since there are at most n negative elements in R. In total, up to /2 2-variant matrices needed represent any given orthogonal matrix.
Next, we set to show that any 2-variant matrix can be represented as a product of at most three matrices, each of the form A₁ @ B1 + A2 @ B2, using m m matrices.
Let (k.o) be an arbitrary 2-variant orthogonal m² x m² matrix for arbitrary k q E [m²]. That is, y = U (h:9) x acts only on x [A]]] and æ[q] to produce y/kt and ylul. for / k. we have y|4 = z((].
Consider two vectors, A, FB E mh Kronecker product of x 6 ÆB of these two vectors is vector x E R with entries defined through products
<*k] = x [A] <<q| = A [pp
for k = (n 1 1)m + X
for q (πt - 1)m +
for K, A, I., P [m].
For example, let (A.o) be a variant matrix action on X, p. then 1, @ B(A.e) is a acting on dimensions = (v - 1)m + and = (v - 1)m + p in the same way as B(p,p) acts on dimensions and p, and producing either identity null elsewhere, as shown below:
matrix A acts on vectors x = A Grg as (A&B)z
0
a
a
B
1
1
B
&
3
a
First, consider k q such that x π v for some v [m]. Define a 2-vaiiant (A,p) such that B[( = Uik,, qHl, that is, B acts on X, p in the same way as U acts on k, 9. We then have
(kka) 1, & Bldel (1 - 1,) @ I.
symmetric construction holds if v. both cases, we can represent a 2-variant orthogonal matrix by A₁ & B, + A₂ & B2.
5

---

The general case of (k-a) for K & and À * can be addressed by converting it into the case via transforming into æ. applying the special case, and then transforming back into R.
We show that an orthogonal matrix V of the form V = CC D + C² 69 D' exists such that
& B(7 + (1) 1 @ Ulhaa = VT (Lx
where BH p}] Ulk, oH}, the X, columns/rows of B are formed by taking submatrix of U defined by columns/rows k, q.
To construct V. set C' = PR-+.. a permutation matrix that moves k to ग, and D - 1x- Also set C" I and D' I Lx. Columns of C & and C' D are linearly independent, and each of the two matrices is orthogonal, thus V is orthogonal.
Consider AA & B. then have
x' ='= Vv Z @ 1λTB I (1-))1))
The first term will use the permutation to move IA [r] to position where it will be multiplied by an (A], and placed at x' o'(k'] for k'' (ι - 1) A; all other entries x xa(l) will be rearranged as well by the permutation. For m = 3. X 2,
2, the transformation that moves 1,
xik- = 2] = z((x 1)m + A] = ay 33 into x x'[k' = 5] = x x'[(T - 1)m + >] and thus brings into
position ready for the special case, is illustrated below
TO 1
07
0
07
[31
T02
0
022
89
000
1
0
82
=
01
X
82
=
0
0
1
0
0
33
0
= [0
01232
01
0
0r 0j"
The second term will preserve xAH-B]]]]] for all entries of an except X; this includes p. since in the general case À * p. The k, entries of x will be now at k', q entries of x', and applying 1, @ ( + (I - 1,) & I on x' will be equivalent to acting on positions k, q of x. The inverse orthogonal transformation VT will restore the transformed values at positions K, q, well all other entries x 111120
(| sA), back to their original positions. The transformation VT is of the same form as V. except using P-tz instead of PR-AAr since the other matrices involved in V are diagonal with unit-magnitude entries. In summary, in the general case, m. x m matrices Aij and Bij exist such that any 2- 2-rritttt orthogonal matrix can be represented as II Ej=1 Aij Bgg.
Together, any orthogonal n. m² dimensional matrix U be decomposed into U - 3n2/2 E3 & Bij.
Corollary 3. Any linear x matrix W can be represented as a product of a finite sequence of sums of two Kronecker products of [n] [m]] matrices followed by selecting an n X m submatrix.
Proof. The result immediately follows by considering an orthogonal matrix with dimension max m x [2), observing that an arbitrary, possibly rank-deficient diagonal matrix D can be decomposed as a product of series of matrices of the form 1 6 (Díj, -))),, + (T-1,)) one per diagonal entry D[j, k.., which allows for producing arbitrary rank-deficient square matrices. from which non-square matrices can be selected.
The above theorem shows that stacking layers represented compactly as (Vrm x r)) (r x vnr) for 2 increases the expressive power of the network. In the idealized case with linear activation function, adding such layers allows the network to eventually produce arbitrary RT + IR lincar transformations, unlike stacking standard factorized layers (n r) (r m), which always maps into an r-dimensional subspace irrespective of the number of layers.
With rank 2, we may need many as 3n² /2 layers to represent an orthogonal n x n matrix. On the other extreme, only one layer needed if the rank is n, since arbitrary n X n matrix can be seen as concatenation of n tiles of size /n x vn. As long as we define indicator /n x vn matrices 1 and use them as tile position selectors, we can use sum Kronecker products of the selection with the corresponding tile to produce the matrix. In between these extremes, the number of layers needed to increase the expressiveness of the network to allow arbitrary transformations depends on the rank in the Shapeshifter representation in the following way.

---

Theorem 4 (Depth-rank tradeoff for deep models involving Kronecker products), Let n = m2 for some m N. and let r I m. Any orthogonal n. x n matrix U can be represented as a product of sequence of sums of two Kronecker products of m. m matrices
U- U-
Aig & Bij --
where Aig and Bij are vn vn matrices, and L 0 (n²/r).
Proof. Instead of 2-variant orthogonal matrices, use r-variant ones. Consider = 3, with Ukk4,,0 and with (is 1)m- + X, q (Nt 1)m + p. and (r 1)m + v. We now have two groups for some have special case as in Theorem
of indices, K. n, T and X, p. v. If K
U (k.q..) 1, @ B(A,pot + (7 - I.) 60;
we have similar special case if
The general case involves no equality in either of the two groups. Then, we can proceed similarly as for 2-variant general case, but need permutation matrix Px and separately permutation matrix P which allow us to define
= Vx = PA & 1 + PA-TTAA @ 1T + I 8 (7 1
1, 1 1))
Here, V is an orthogonal transformation that uses a sum of three Kronecker products as a trans- formation that maps the general case the into higher r as long as r I m, the number of diagonal entries in matrices A: we need V to a sum of r Kronecker products involving distinct dimensions of A. In summary, we need less than Ei Aij B,j to represent arbitrary r-variant orthogonal matrix. A product of two k-variant matrices is at most 2k-variant. Grouping r/2 Givens rotations or, more generally, 2-variant matrices result in at most r-variant matrix, thus need at most L O (3n² /r) layers, each involving a Kronecker product of rank at most r.
T case. The construction naturally extends
As is common in theoretical work on deep networks, the results are limited to idealized multilayer models with linear activations. However, they can provide insights into networks with nonlinearities; for example, activations such as ReLU that are linear on large part of their input will lead to piece-wise linear network, and the results above hold in a piece-wise fashion.
Experimental Results
We validated the approach on machine translation using sequence-to-sequencee models. The experi- ments were performed on a single V100 (longest run: 6 days) or A100 GPU (Iongest run: 1 day). Time overhead experiments were performed on dedicated workstation with a single NVIDIA RTX 3090 GPU. As the basis for Shapeshifter, we used Transformer (I, with embedding and encoder/decoder layers replaced with compact representations. in the multi-head self-attention blocks. For embedding matrices, which are much larger and can be reduced more effectively, we used higher rank, while aiming keep the total size of factorized embeddings below the total size of the rest of the factorized encoder/decoder. The time overhead
Shapeshifter. we used small rank for all matrices
Table Overhead introduced by Shapeshifter compact representation. We compared T5-small Transformer model 35 with Shapeshifter model resulting from the T5-Small model, with rank 256 for embedding and rank 16 within the multi-headed self-attention blocks. We measured time train 10 epochs, and time to perform translations using trained model on the full test set.
Training time [s]
Inference time [s] Shapeshifter 16/256
Dataset
Transformer
Shapeshifter 16/256
Transformer
Eo 36
16,192
18,007 (+11%)
110
124 (+13%)
Dn-En
37
2,917
3,426 (+17%)
203
219 (+8%)
7

---

Ours
PHM
Transformer
Ours
De-En
DeLighT
Transformer
BLEU score
En-Fr
Ours
DeLighT Transformer
Transformer
Ours
Degggh
De-En
En-Ro
Transformer
Ours
PHM
En-Ro
Ours
DeLighTT1
Transformer
En-De
params (in min)
params (in mln)
Comparison of the proposed Shapeshifter compact representation applied to Transformer with two alternative approaches for compact Transformers: PHM layers [8] and DeLighTT [14]. See Tables 2 and for details.
Figure 1:
(see Table D introduced by the representation is modest, up to 17% increase in running time during training, and up to 13% during predictions with a trained model.
We compared our approach to two recently proposed approaches for reducing model size: DeLighT 14 and PHM Layers [8]. DeLighT uses separate vocabulary for the source language encoder embeddings, and different vocabulary for the target language decoder embedding and output layer. PHM Layers, like its predecessor Quaternion Transformer [9), uses the same Byte-Pair Encoding 38 in both encoder and decoder. To facilitate comparisons, we followed both approaches and trained two Shapeshifter variants, one with separate embeddings and one with single embedding.
5.1
Comparison with PHM Layers
In comparisons with PHM layers [8], we used T5-small Transformer 35 which shares a single embedding matrix in both the encoder and the decoder. We use Huggingface Transformers [40] for PyTorch [4]] implementation. We evaluate the approach on IWLSLT' 14 German-to-Engliss (De-En)
37 and WMT 18 English-to-Romante (En-Ro) [36] datasets. For the first dataset we use learning
Table 2: Results of comparisons with PHM layers [18. Model performance measured using
BLEU [39 on dev set. We also list total number model parameters, its breakdown into number of parameters in the dncoder multi-headed self self-attention and feed-forward layers, and separately in the all the embedding in the model. We also express the parameter reduction as percentage and fold change compared to the size of the corresponding Transformer model. Shapeshifter Tencoder
I "embedding denotes encoder/decoder and embedding ranks.
Model
Total
Enc./Dec.
Emb.
Pet.
Fold
BLEU
WMT' 18 English-to- -omo------omman (En-Ro) dataset
36
Transformer [ from [8]
44M
22.79
PHM-Tm 16 [18
2.9M
19.63
*Transformer I
60.5M
44M
16.5M
100.0
24.30
PHMM-m 16 [18]
19.6M
3.2M
16.5M
32.4
3.08
22.38
Shapeshifter 24/256
5.2M
3.1M
2.1M
8.62
11.59
22,56
Shapeshifter 16/256
4.2M
2.1M
2.1M
6.95
14.39
22.12
IWSLT'14 Lerrman-too-Engeee (De-En) dataset
[37
Transformer 1 from [18]
44M
36.68
PHM-Tm n 16 [8
2.9M
33.89
*Transformer O
60.5M
44M
16.5M
100.0
36.72
*PHM-Tm n 16 18
19.6M
3.2M
16.5M
32.4
3.08
36.49
*Shapeshifter 16/256
4.2M
2.1M
2.1M
6.95
14.39
36.36
* denotes our experimental results, other results taken from referenced paper. denotes the information was not available in the referenced paper.

---

rate 2e-3 with batch size of 128, while for the larger En-Ro dataset we use 3e-3 with batch size of 192. We used LAMB optimizer [42 with inverse square root scheduler, dropout 0.1, no weight decay, and 0.1 label-smoothed cross entropy loss.
To facilitate comparison of results with PHM Layers approach under the same conditions, reimplemented the approach and applied it to T5-Small Transformer that we used as basis for experiments with our method. The small increase in size the PHM Transformer observed in our re-implementation of PHM layers compared to the parameter size provided in the literature [[8] (3.2M 2.9M parameters) results from the fact that the underlying T5 Transformer that we build on uses three separate duid dhid matrices for self-attention query, key, and value weights for all heads, while the Transformer used [18] stores all three as a single. concatenated d 3dhid matrix.
The results presented Table 2 and the left panel of Figure ?? indicate that while our full models four times smaller than full PHM models, they offer very similar on-task performance. The parameter reduction comes not only from factorized embeddings in Shapeshifter, but also from matrices inside the attention blocks in encoder/decoder: both Shapeshifter 16 256 and PHM n 16 use sum of 16 Kronecker products to represent a matrix, yet PHM results in a 1.5 times larger encoder/decoder when applied to the same exact base architecture.
5.2 Comparison with Deliggh
Following DeLighT 14 we used Transformer models as implemented in fairseq [45] We bench-
marked the Shapeshifter models four datasets: IWSLT 14 German-to-English (De-En) 33). WMT' 16 English-to-Romaniae WMT' English-to-Frenchh (En-Fr) 44 The specific Transformer architecture used by DeLighT,
(En-Ro)
[43) WMT English-to-Geree Gerermannn (En-De) 44 and
and also in our experiments, varies depending on the dataset. For the WMT' 14 En-De we used 12 transformers blocks with 4 attention heads, 512 the embedding dimension and 1024 for the fan out fully-connected layer. For the other three datasets we used 12 transformers blocks with attention heads, 512 as the embedding dimension and 2048 for the fan out fully-connected layer. For the training setup we have used Adam optimizer, learning rate of 5e-4, inverse square root scheduler with 15K warmup steps, dropout 0.3, weight decay of le-4, and 0.1 label-smoothed cross entropy loss.
Compared to the smallest of the DeLighT models available for each dataset, as summarized in Table 3 and in the right panel of Figure ??, the Shapeshifter models have between 1.5 and times
Table Results of comparisons with DeLighT 14). Same format as in Table 2
Model
Total
Enc./Dec.
Emb.
Pct.
Fold
BLEU
IWSLT' 14 German-te tee--tt-----ee to-English (De-En) dataset 37
Transformer [1. from 14
42M
100.0
34.3
DeLighT [1]
14M
35.5
2.82
33.8
*
"Transformer *Shapeshifter 64/256
39.5M
31.5M
7.9M
100.0
35.43
9.3M
7.2M
2.
23.6
4.24
35,43
WMT' English-to
Monglishtt--Romanian Romanian (En-Ro) dataset
[3
Transformer [T] from [14
62.0M
44.
17.9M
100.0
34.3
DeLighT [14]
22.0M
35.5
2.82
34.3
*Transformer
62.0M
44. 44.1M
17.9M
100.0
33.89
Shapeshifter 64/256
10.4M
8.2M
2.2M
16.8
34.55
Shapeshifter 24/256
5.4M
3.1M
2.2M
8.6
1..63
32.48
WMT' 14 English-to-Germae (En-De) dataset (44)
Transformer [1. from [14
62.0M
44.1M
17.9M
100.0
27.3
DeLighT [14]
37M
59.6
1.68
27.6
"Shapsshffter 64/256
10.7M
8.2M
2.5M
17.2
5.7
26.6
WMT' 14 Beaiish-to-FFenede (En-Fr) dataset
44
Transformer [1] from 14
62.0M
44.1M
17.9M
100.0
39.2
DeLighT [14]
37.0M
59.6
1.68
39.6
"Shapeshifter 64/256
10.7M
8.2M
2.5M
17.3
5.78
40.78

---

fewer parameters, yet offer similar quality; Shapeshifter achieves higher score than DeLighT on two datasets, and lower score on two other datasets.
5.3 Comparison with Standard Low-rank Factorization
To validate experimentally the theoretical results from Section 4.1 concerning the increased expres- siveness of the factorization type used Shapeshifter compared to standard n r, low-rank factorization, we trained models factorized this way using the same encoder/decoder rank of 16, and the same embedding rank of 256 as Shapeshifter. To test only the stack of Transformer layers. we also trained models that do not factorize the embedding matrix. We used one small dataset, Co-mannto-Englshhe and one large, WMT 18 Boglish-to-Romanee show that the size of the model is reduced substantially in the Kronecker- based approach compared to standard low-rank representation. The reduction comes predominantly from the embedding, which involve non-square matrices. Despite more than two-times larger number of parameters, standard low-rank representation shows much higher loss on the training set, with no significant difference in terms of generalization outside of the training set, confirming that the difference between the two representations results from increased expressiveness a stack of low-rank foonecker-producee layers. Similar behavior can be observed when the comparison involves models where the embedding matrices are not factorized.
IWSLT
The results in Table
Table 4: Comparison with standard low-rank representation. Factorized models are trained de novo small (IWSLT' 14 De-En) and large (WMT' 18 En-Ro) dataset.
Dataset
Factorization type
Total
Enc/Dec
Emb.
BLEU
Train Loss
Dev Loss
De-En
Shapeshifter 16 256
4.2M
2.1M
2.1M
36.36
2.59
2.67
De-En
Low-rank 16 256
10.6M
2.2M
8.4M
26,68
2.97
2.99
De-En
Shapeshifter 16 -
18.6M
2.1M
16.5M
35.85
2.66
2.73
De-En
Low-rank 16 /-
18.7M
2.2M
16.5M
32.01
2.86
2.90
En-Ro
Shapeshifter 16 256
4.2M
2.1M
2.1M
22.12
2.19
3.09
En-Ro
Low-rank 16 256
10.6M
2.2M
8.4M
17.47
2.32
3.37
En-Ro
Shapeshifter 16
18.6M
2.1M
16.5M
21.93
2.16
3.09
En-Ro
Low-rank /6/-
18.7M
2.2M
16.5M
19.34
2.33
3.34
Conclusion
Our theoretical and experimental results show that deep models composed of stacked low-rank Kronecker- poonecker-product-beee product-based representations are more expressive, yet smaller, than equivalent models that use standard low-rank factorized matrix representations. These observations help solve puzzle of how recent methods such word2ket [17 and PHM layers [18] achieve their impressive parameter reduction rates for embeddings and for encoder/decoder layers, respectively. despite training models de novo, without the help of an existing large model serving blueprint for compression or pruning, or as teacher for knowledge distillation. Building on these results, we provide a comprehensive Shapeshifter[ approach that works both for the embeddings and for the encoder/decoder, using more effective way to exploit Kronecker products for factorized representations. Experimental comparisons with state-of-the-art model reduction approaches, not only PHM but also recently proposed Del DelhgghT [14, on a range of machine translation problems, show that the approach offers similar translation quality with much fewer parameters.
Funding Disclosure and Competing Interests
This work was partially funded by NSF grant IIS- IS-1453658 to T.A. The authors have competing interests.
'Code available at: http://hhhh..eeeearrr/a/aaaaaaaa
10

---

References
[1] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Proceedings of the 31st International Conference on Neural Information Processing Systems, pages 6000-6010, 2017.
[2] Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: pre-training of deep bidirectional transformers for language understanding. In Jill Burstein, Christy Doran, and Thamar Solorio, editors, Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, NAACL-ILLT 2019, pages 4171-4186, 2019.
[3] Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel Ziegler, Jeffrey Wu, Clemens Winter, Chris Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language models are few-shot learners. In Advances Neural Information Processing Systems, volume 33, pages 1877-1901, 2020.
[4] William Fedus, Barret Zoph, and Noam Shazeer. Switch Transformers: Scaling to trillion parameter models with simple and efficient sparsity. arXiv preprint arXiv:2101.03961 2021.
[5] Chunyuan Li, Heerad Farkhoor, Rosanne Liu, and Jason Yosinski. Measuring the intrinsic dimension of objective landscapes. In International Conference on Learning Representations, 2018.
[6] Armen Aghajanyan, Sonal Gupta, and Luke Zettlemoyer. Intrinsic dimensionality explains the effectiveness of language model fine-tuning. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the I Ith International Joint Conference on Natural Language Processing (Volume 1: Long Papers), pages 7319-7311 7328, 2021.
[7] Jonathan Frankle and Michael Carbin. The lottery ticket hypothesis: Finding sparse, trainable neural networks. In International Conference on Learning Representations, 2018.
[8] 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.
[9] Tianlong Chen, Jonathan Frankle, Shiyu Chang, Sijia Liu, Yang Zhang, Zhangyang Wang, and Michael Carbin. The lottery ticket hypothesis for pre-trained BERT networks. In Advances in Neural Information Processing Systems, 2020.
[10] Sai Prasanna, Anna Rogers, and Anna Rumshisky. When BERT plays the lottery, all tickets are winning. In Proceedings of the 2020 Conference on Empirical Methods Natural Language Processing (EMNLP), pages 3208-3229, 2020.
[11] Victor Sanh, Lysandre Debut, Julien Chaumond, and Thomas Wolf. DistilBERT, a distilled version of BERT: smaller, faster, cheaper and lighter. arXiv preprint arXiv: arXiv:1910.00 1910.01 108, 2019.
[12] Bei Li, Ziyang Wang. Hui Liu, Quan Du, Tong Xiao, Chunliang Zhang, and Jingbo Zhu. Learning light- translation models from deep transformer. Proceedings of the AAAI Conference on Artificial Intelligence, 35(15): 12117-132222 2021.
[13] Fusheng Wang, Jianhao Yan, Fandong Meng, and Jie Zhou. Selective knowledge distillation for neural machine translation. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 1 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers), pages 6456-6466, 2021.
[14] Sachin Mehta, Marjan Ghazvininejad, Srinivasan Iyer, Luke Zettlemoyer, and Hannaneh Ha- jishirzi. Deh:ighT: Very deep and light-weight transformer. International Conference on Learning Representations ICLR 2021, 2020.

---

[15] Zhenzhong Lan, Mingda Chen, Sebastian Goodman, Kevin Gimpel, Piyush Sharma, and Radu Soricut. ALBERT: lite BERT for self-supervised learning of language representations. In International Conference on Learning Representations ICLR 2020,, 2019.
[16] Minh-Thang Luong, Hieu Pham, and Christopher D Manning. Effective approaches to attention- based neural machine translation. In Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing, pages 1412- 1421, 2015.
[17] Aliakbar Panahi, Seyran Saeedi, and Tom Arodz. word2ket: Space-efficient word embeddings inspired by quantum entanglement. In International Conference on Learning Representations (CLR'2020, 2019.
[18] Aston Zhang. Yi Tay, SHUAI Zhang, Alvin Chan, Anh Tuan Luu, Siu Hui, and Jie Fu. Beyond fully-connected layers with quaternions: Parameterization of hypercomplex multiplications with 1/n parameters. In International Conference on Learning Representations ICLR 2022,, 2020.
[19] Yi Tay, Aston Zhang, Anh Tuan Luu, Jinfeng Rao, Shuai Zhang, Shuohang Wang, Jie Fu, and Siu Cheung Hui. Lightweight and efficient neural natural language processing with quaternion networks. In Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 1494-1503, 2019.
[20] Shuchang Zhou, Jia-Nan Wu, Yuxin Wu, and Xinyu Zhou. Exploiting local structures with the Kronecker layer in convolutional networks. arXiv preprint arXiv: 151..09194 2015.
[21] Cijo Jose, Moustapha Cissé, and Francois Fleuret. Kronecker recurrent units. In International Conference on Machine Learning, pages 2380-2383 PMLR, 2018.
[22] Ivan V Oseledets. Tensor-train decomposition. SIAM Journal on Scientific Computing, 33(5):2295-231 2211995--37,2200 2011.
[23] Emily Denton, Wojciech Zaremba, Joan Bruna, Yann LeCun, and Rob Fergus. Exploiting linear structure within convolutional networks for efficient evaluation. In Advances in Neural Information Processing Systems, pages 1269-1277, 2014.
[24] Alexander Novikov, Dmitry Podoprikhin, Anton Osokin, and Dmitry Vetrov. Tensorizing neural networks. Advances in Neural Information Processing Systems, volume 32, 2015.
[25] Charles C Onu, Jacob E Miller, and Doina Precup. A fully tensorized recurrent neural network. arXiv preprint arXiv:2010.04196 2020.
[26] Oleksii Hrinchuk, Valentin Khrulkov, Leyla Mirvakhabova, Elena Orlova, and Ivan Oscledets. Tensorized embedding layers. In Findings of the Association for Computational Linguistics: EMNLP 2020, pages
2020.
[27] Xindian Ma, Peng Zhang, Shuai Zhang, Nan Duan, Yuexian Hou, Ming Zhou, and Dawei Song. A tensorized transformer for language modeling. Advances in Neural Information Processing Systems, 32:2232-2242, 2019.
[28] Thomas Frerix and Joan Bruna. Approximating orthogonal matrices with effective Givens factorization. In International Conference Machine Learning, pages 1993-2001. PMLR, 2019.
[29] Harold Henderson and Shayle R Searle. The vec- ooc-permutation matrix, the vec operator and Kronecker products: A review. Linear and multilinear algebra, 9(4):271-288 1981
[30] Charles F Van Loan. The ubiquitous Kronecker product. Journal of Computational and Applied Mathematics, 123(1-2):85-000, 2000.
[31] Charles F Van Loan and Nikos Pitsianis. Approximation with Kronecker products. In Linear algebra for large scale and real-time applications, pages 293-314. Springer, 1993.
[32] Julie Kamm and James Nagy. Kronecker product and SVD approximations in image restoration. Linear Algebra and its Applications, 284(1-3):177-192, 1998.
12

---

[33] Eugene Tyrtyshnikov. Kronecker- approximations for some centiion-relatdd matrices. Linear Algebra and its Applications, 379:423 437, 2004.
[34] Wallace Givens. Computation of plain unitary rotations transforming a general matrix to triangular form. Journal of the Society for Industrial and Applied Mathematics, 6(1):26-50, 1958.
[35] Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu. Exploring the limits of transfer learning with unified text-to-text transformer. Journal of Machine Learning Research, 21(140):1667, 2020.
[36] Ond Onrej Bojar, Christian Federmann, Mark Fishel, Yvette Graham, Barry Haddow, Matthias Huck, Philipp Kochn, and Christof Monz. Findings of the 2018 Conference on Machine Translation (WMT18). In Proceedings of the Third Conference on Machine Translation, volume 2, pages 272-307, 2018.
[37] Mauro Cettolo, J Niehues, Stüker, Luisa Bentivogli, and Marcello Federico. Report on the
1 1thh IWSLT evaluation campaign. IWSLT 2014. In IWSLT-Internationall Workshop on Spoken Language Processing, pages 2-17. Marcello Federico, Sebastian Stüker, François Yvon, 2014.
[38] Rico Sennrich, Barry Haddow, and Alexandra Birch. Neural machine translation of rare words with subword units. In Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics ( (Volume I: Long Papers), pages 1715-1725, 2016.
[39] Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. BLEU: a method for automatic evaluation of machine translation. In Proceedings of the 40th annual meeting of the Association for Computational Linguistics, pages 311-318, 2002.
[40] Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowiez, et al. HuggingFace's Trans- formers:
State-of-the-art natural language processing. arXiv e-prints, pages arXiv-1910, 2019.
[41] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, pegerrerformence deep learning library. Advances in Neural Information Processing Systems, 32:8026-800 8037, 2019.
[42] Yang You, Jing Li, Sashank Reddi, Jonathan Hseu, Sanjiv Kumar, Srinadh Bhojanapalli, Xiaodan Song, James Demmel, Kurt Keutzer, and Cho-Jui Hsieh. Large batch optimization for deep learning: Training BERT in 76 minutes. In International Conference on Learning Representations ICLR 2020, 2019.
[43] Ondfej Bojar, Rajen Chatterjee, Christian Federmann, Yvette Graham, Barry Haddow, Matthias Huck, Antonio Jimeno Yepes, Philipp Koehn, Varvara Logacheva, Christof Monz, Matteo Negri, Aurélie Névéol, Mariana Neves, Martin Popel, Matt Post, Raphael Rubino, Carolina Scarton, Lucia Specia, Marco Turchi, Karin Verspoor, and Marcos Zampieri. Findings of the 2016 Conference on Machine Translation. In Proceedings of the First Conference on Machine Translation:
Volume 2, Shared Task Papers, pages 131 1398, 2016.
[44] Ondrej Bojar, Christian Buck, Christian Federmann, Barry Haddow, Philipp Koehn, Johannes Leveling, Christof Monz, Pavel Pecina, Matt Post, Herve Saint-Amand, Radu Soricut, Lucia Specia, and Aleš Tamchyna. Findings of the 2014 Workshop Statistical Machine Translation. In Proceedings of the Ninth Workshop on Statistical Machine Translation, pages 12-58, 2014.
[45] Myle Ott, Sergey Edunov, Alexei Baevski, Angela Fan, Sam Gross, Nathan Ng, David Grangier, and Michael Auli. fairseq: fast, extensible toolkit for sequence modeling. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics (Demonstrations), pages 48 48-53, 2019.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See bottom of Section 4.1 for
discussion of the limitations of the theoretical study of expressivity.
(c) Did you discuss any potential negative societal impacts of your work? [No] While there is ample work discussion potential negative societal impacts of language models general, we have not been able to identify negative impacts of reducing the size of the models.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See Section
4.1.
(b) Did you include complete proofs of all theoretical results? [Yes] See Section 4.1.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main ex- perimental results (either in the supplemental material URL)? [Yes] See wwtp///arro//sappaaafff...oe
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Section
(c) Did you report error bars (c.g., with respect to the random seed after running exper- iments multiple times)? [No] Running Transformer models is expensive, only performed one run. This common practice in the field, as seen in cited references, e.g. the work use in comparisons [1)
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Section 5.
4. If you are using existing assets (e.g., code, data, models) or curating/reelasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes]] We cited the creators of PyTorch, fairseq, Huggingface Transformers, IWSLT and WMT, see Section 5.
(b) Did you mention the license of the assets? Yes] Our code refers to the licenses of the assets it relies on.
(c) Did you include any new assets either in the supplemental material or as a URL? [No] We are using only publicly available, benchmark datasets.
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [No] We are using only publicly available, benchmark datasets. (e) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [No] We are using only publicly available, benchmark datasets.
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [No] We are not using crowdsourcing nor conducting research with human subjects.
(b) Did you deseribe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [No] See above.
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [No] See above.
14


Reviews:
[{"review_id": "y5mRJDZ6ekq", "reviewer": "Reviewer_tnWM", "summary": "A sizable effort has been made in recent history to obtain the accuracy of very large language models at a fraction of the parameter of the large models. Broadly these methods fall into various categories like model compression, factorized representation, distillation etc. This paper underlines another such attempt at obtaining a factorized representation of matrices to reduce the parameter space. The authors justify the use of Kronecker products to factorize parameter space, by showing that stacked layers of low rank matrices increase expressiveness. They also show the effectiveness of their proposed method by achieving a 4 to 14-fold reduction in parameters without sacrificing accuracy.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "Contributions:\nOne of the key contributions of this paper is showing how unlike low rank matrix factorization, stacking multiple layers of Kronecker factors, has an effect on the kind of matrices that can be represented. In the process they prove / make the following key observation:\n\n-- An orthogonal matrix can be  represented as a product of O(n^2) 2-variants givens matrices (known)\n\n-- Any 2-variant Givens matrix can be represented as a product of at most three component matrices where each component matrix is a sum of two pairs of Kronecker products. (theorem 2). \n\n-- This result extends to any n-by-m matrix in general. \n\n-- If instead one uses the sum of r Kronecker products of  matric pairs then the number of such matrices that are needed to represent an orthogonal matrix is O(n^2/r).\n\n-- Multiple experiments show that as compared to other factored representations such as low-rank, PHM the shapeshifter method achieves a better tradeoff in terms of parameter and BLEU score. \n\nWeakness\n\n-- Using Kronecker products to reduce/factorize the parameters has been explored in multiple works (and has been cited by the authors), thus reducing the novelty of shapeshifter. \n\n\n\nQuestions for the Authors:\n\n-- Given that in line 144 -145 the multiplication step uses many operations such as transpose and reshape, it would have been good to see on synthetic examples the tradeoff between memory (perhaps parameter size) and time for shapeshifter and other baselines. I would assume that a lower parameter representation is achieved at the cost of higher computational requirements.\n\n-- The previous question also points towards another relationship i.e. between computational cost (training time) and parameter reduction. Have the authors done any experiments on it or given it any thoughts?\n\nMinor points\n\n-- Instead of the result table, the tradeoff would be better visible with a plot of parameter size and BLUE score. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have not discussed any adverse societal impact of their research, and justified it as they are trying to reduce the size of large language model, which should provide solutions to some of the limitations of large language models.", "review_text": "", "extra_scores": {"ethical_concerns": "NA", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "11"}, "extra_text": {}}, {"review_id": "y1xkp_ctQi", "reviewer": "Reviewer_UTjx", "summary": "Shapeshifter reparameterizes dense kernels into a product of two lower-rank matrices. Shapeshifter introduces reshapes and transposes to make this reparameterization more efficient. The paper provides a theoretical justification for its expressivity and strong experimental results in machine translation.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "Originality: I haven't seen this exact factorization in previous literature, so I believe the idea is novel. It's a relative straightforward extension of low-rank factorization. I consider the simplicity a positive, however. TensorNetwork (https://github.com/google/TensorNetwork/tree/master/tensornetwork/tn_keras) is another generalization of low-rank factorization that I would have liked to see a comparison to.\n\nQuality: Claims are supported with theoretical justification and experimental results. The decomposition into Kronecker products provides good intuition. As the authors note, \"the [theoretical] results are limited to idealized multilayer models with linear activation\". Given that I hoped to see more experimental results. Maybe at least language modeling and compare against BERT (GLUE, SQuAD)? Some practical matters were left unaddressed. What's the effect on the reshapes and transposes on training and inference speed? It's common in larger models to parallelize the dense layer across multiple accelerators. Is that possible here?\n\nClarity: Paper clearly explains the ideas and experiments in a way that would be easy to reproduce.\n\nSignificance: Given the ease of implementation, I could see this method attracting widespread use as a way to reduce parameter count. More experimental results and benchmarks are needed and above practical matters would need to be addressed for researchers and practitioners to feel confident in using this technique, however.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I don't believe there are any potential negative societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "tXde1BmsCrY", "reviewer": "Reviewer_6iZJ", "summary": "This paper proposes a method to reduce the number of parameters by weight factorization. Unlike traditional low-rank factorization (n x r and r x m), this work decomposes the matrix into two sqrt(mn) x r matrices. The algorithm includes the reordering of elements to recover the desired shape. The authors find connections to Kronecker products and theoretically support the expressiveness of the proposed method. Experiments on NMT tasks show that Shapeshifter can achieve better parameter efficiency (fewer parameters with comparable performance). The results are compared to two similar works: PHM and DeLighT.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "Overall, the idea is simple and efficient. The paper is well-written and easy to follow. I also appreciate that the authors explained experiments in detail and split the parameter savings for each component in every table.\n\nI have a few concerns and suggestions:\n\n(1) In section 5.3 and table 5, the expressiveness is showed by comparing with low-rank factorization. (“Despite more than two times… increased expressiveness of a stack of low-rank … layers” (line 340-343)) However, the parameter reduction almost comes from the embedding, so how can we know that different factorization in layers is the reason of better performance? I suggest using the same embedding factorization method (or no factorization for the embedding) to match the number of parameters and only change layers above for fair comparison. Also, there should be some explanation of the relationship between the number of parameters and expressiveness.\n\n(2) I am not much familiar with the theoretical part, but does the analysis still holds after reshaping and transpose? Maybe these operations change the rank of the matrix?\n\n(3) As mentioned, (line 156-157) I agree that Shapeshifter implementation should be faster than PHM (and possibly slower than naïve low-rank factorization). It will strengthen the paper if there are some inference speed comparisons.\n\n(4) I am just curious that low-rank factorization (both naïve and Shapeshifter) ‘from-scratch’ is better than ‘decompose-after-training’. If we do not think about the training cost and the latter performs better, why should we train with a factorized form?\n\nMinor issue: in table 5, “Ro-En” should be changed to “En-Ro”.\n\n-------------\nAfter reading the authors' responses and other reviews, I think my concerns are well addressed. I appreciate authors, especially for extra experiments, and I'll change my score from 5 to 6.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors well addressed the limitations of theoretical analysis. Because the idea mainly focuses on efficiency, I do not think this paper needs more discussion about the social impact.", "review_text": "", "extra_scores": {"ethical_concerns": "There seems to be no ethical concern.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "5"}, "extra_text": {}}, {"review_id": "ju9jKzdbh5j", "reviewer": "Reviewer_7r5Z", "summary": "This paper proposes Shapeshifter, a parameter efficient Transformer using low-ranked factorized representations and some reshaping tricks to achieve fast, space efficient and expressive linear layers. ", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "I think this paper is a great contribution to existing literature that tries to make Transformers more parameter efficient. \n\nResults look great and promising, the method also looks interesting and simple (in a good way). \n\nThe results look very good, and Shapeshifter models seem to be able to substantially compress Transformers by almost 20 times in some cases while maintaining competitive performance. Results look very promising. The method also looks simple enough to have widespread potential impact. \n\nA particular nit I had is about the complexity. I think there is no mention or evaluation of flops/throughput/speed of the model. I was wondering if the authors could report that. Parameter counts are only one aspect of efficiency and it would be good to know how fast/slow the model is. \n\nAnother concern is also that experimental comparisons are quite limited and only conducted on MT tasks. It would be great if authors can provide more evidence that this works on another task other than MT alone. \n\nOverall, I like the idea and i think this could be pretty impactful. \n\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"ethical_concerns": "N/A ", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1.0"}, "extra_text": {}}, {"review_id": "emXhKB3joRA", "reviewer": "Reviewer_S3X5", "summary": "This paper presents an approach called ShapeShifter to compress large language models. The paper follows the approach of reducing number of parameters by using factorized matrix representations. The primary idea is to represent the matrix as a sum of Kronecker products, instead of standard low-rank factorizations. The paper theoretically shows that for non-square matrices, the proposed approach allows for increased reduction in parameters for the same decomposition rank. For square matrices, it allows for increased expressiveness of the decomposition for the same rank. Experimental results on machine translation tasks show that the proposed approach performs much better than the state-of-the-art model compression approaches and is just slightly worse than the large models.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "The paper is very well written and easy to understand. The primary idea itself is quite novel, although the use of Kronecker products as a matrix factorization technique has been around for a long time but this paper shows its application in compression large neural network which is quite interesting.  The authors also provide ample theoretical and experimental evidence to show that their method is indeed better than the state-of-the-art.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "1) Since the proposed compression still lags behind the large model it would be interesting to see some analysis on what exactly is this model not able to express, for instance how well does a rank r Kronecker product matrix represent a matrix from the original large model.\n2) The paper does not talk about any reduction in training time or prediction time, it would be good to see some discussion on that as well.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "B_nw6dDb77N", "reviewer": "Reviewer_uuLV", "summary": "This paper proposes an algorithm they call ‘Shapeshifter’ to reduce the number of parameters needed for Transformer-based models while preserving expressiveness and performance. The proposed algorithm is based on the idea of low-rank factorizations of weight matrices, but uses a different factorization method involving sums of Kronecker products that leads to greater expressiveness. They show theoretical analysis to prove their factorization can accurately represent any $n \\times m$ matrix or stack of matrices (in an idealized case), and experimental results using transformer-based models for translation on English-German, English-French and English-Romanian. They demonstrate superior or comparable performance with vastly fewer parameters compared to some other model compression techniques.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "This paper utilizes applies concepts proposed in previous work in a novel way to create a general method for reducing parameters needed in a wide variety of deep architectures. The proposed method is far more general than the work that came before it, and the reduction in parameter size it offers is applicable throughout almost any application in deep learning. I think it is a very strong paper overall, and a very useful contribution to the field.\n\n\nThe main criticisms I would make of this paper relate to the results and related work. First, I think it is odd that knowledge distillation methods such as DistilBERT are mentioned in the introduction, but not discussed in the related work or compared against in the results. I do understand that the proposed method is somewhat orthogonal to knowledge distillation and could perhaps even be used in concert with it. Nevertheless, the majority of successes in minimizing the size of transformer models in the literature thus far have used knowledge distillation (DistilBERT, TinyBERT, etc…), and a simple comparison of your method’s effectiveness against these existing approaches in preserving accuracy while reducing parameters would help make a stronger claim for the method’s usefulness. Without this comparison it is hard to judge if this using this method would lead to an actual improvement over existing techniques for shrinking model size. My one hesitation about giving this paper a higher score is due to my uncertainty over how it compares to these models.\n\n\nSecond, I think the results section could be better structured. There are 5 tables containing results from 5 different datasets, but multiple tables contain results from the same datasets and there are multiple different datasets used for the same language pairs. Many of the tables also lack captions and in places it is unclear how to interpret them (e.g. why are the results with the DeLighT architecture and PHM architecture both in table 2, with no explanation other than a horizontal line about what the difference between the first set of results and the second set of results is). These aren’t critical issues, but I found that I had to read through the results section three or four times before I understand what each of the tables was supposed to be representing.\n\n\nFinally, I had one or two questions I wanted to ask about the architecture. First, at the end of section 4 you claim “Compared to the equivalent sum of Kronecker-products representation, using the matrix factorization representation avoids the explicit summation of terms, resulting in simpler, more efficient implementations”. Is it actually faster? It seems like it should have the same number of operations to me. Second, you mention that the $m \\times n$ matrix is reshaped into a $\\sqrt{mn} \\times \\sqrt{mn}$ matrix. Do you discuss how you handle the case where $\\sqrt{mn}$ is not an integer?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Little to no discussion of either as far as I can tell. It might be a good idea to add some discussion about the situations where this approach is and is not suitable compared to other model compression approaches.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper attempts to improve parameter efficiency of transformer models for sequence modelling. In this regard, the authors propose a novel replacement of all matrices in the transformer by sum of Kronecker products (a type of low-ranked factorized representations) and some reshaping tricks. Further, the expressivity of such Kronecker-based linear layers is analysed. Empirical results on translation looks promising (better model-size vs performance trade-off as compared to other compression approaches for transformers). We thank the reviewers and authors for engaging in an active discussion, which resulted in clearing a lot of the concerns (e.g. speed/flops) and a lot of constructive feedback were provided to improve the paper. The authors provided new empirical results as part of the discussion, please include them in the final version of the paper as they add great value and understanding to the model as a whole.

- Please remove "fast" from abstract in the final version as the proposed method is slower than baseline in both training and inference.
Decision: Accept (Poster)