Multiplication-Free Transformer Training via Piecewise Affine Operations
Authors: Atli Kosson
Martin Jaggi
Venue: NeurIPS 2023 poster (2023)
Keywords: multiplication-free
neural architectures
piecewise linear networks
piecewise affine networks
efficient training
efficient arithmetics
TL;DR: Transformers can be trained in a fully multiplication-free fashion using an addition-based piecewise affine alternative

Abstract: Multiplications are responsible for most of the computational cost involved in neural network training and inference. Recent research has thus looked for ways to reduce the cost associated with them. Inspired by Mogami 2020, we replace multiplication with a cheap piecewise affine approximation that is achieved by adding the bit representation of the floating point numbers together as integers. We show that transformers can be trained with the resulting modified matrix multiplications on both vision and language tasks with little to no performance impact, and without changes to the training hyperparameters. We further replace all non-linearities in the networks making them fully and jointly piecewise affine in both inputs and weights. Finally, we show that we can eliminate all multiplications in the entire training process, including operations in the forward pass, backward pass and optimizer update, demonstrating the first successful training of modern neural network architectures in a fully multiplication-free fashion.

Multipicatton-Free Transformer Training via Piecewise Affine Operations
Atli Kosson
Martin Jaggi
EPFL, Switzerland
firstname wwwtnammeesfll.ccmmmmmm
Abstract
Multiplications responsible for most of the computational cost involved in neural network training and inference. Recent research has thus looked for ways reduce the cost associated with them. Inspired by Mogami (2020), we replace multiplication with a cheap piecewise affine approximation that is achieved by adding the bit representation of the floating point numbers together as integers. We show that transformers can be trained with the resulting modified matrix multiplications on both vision and language tasks with little no performance impact, and without changes to the training hyperparameters. We further replace all non- -ineaiiresss in the networks making them fully and jointly piecewise affine both inputs and weights. Finally, we show that can eliminate all multiplications in the entire training process, including operations in the forward pass, backward pass and optimizer update, demonstrating the first successful training of modern neural network architectures fully multiplication- free fashion.
Introduction
1/x
The computational cost of training state-of-the- neural networks has risen rapidly in recent years []] Aside from the increased price of training, this also requires more energy which of- ten comes with an environmental impact. Large language models, such as foundation models (2], are particularly expensive to train. These models are typically based on the transformer architec- ture [34]
exp2 (x)
log:
5-
Neural network training consists largely of ma- trix multiplications that generally account for the vast majority of the computational cost for standard architectures such as transform- ers. These matrix multiplications are performed by multiplying and accumulating the scalar el- ements of the matrices which are generally en- coded as floating point values during training. As floating point multiplication significantly more complicated than addition, it requires more logic gates and energy to perform in hardware. Horowitz (2014) estimates that for float32 operands, multiplication requires 4x more energy than addition. Approaches for computationally efficient training thus often focus on reducing the cost the multiplications. One such method is mixed precision training [23], where the multiplications are performed in lower precision format such as float16 or bfloat16 while the accumulation is still performed the standard float32. Mod-
Figure 1: Elementary neural network operations (solid lines) along with cheaper piecewise affine alternatives (dashed lines). The piecewise affine functions periodically match the originals and the derivative of each segment is an exact power of 2.
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

ern hardware accelerators for deep learning, such as TPUs [1] and tensor core GPUs 226 have specialized hardware support for matrix multiplication mixed precision.
A very different approach is to modify the neural network architecture itself, such as replacing multiplications with computationally cheaper but fundamentally different operations. This is the idea behind AdderNet [4] that uses the absolute difference of two numbers instead of their product in matrix multiplications. AdderNets involve few multiplications during inference but require special tricks during backpropagation that involve multiplications and/or exponentiation to achieve optimal performance. Another alternative tropical algebra that replaces the products with additions and the accumulation with a maximum, but has not shown to give performance competitive with standard neural networks (22) [9]. For both of these approaches, the main hardware advantage is replacing multiplications with additions that tend to be much cheaper in hardware.
The core idea we pursue in this paper falls in-between the two aforementioned approaches. We replace multiplications with operations that roughly approximate them but have a cost as cheap as addition. Since the operations are not fundamentally different, they should serve as a drop-in replacement for multiplications-sinn -iimlar to mixed precision- requiring architectural changes, while potentially being significantly cheaper. One such approximation is Mitchell's logarithmic multiplication 24 which approximates the product of A > 0 and B > 0 as:
AB Rs paexpz(palogz(A) + palogz(B))
(I)
where pacxp2 and palogz are cheap approximations of exp; and log2 shown in Figure along with an example output. All the approximations are piecewise affine (sometimes called piecewise linear) in their input arguments. The core of this operation can be performed efficiently in hardware using
int additions which are around 9x cheaper than float addition for 32-bit operands [12]. We roughly estimate the cost of piecewise affine multiplication to be around 30x less than that of standard float32 Approaches
multiplication in terms of the area and energy used by the operation itself (Appendix B I
based on logarithmic multiplication have also been explored for neural network inference and found to enable around 5x energy saving compared to bfloat16 multiply-and-ann aac-mucuuela operations [16).
Mogami 25 showed that Equation T can be performed by directly adding the floating point number representations together as integers, with some extra handling of the exponent accounting for the exponent bias, underflows and overflows. They further show that this trick can be used to train convolutional neural networks (in particular ResNet50 (II] with minor or no degradation compared to standard multiplications. In this work we further explore the application of piecewise affine approximations to neural network training, summarized below:
We show that transformers can be trained with piecewise affine matrix multiplications on both vision and language data with little to no performance impact. We compare this to AdderNet based transformers [30] demonstrating better accuracy while replacing more multiplications.
We define additional piecewise affine functions for all other operations in neural network and demonstrate fully multiplication-free training, with only a minor performance impact. No multiplications are used in any part of training, including the forward pass, backpropaga- tion and optimizer computation. To the best of our knowledge, this is the first time a neural network has been trained entirely without standard multiplications.
We show that the resulting neural networks are fully piecewise affine (sometimes called piecewise linear) both in their input and in their weights, a property that traditional trans- formers are very far from satisfying.
We publicly release our code2] including custom kernels, in the hopes of aiding further research into multiplication-free free neural networks.
I Note that special hardware support is needed realize these gains, see discussion Section
"oode available http://////pppp////e/ss/eeeeeeea wwfffeeemmippliaattt......aeeeee

---

2 Methods
2.1 Floating Point Numbers
Since the exact representation of floating point numbers is important to method we will give brief overview here. floating point number is represented as:
(-1)² S 2 (1 + M)
where S E {0, } is a sign bit, E is an integer encoding the exponent, and 0 < M < is the mantissa fraction. Note that this is analogous to the normalized scientific notation for decimal numbers (for example +1.23 10_
The encoding used for F and M varies between floating point formats. The commonly used IEFE 754 float32 uses the following bit representation:
[S eo, E7. Mo.
M22
where the exponent is encoded unsigned integer E with bias of 127 i.e. F: = F. 127 e0 127 and the mantissa as an unsigned integer M that is divided by 2 to get
M
A7 mg... 1922
223
223
Floating point numbers also encode special values that do not fit within the representation given in Equation 2 In float32 = 255 is used to represent NaN (not a number) or infinity depending on the value of M. For E = 0 the float is interpreted as a denormal number (-1) S 2 - which also gives the representation of O, which is E 0 and M O. Some floating point formats, e-g. bfloat16 do not allow denormal numbers other than O, since those can be more expensive to handle in hardware.
2.2 Piecewise Affine Multiplication
We define the piecewise affine multiplication (or PAM for brevity) of two floating point numbers:
A (-1)sa 2Ea (1 (A),
B B= B-() 2EB (1 MB)
(4)
A B:
A:B : (-1)SAiB, FA . (1 + MAAB)
(5)
SA:B = SA + SB
(6)
FAIB = FA + Fg 1[M4 + MB 2 1}
(7)
MAIR == MA + Mn - 1[Ma + Mn 2 1}
(8)
where 1{a} is one when holds and zero otherwise.
We observe that A B is roughly achieved by adding the signs, exponents and mantissas of A and B. In fact, this becomes precise if we allow MA ø to overflow into E B. This happens if we add the float32 bit representations of A and B together as int32.
A technicality is that the exponent requires special handling, the resulting E is only offset by 1127 should be offset by twice that amount requiring us to subtract 127 from the exponent of the sum. We also need to make sure the resulting F. has not overflowed or underflowed, instead clamping it to the min and max values. Possible denormal values (mantissa starting with zeros) can be flushed to zero for simplicity, done in e.g. bfloat16. Finally we check that the incoming A and B do not represent special values such as NaN or infinity and handle those cases explicitly.
For float32, PAM can thus be simply implemented with two int additions and a couple of checks for the exponent. For current hardware accelerators such as GPUs, this expensive and requires multiple instructions. However the logic is much simpler than for standard multiplication, so new hardware with native support could perform this operation cheaply. With a custom floating point format without an exponent bias, we could further get rid of one of the int additions as well. This could also be done for configurable hardware such as FPGAs. In Appendix we roughly estimate the hardware cost of PAM, estimating the savings to be around 5-30x over standard multiplication in float16 and float32.
3

---

2.3 Other Piecewise Affine Operations
As mentioned in the introduction, piecewise affine multiplication can be expressed in terms of paexp2 and palog2 which we can write as follows for A. B from Equation 4
paexp2 (A) 21
A [A]]
(9)
palogz (A) Σ + MA. for A > 0
(10)
where [A] denotes rounding down to the nearest integer. For positive inputs Equation then becomes:
AB z paexpa(palogz(44 (A) + palogz(B)) B))
(11)
- (1 +1+ E'A + EB + MA + MB [EA + EB + MA + MB.)
(12)
(1 + MA + Mn M( + MA 1})
(13)
Which is equivalent to A B, aside from the computation of the sign.
We define piecewise affine division as the inverse of A B:
4 B = (- (-1) . 2 (1 M MA B)
(14)
SA = SA SB
(15)
F = F. EB 1(MA MB S 0}
(16)
M = MA MB + 1(MA- MB S 1}
(17)
which corresponds to ppaxpy(palog, paloga (B)) for positive numbers. A can also be efficiently performed in hardware float32 using int32 subtraction where bias offset of 127 needs to be added to the result.
With paexp2 and palogz the natural logarithm and exponential as well as square roots.
also define general piecewise affine functions for powers, including
paexp(A) (A) (lexp2(oog2 (e)= AA)
(18)
palog (A) palogz (A) - log2(e)
(19)
pasqrt(A) (A) pacxpa (A))
(20)
With these functions we can implement various neural networks operations such as normalization layers, softmax, cross-entropy and other losses as well optimizer updates.
2.4 Piecewise Affine Neural Networks
Modern artificial neural networks are compositions of the operations discussed in the previous subsections. We thus replace each traditional operation network with its piecewise affine approximation. Unlike traditional networks, the resulting network will now be piecewise affine function, both its weights and also in its input values. This follows directly since the composition (and sum) of two piecewise affine functions (with one many arguments) remains piecewise affine. iterate the composition through all layers and loss computation.
This global property of being piecewise affine (and thus having piecewise constant gradients) is remarkable as does not hold for traditional e.g. ReLU networks, due the composition with the most common losses, and also is far from true for traditional transformers. Despite this drastic change in the gradient structure and loss landscape, we will show that commonly used optimizers (and their multiplication-F free counterparts) still enable successful training out of the box without additional hyperparameter tuning.
2.5 Derivatives
we consider two ways to compute the derivatives of the piecewise affine functions. The first option is to compute the true derivatives those functions, which are piecewise constant and discontinuous. The second option is to implement the analytical derivative of the original function we are approximating, for example standard multiplication, with the piecewise affine functions. We will refer to the first option as the exact derivative and the second as the
Following Mogami 25

---

Table 1: Derivatives for Piecewise Affine Operations for A, B defined in Equation 4
OPERATION
EXACT DERIVATIVE
APPROXIMATE DERIVATIVE
Y A²B
ÓA Br
Y A&B
AΛ 2- fg R by
8Λ dy + BBB
Y A B
6B = - (B:BB)
óg -(A=5y) -(A35)) (B:B)
Y (Ae
AΛ 21=In(2)=55
Y = paloga(A)
DA = 2 FA by
5A By (n=1))
approximate derivative. Table both kinds derivatives for each operation described previously, use delta notation for backpropagation, i.e. 6Λ and 6y
0T. for some unspecified sealar øy
function I. that only depends on A through the output 23
We note that is an exact power of two which means that the multiplication can be performed exactly via PAM, see Section 2.7 Both types of derivatives can therefore be computed in multiplication-free manner, only using PAM and related operations. This also extends to derived operations such as paexp, palog, pasqrt, softmax and normalization. We can backpropagate through the derived functions via the the computational graph that defines them, using either the exact or approximate derivatives given above. By extension, we can perform the entire forward and backward pass through a neural network consisting of these primitives without any traditional multiplication operations.
though the exact derivative sometimes contains multiplication, of the numbers
2.6 Optimizers
Networks with piecewise-affing components can be trained using standard gradient based optimization using the derivatives given in the previous section. However, the implementation of the optimization algorithm itself might involve additional multiplications (such with varying learning rates, adaptive learning rates or for computing other optimizer statistics). We thus also experiment with replacing all optimizer multiplications and divisions with their piecewise affine analogs, and quantify the impact of this change in our experimental results.
2.7 Approximation Error
Figure 2 compares PAM and standard multiplication. It also shows the relative error of ø1 702 compared to 22 which depends on the exact mantissas of the inputs. PAM gives the exact result when the mantissa of either input is zero, i.c. when a power of 2. The maximum relative error of (1+0.3+0.3)-1.5*
1199 = - 11.1% is obtained when M = 0.5 for both numbers. When either input is fixed, e.g. when multiplying a variable by a constant, the maximum error can lower.
1,5"
0.0
-1111
X1
2
X1
2
X1
Figure 2: Comparison of the piecewise affine multiplication and standard multiplication of two num- bers Fy I2 the range 21. These patterns repeat per octave. Left: Piecewise affine multiplication. Middle:
Standard multiplication. Right: Relative error 21 1ag= measured in percents.
2122
5

---

The relative approximation error of PAM can be reduced by an additional PAM operation. For an appropriately choosen value a, the expression xj Fx2 a will better approximate 41 22 on average and/or the worst case. If either 21 22 is a constant that is known ahead of time, e.g. when computing paexp and palog, this can be taken into account when choosing a for a specific operation. For PAM matrix multiplications, scaling the output instead of the inner scalar products may be sufficient to eliminate bias in the output magnitude. In general this sort of approximation will be more expensive than single PAM operation and we leave it to future work to explore where and when this additional error compensation is beneficial.
The exact and approximate derivatives have different error characteristics when viewed as approxi- mations of the derivative for a standard multiplication. The exact derivative is unbiased on average, since PAM is continuous and matches multiplication at certain points. However, the exact derivatives are discontinous and have a high variance in the sense that for a specific input the error is often large. On the other hand, the approximate derivative usually has a lower error at a given point (i.e. low variance) but may be biased on average. These characteristics of the two derivative types also hold for the other functions. Figures and and Iin the appendix show the exact and approximate derivatives for several functions.
3 Experiments & Results
3.1 Experimental Setup
We use PyTorch (28) for our experiments and run them using either Nvidia A100 (40GB) or V100 (32GB) GPUs. Elementwise piecewise affine multiplication, division, palog2 and paexp2, as well as PAM matrix multiplications are performed using custom CUDA kernels. For verification, we also run alternative native torch implementations of these operations that run significantly slower. Other functions such as normalization and softmax are implemented by composing these operations. The training setup (e.g. hyperparameters) for both the standard and piecewise affine networks is identical. All hyperparameters are obtained from other works and have not been tuned specifically for piecewise affine training.
In our experiments we consider two training tasks, one on text data and one in computer vision. The first one is German to English translation on the IWSLT14 DE-EN dataset [3 consisting of roughly 160K sentence pairs from translated TED talks. The model is small transformer with encoder and decoder layers each, 4 attention heads an embedding dimension of 512, feed forward hidden dimension of 1024 and ReLU activations. The training code for this task is based on the FairSeq (27) codebase. Our baseline setup trains for 20 epochs, using cosine decay schedule with 4000 warmup steps and a peak learning rate 5- 10 with a maximum batch size of 4096 tokens. We use AdamW W (21 [7 for optimization with 3, = 0.9, A3 = 0.98 and weight decay of 10-4. During training we apply a dropout with drop probability 0.3 and use cross entropy with a label smoothing of 0.1........ For evaluation we use beam search with 5 beams and report the BLEU score on the test set.
The second task is training a DeiT-Tiny (32 Vision Transformer 5 without distillation. This model has 5M parameters, 12 layers with 3 heads and an embedding dimension of 192. We train on either CIFAR10 [9] or the ImageNet- 1k 66 dataset. CIFARIO 10 consists of 50K training and 10K test images of size 32 x 32 corresponding to 10 classes. When training on CIFARIO 10 we upscale the images 224 224 and use the same data augmentation procedure described in DeiT [32) for ImageNet. ImageNet- Ik [6] contains 1.28M training images and 50K validation images in 1000 classes. The images have different sizes but are processed a resolution of 224 x 224 for training. These experiments are based on the PyTorch Image Models project (36). Optimization is performed using AdamW with 31 0.9, 33g 0.999 and weight decay of 0.05. Our base learning rate of 5- 10-4 which is scaled linearly by the total batch size (1152 for ImageNet, 1024 for CIFARIO) 10) divided by 512. We use a cosine decay learning rate schedule with a warmup of epochs and train for total of 300 epochs on ImageNet or 600 epochs on CIFARI0.
3.2 Replacing Matrix Multiplications
As mentioned before, matrix multiplications account for the majority of the computational cost of training neural networks and are therefore provide the largest opportunity for cost reduction. We experiment with replacing all matrix multiplications on both the forward and the backward passes with matrix multiplications where scalar multiplications are replaced by piccewise affine

---

Table 2: Top-1 1 Test/Validation Accuracy for DeiT- Teny Training. The brackets denote the change
from the baseline. Shu et 2021 reports a different baseline accuracy of 92.6% on CIFARIO.
DATASET
BASELINE
PA-MATMUL
ADDER
CIFARIO
94.8%
95.0|+0.21%
92.4 0.2%%*
IMAGENET
72.2%
72.2[+0.0]% %
70.5|-1.77 1.7
multiplications. This includes all linear layers, the batched matrix multiplication used in the attention and the convolutional layer used for the patch embedding in the vision transformer. Here we the same type of matrix multiplications on the backwards pass which corresponds to the approximate
derivatives described in Section 2.5
Our results for DeiT-Tiny on CIFARIO and ImageNet can be seen in Table 2 The PAM based matrix multiplication training matches the baseline accuracy for both datasets. We compare Adder Attention [30] which also replaces multiplications by cheaper addition based operations. They do not replace the batched matrix multiplication and use standard matrix multiplication for the first and last transformer layer on ImageNet and also use multiplications to smooth the gradients during the backwards pass. Adder Attention transformers can roughly match their reported baseline accuracy for CIFAR 10, but do suffer from a sizable degradation on ImageNet.
For IWSLT14 we obtain baseline test BLEU score of 34.37. Replacing all matrix multiplications on the forward and backwards passes with PAM based matrix multiplications gives test BLEU score of 34.22. Both scores averaged over three runs. The observed difference of 0.15 is slightly larger than the run-to-run variance we observed, but fairly small overall. We also note that we use standard hyperparameters originally obtained from FairSeq and tuning the hyperparameters may improve performance.
In Appendix C we show similar experiments for several non non-transformer models including convo- lutional neural and mixer architectures on CIFAR-I0. We find little to no degradation across all networks tested.
3.3 Replacing Other Operations
In Table we measure the impact of using piecewise affine versions of different network components. We isolate the effect of each component and experiment with the two different derivative types described in Section [ MATMUL refers to the linear layers and the batched matrix multiplications that replaced in Section 3.2 Using exact derivatives for the matrix multiplications performs notably worse than the approximate ones. The same holds for piecewise linear layer normalization, with approximate derivatives observe little notable one. ATTENTION SOFTMAX refers to the softmax operation performed computation and excludes the softmax for the loss. Here we find that the using the exact derivatives cause a training instability when using the default hyperparameters whereas the with the approximate backwards pass the performance impact is negligible. The Loss function, softmax cross-entropy with label smoothing, is the only operation where we find the approximate BWD pass to perform
degradation but using the exact ones cause
the attention
Table 3: BLEU Test Scores IWSLT14 DE-EN translation for modified Transformer-Smie Small training where certain operations are replaced with piecewise affine approximation, using either the exact approximate backward pass. Cumulative experiments replace all previously listed operations using the better performing derivative version for each one. The brackets denote the change from the bascline BLEU score 34.4 = 0.1. Each reported score the ste over three runs with different seeds.
PA OPERATION(S)
EXACT BWD
MIMIC BWD
CUMULATIVE
MATMUL
33.4[- -.0]
33.4[
0.1
34.2 0.2
34.2[-0.2] 0.2
ATTENTION SOFTMAX
3.0 11-31144-
0.9
34.3
0.7
34.2
1 0.2
LAYER NORM
33.7 -3.7
34.4'-0.0 0.1
34.4|-0.0
+ 0.1
LOSS
33.7
-
0.2
33.0
33.7|-0.7] 0.2
OPTIMIZER
31.2[
0.2
+ 0.1
33.5[
0.3
7

---

worse than the exact one. It is also the only network component where both types of derivatives have a notable performance loss.
Finally we experiment with using piecewise affine operations for the optimizer update. The Adam optimizer uses multiplication, division and square root. Replacing all of them only causes minor degradation of 0.2 BLEU compared to the standard version.
3.4 Fully Multiplication-Free Training
Here we combine all the piecewise affine replacements from the previous section one by one. The resulting BLEU scores are displayed in the last column of Table We chose the derivative type that performed better for each operation which is the approximate one for everything except the loss. Each transformer block contains gain that replace with PAM when we replace the attention softmax.
Overall there little to no performance impact from replacing the matrix multiplications, softmax and layer normalization. Replacing all of them together does not seem to cause any unforseen issues. Consistent with our previous observations, replacing the loss with a piecewise affine function causes small BLUE score degradation.
The last entry in Table covers every multiplication and non-linearity in the training process. This includes the forward pass, the backwards pass and the parameter updates by the optimizer. The resulting performance impact is only 0.9 BLEU points and hyperparameter tuning could potentially reduce it even further.
Related Work
As mentioned in the introduction, most related work falls into the two classes of approaches, depend- ing the original neural network architecture is preserved or not.
For the first type, fine-grained changes of operations are made to individual multiplications or groups thereof, aiming to closely approximate the original multiplications. Examples for this are mixed precision training (23), and more generally block-floating point schemes, where several weights are grouped together share the same floating point exponent, enabling inference and training [8 g. Another class of related approaches is quantization, which is widely used for inference but introduces additional challenges for training [20]. All mentioned approaches have in common that some multiplications are still needed, thus might not be viable on multiplication- free hardware.
Approaches of the second type allow more drastic changes to the architecture, thus offering more promise to new types of multiplication-free operations. A prominent example are AdderNets 4 30) the related EF-operator (38] which rely on absolute differences instead of inner products, and show these can serve as replacement layers for convolutions or also parts of self-attention layers (30), though training can not be made fully multiplication-Fii free while maintaining performance. Another type of fundamentally different architectures can arise by replacing classical arithmetic with tropical algebra, where all multiplications are replaced by additions and additions are replaced by maximum. While numerically very efficient, performance was not shown to be competitive with standard neural networks
To the best of our knowledge, the approach of Mogami 25 @which serves as the basis of our work here-in currently the only work which allows to preserve the neural network architecture while at the same time paving the way for training on fully multiplication- hardware, if applied to all elements of the training process.
5 Discussion
The main goal of this work demonstrate the applicability of piecewise affine function approxi- mations to end-to-end transformer training. In our experiments we showed that all operations during training can be replaced by such functions. We believe this is the first fully multiplication- free training of transformer model and potentially any neural network. While PAM approximates real multiplication to a certain extent, does not aim to do so as closely as possible, unlike floating point multiplication in finite precision. Instead PAM uses line segments with slopes that are powers of 2. By doing so it becomes significantly simpler, providing the same hardware benefit as replacing all multiplications with e.g. addition, like some other approaches to multiplication-Fii free networks aim to
8

---

do. At the same time PAM does roughly approximate standard multiplications overall, allowing it to function as a plug-in replacement across various usecases. This includes the optimizer update and the weighted average in attention, which would be hard to replace with something like addition. PAM therefore seems to strike good balance between cost and utility.
Our main inspiration is the work of Mogami [25] which applied piecewise affine approximations to convolutional networks, including convolutional layers, linear layers, batch normalization and exponents, Depending on the implementation, this may have been sufficient to make the forward and backwards pass fully multiplication-Fre -free but it unfortunately unclear from the paper and no code is publicly available. We focus on transformers making both the forward and backwards passes multiplication-Ff free and fully piecewise affine. We also extend this to the optimizer eliminating all mul- tiplications in the training process, allowing it to run on entirely on hardware without multiplication support.
Although piecewise affine operations are logically simpler than their standard equivalents, special hardware is required fully reap the theoretical advantages. Currently available hardware ac- celerators, such as GPUs and TPUs, have arithmetic units that are specialized for floating point multiplication but lack the comparatively simpler logic circuits that would enable fast piecewise affine multiplication. In practice this means that our present GPU implementation has to perform multiple instructions for every standard aattiill-and-cccummett cantly slower, even with custom kernels. Field-Pue Progrrrrgaaaablee Gate Arrays (FPGAs) are one type of hardware that could immediately benefit from PAM. Since their logic circuits are fully configurable, they don't it have the "sunken cost" of standard multiplication arithmetic and can instead spend it on PAM circuits.
operation causing it to run signifi-
As described in Section 2.4, replacing all multiplications and non-lincarities in neural network with piecewise affine operations results in network that is fully jointly piecewise affine in both inputs and weights. This is an interesting theoretical property since it differs significantly from standard transformers.
Surprisingly, replacing all operations in the network itself doesn't 't seem to have a large impact on the performance in our setup. This differs from the observation by Mogami 2020 which found that linear layers did not work well with approximate derivatives. We observe a similar phenomenon for the loss function which could indicate that training is sensitive to slight errors early in backpropagation.
This project focused on standard neural networks without any modifications. However it would be interesting to explore modifying the network architecture to be even better suited to piecewise affine approximations. One potential way of doing this is to use log, and exp, throughout, for instance in the softmax and loss computation. These operations are much easier to approximate than their base-e equivalents. Exploring the effects of error both from quantization as the mantissa is decreased and from magnitude bias is another future research direction.
6 Conclusion
In this work we explored the use of hardware-efficient piecewise affine operations for transformer training. We experiment on CIFARIO [19] and ImageNet-1k k (6] with DeiT-tiny 32 as well as on IWSLT14 German to English translation (3 using a small transformer network. We show that floating point multiplications within matrix multiplications can be replaced by cost-effective piecewise affine multiplications with minor or no performance degradation for all three datasets, and without additional hyperparameter tuning.
We further show that we can extend this to replace all multiplications, division and non-linear functions in the small transformer, the loss function and the optimizer with piecewise affine functions. The resulting performance impact is minor and could potentially be reduced further by hyperparameter tuning. This eliminates all multiplications in the entire training process, for fully multiplicatio-ffre free training which we believe has not been demonstrated before. This also makes the network fully and jointly piecewise affine in both inputs and weights, property that could be of theoretical interest.
We publicly release our code, including the kernels that made our experiments computationally viable. This could help further research in this area and into other multiplication-fit free methods.

---

References
[1] D. Amodei and D. Hernandez. Al and compute, 2018. URL http:::t/p///o http:://opeenai.ccco com/blog/
ai anddaddddoon compute/
[2] R. Bommasani, D. Hudson, Adeli, Altman, S. Arora, S. von Arx, M. S. Bernstein, J. Bohg, A. Bosselut, E. Brunskill, et al. On the opportunities and risks of foundation models. arXiv preprint arXiv: 108. 0020800778,...8 2021.
[3] M. Cettolo, J. Niehues, S. Stüker, L.. Bentivogli, and M. Federico. Report on the 11th IWSLT evaluation campaign. In Proceedings of the / 1th International Workshop on Spoken Language Translation: Evaluation Campaign, pages 2-17, Lake Tahoe, California, Dec. 4-5 2014. URL
[4] H. Chen, Y. Wang, C. Xu, B. Shi, C. Xu, Q. Tian, and C. Xu. Addernet: Do we really need multiplications in deep learning? In Proceedings of the IEEE/CVF conference computer vision and pattern recognition, pages 1468-1477, 2020.
[5] J.-B. Cordonnier, A. Loukas, and M. Jaggi. On the relationship between self-attention and convolutional layers. In ICLR- International Conference on Learning Representations, 2020.
[6] J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei. ImageNet: Hierarchical Image Database. In CVPR09, 2009.
A Large-Scale
[7] A. Dosovitskiy, L. Beyer, A. Kolesnikov, D. Weissenborn, X. Zhai, T. Unterthiner, M. Dehghani, M. Minderer, G. Heigold, S. Gelly, J. Uszkoreit, and N. Houlsby. An image is worth 16x16 words: Transformers for image recognition at scale. In ICLR International Conference Learning Representations, 2021.
[8] M. Drumond, Lin, M. Jaggi, and B. Falsafi. Training DNNs with Hybrid Block Floating Point. Advances in Neural Information Processing Systems, 31, 2018.
[9] S. Fan, L. Liu, and Y. Luo. An alternative practice of tropical convolution to traditional convolutional neural networks. In 2021 The 5th International Conference on Compute and Data
Analysis, pages 162-168, 2021.
[10] A. Gholami, S. Kim, Z. Dong, Z. Yao, M. W. Mahoney, and K. Keutzer. A survey of quantization methods for efficient neural network inference. arXiv preprint arXiv:2 13630, 2021.
[11] K. He, X. Zhang, S. Ren, and J. Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 770- 778, 2016.
[12] M. Horowitz. 1.1 computing's s energy problem (and what we can do about it). In 2014 IEEE International Solid-State Circuits Conference Digest of Technical Papers (ISSCC), pages 10-14, 2014. doi: 10. (U09//SCCC.211..6577777
[13] Johnson. Rethinking floating point for deep learning. arXiv preprint arXiv: 2018.
[14] N. P. Jouppi, C. Young, N. Patil, D. Patterson, G. Agrawal, R. Bajwa, S. Bates, S. Bhatia, N. Boden, A. Borchers, et al. In-datacenter performance analysis of tensor processing unit. In Proceedings of the 44th annual international symposium on computer architecture, pages 1-12, 2017.
[15] D. Kalamkar, D. Mudigere, N. Mellempudi, D. Das, K. Banerjee, S. Avancha, D. T. Vooturi, N. Jammalamadaka, J. Huang, H. Yuen, et al. A study of 6 for deep learning training. arXiv preprint arXiv: 1905. /2322, 2019.
[16] M. S. Kim, A. A. D. B. Garcia, H. Kim, and N. Bagherzadeh. The effects of approximate multiplication on convolutional neural networks. IEEE Transactions on Emerging Topics in Computing, 2021.
[17] D. P. Kingma and Ba. Adam: A method for stochastic optimization. arXiv preprint 14X1v:1412.6980, 2014.
[18] U. Köster, T. Webb, X. Wang. M. Nassar, A. K. Bansal, W. Constable, O. Elibol, S. Gray,
S. Hall, I.. Hornof, al. Flexpoint: An adaptive numerical format for efficient training of deep neural networks. NeurlPS Advances in Newral Information Processing Systems, 30, 2017.
[19] A. Krizhevsky, G. Hinton, et al. Learning multiple layers of features from tiny images. Technical report, 2009.
10

---

[20] H. Li, De. Z. Xu, C. Studer, H. Samet, and T. Goldstein. Training quantized nets: A deeper understanding. NeurIPS- Advances in Neural Information Processing Systems, 30, 2017.
[21] I. Loshchilov and F. Hutter. Decoupled weight decay regularization. arXiv preprini 17Xiv:1711.05100 2017.
[22] Y. Luo and Fan. Min-max-plut neural networks. arXiv preprint arXiv:2102.06356 2021.
[23] Micikevicius, S. Narang, Alben, G. Diamos, E. Elsen, D. Garcia, B. Ginsburg, M. Houston, O. Kuchaiev, G. Venkatesh, and H. Wu. Mixed precision training, In ICLR International Conference on Learning Representations, 2018.
[24] J. N. Mitchell. Computer multiplication and division using binary logarithms. IRE Transactions on Electronic Computers, EC-1 (4):512--17 1962. doi: 10.1 10.1909T 1932.52199.1
[25] Mogami. Deep neural network training without multiplications. In Beyond BackP rropaaropatioon WS al 34th Conference on Neural Information Processing Systems, 2020.
[26] Nvidia. Nvidia Tesla V100 GPU Architecture. In Nvidia Tesla V100 GPU Architecture, 2017.
[27] M. Ott, S. Edunov, A. Baevski, A. Fan, S. Gross, N. Ng. D. Grangier, and M. Auli, fairseq: A fast, extensible toolkit for sequence modeling. In Proceedings of NAACL-HLT 2019: Demonstrations, 2019.
[28] A. Paszke, S. Gross, F. Massa, A. Lerer, J. Bradbury, G. Chanan, T. Killeen, Z. Lin, N. Gimelshein, L. Antiga, A. Desmaison, A. Kopf, E. Yang. Z. DeVito, M. Raison, A. Tejani, Chilamkurthy, B. Steiner, L. Fang, J. Bai, and S. Chintala. Pytorch: An imperative style, high- performance deep learning library. In NeurlPS- Advances in Neural Information Processing
Systems 32, pages 5024-8035. 2019.
[29] C. Sakr, N. Wang. C.-Y. Chen, J. Choi, A. Agrawal, N. Shanbhag, and Gopalakrishnan. Ac- cumulation bit-width scaling for ultra-low precision training of deep networks. In International Conference on Learning Representations, 2019. URL BRLhhttps: h/:p:::///peeee //tp///veee/eeeee/////ee/ee wwtpeviwwww.wee.oeeeeeeeeee net/forum?
id=BkIMjsRqy7
[30] H. Shu, J. Wang, H. Chen, I. Li, Y. Yang. and Y. Wang. Adder attention for vi- sion transformer. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P. Liang, and J. W. Vaughan, editors, NeurIPS Advances in Neural Information Processing Systems, volume 34, pages 19899-19909, 2021. URL.URRRLLttttt http:////wrroeeeengeeee.ee..eapp 1372591161333aaa1111110111111113
pdf
[31] K. Simonyan and A. Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv: 2014.
[32] H. Touvron, M. Cord, M. Douze, F. Massa, A. Sablayrolles, and H. Jégou. Training data-efficient image transformers & distillation through attention. In ICML- International Conference on Machine Learning, pages 10347-10357. PMLR, 2021.
[33] A. Trockman and J. Z. Kolter. Patches are all you need? arXiv preprint arXi::2201.0979)
2022.
[34] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, L. Kaiser, and I. Polosukhin. Attention is all you need. NeurIPS- Advances in neural information processing systems, 30, 2017.
[35] N. Wang. J. Choi, D. Brand, C.-Y. Y. Chen, and K. Gopalakrishnan. Training deep neural networks with bit floating point numbers. In Bengio, Wallach, H. Larochelle, K. Grauman, N. Cesa- Bianchi, and R. Garnett, editors, Advances in Neurul Information Processing Systems, volume 31. Curran Associates, Inc., 2018 URL
[36] R.
Wightman.
Pytorch image models.
https://github..com///i///
pytorch- iaana-imm----aa image-models models 2019.
[37] S. Xie, R. Girshick, P. Dollár, Z. Tu, and K. He. Aggregated residual transformations for deep neural networks. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 1492-1500, 2017.
[38] O. Yıldiz. Training methodology for a multiplication free implementable operator based neural networks. Master's thesis, Middle East Technical University, 2017. URI. httpss
//hdl, handle net/11511/26664
11

---

A
Additional Figures
1.3
Relative error for 1.5 x
Derivatives for 1.5-X
Relative gradient error for 1.5
22
0.2
18
0.1
-.2
14
-2
-2
-2
-2
1.5/x
error
Derivatives 1.5/x
Relative gradient emor
0.94
0.2
0.0
-10
0.02
0.00
-20
Relative for x/1.5
Derivalives x/1.5
Relative gradient x/1.5
2.50
0.32
1.75
0.4
0.30
1.50
1.25
0.04
0.7
0.00
x²
Relative error for
Derivatives for x²
Relative gradient error for x
0.2
-5
-0.2
0.10
Vx
Derivatives
gradient
3.0
2.5
0.05
2.0
0.3
0.2
0.1
0.0
1.0
0.92
-0.1
0.5
-0.2
0.09
2.5
10.0
0.0
2.5
5.0
20.0
2.5
3.0
10.0
0.0
3.0
10.0
Figure 3: Piecewise affine multiplication, division, square and square root along with their standard equivalents. Each row corresponds to one function. Left: A function (solid line) with its piecewise affine alternative (dashed line). Left middle: The relative error f(z)=(()) when the piecewise affine
[f(z)]
function f is viewed as an approximation the standard function f. Right middle: The derivatives of f (solid black), the exact derivative for (dotted blue) and the approximate derivative of f (dashed red). We assume ôy 1.25 in the equations in Section 2.5 which emphasizes the PAM operations used, compared to ōy = 1 where PAM matches standard multiplication. Right: The relative error (' for the exact derivative f' (dotted blue) and the approximate derivative f' (dashed red)
(f)
when viewed an approximation of (2)x,, the derivative of (xx
12

---

exps (X]
Relative error for expy (x)
Derivatives for expy (X)
Reletive gradient error for exp:
0.06
9.3
0.04
0.2
0.03
9.1
0.0
-0.1
0.01
-02
-2.3
explx)
Relativee exp(x)
Derivatives expix)
Relative for
150
0.4
0.3
150
0.75
100
Mmm
0.50
150
0.25
0.0
0.00
-0.1
-32
0.50
log: [x]
Relative error for logz DX
Derivatives for loge Or)
Relative gradient error for log: (x)
1.
0.4
2.0
-0.05
1.5
1.5
-0.30
-0.35
0.0
-0.20
0.5
-0.1
-3.2
0.25
for
gradient
12-
1.00
0.75
0.25
0.00
0.2
-0.25
-0.50
25
50
100
50
100
25
50
300
50 1.00
Figure 4: The equivalent of Figure for exponentials and logarithms, showing piecewise affine functions with their standard counterparts. Piecewise affine exponentials and logarithms along with their standard equivalents. Each row corresponds one function. Left: function (solid line) with
its piecewise affine alternative (dashed line). Left middle: The relative error f(x)-f(x) when the
[(,]]
piecewise affine function f is viewed as approximation of the standard function f. Right middle: The derivatives of f (solid black), the exact derivative for f (dotted blue) and the approximate derivative of f (dashed red). We assume dy = 1.25 the equations Section 2.5 which emphasizes the PAM operations used, compared to öy = where PAM matches standard multiplication. Right:
The relative error f'(x)_f((m) for the exact derivative f' (dotted blue) and the approximate derivative [x)]
f' (dashed red) when viewed as an approximation of f'(z), the derivative of fz))
13

---

Table 4: Hardware costs of arithmetic operations in different precision from 12
10
ADDITION
MULTIPLICATION
FORMAT
ENERGY [pJ]
AREA [um*]
ENERGY [pJ] AREA [um*)
INT32
0.1
137
3.1
3495
INT16
0.05
67
INT8
0.03
36
0.2
282
FLOAT32
0.9
4184
3.7
7700
FLOAT16
0.4
1360
1.1
1640
B Hardware Cost of Piecewise Affine Multiplication
It important to note that our objective in this work is to investigate the machine learning characteris- ties of training with piecewise affine operations, rather than designing a hardware implementation. demonstrate that such training is viable, with final model performance and convergence speed roughly identical to standard training. Without such algorithmic evidence to motivate their development, the development of efficient hardware implementations is unlikely. Although the details of the integrated circuit design should not affect e.g. convergence, they can drastically affect the cost the operation in terms of energy or area.
Such hardware considerations include which aspects standard floating point numbers are supported, e.g. denormal numbers, different types of NaNs and so on, well as whether to use a custom encoding of exponent for instance. An actual hardware implementation would also have to consider factors such latency, as well as memory characteristics like bandwidth and read costs. The design could either focus on individual operands or vectors like tensor cores and systolic arrays. Operating directly on vectors matrices allow significant amortization of some of the costs involved.
Ignoring most of these considerations we can arrive at very rough estimate of the costs. We assume that the cost of multiply- and-accumulate operations is the sum of the costs provided in Table for multiplication and addition. A PAM operation can be performed with one full int32 addition and one int8 addition for the exponent which also needs check for under overflow. When implemented as a logic circuit, we estimate the cost of this could be comparable to two int32 additions. Using these numbers float32 PAM uses roughly 2:0.1 3.7 5.4% of the energy and 2-137
7700 = 3.6% of the area
compared to float32 multiplication and 1.1 = 18% the energy and 2-137 = 17% of the area 1640
compared to float16 multiplication. PAM is likely work with smaller numbers such float16 which would reduce the cost further by a factor of around x. In Appendix D we find that mantissas as narrow bits may work well, significantly less than the 10 and 7 bits used in float16 and bfloat16.
PAM reduces the cost of multiplications by roughly an order of magnitude but does not affect accumulation. The average savings for multiply-and-accumen lower. For multily float32-accumulate PAM could have a cost of roughly 2-0.1+0,9 24% of the energy and 2: 13744188
(MAC) operations will therefore be
3.7+0.99
7780+1181 38% of the area. For standard mixed precision float16-multipl
1640-44184 77% of the area. As have eliminated the majority of the cost associated with the multiplication, the accumulation accounts for the majority of the remaining arithmetic costs of dot products. These costs can likely be reduced with methods such as chunked accumulation lower precision 29 35 combining multiple operations as done in tensor cores, or the Kulisch accumulation method used in [13]. We have not explored the use of these methods here but conjecture they are likely complementary our approach, just as they have been for standard multiplication.
foatt2-accumulate the costs are 2-0.1+0.9 55% of the energy and 2-137+-4184
1.1++0.9
C Additional Architectures
The main focus of this work is on transformer networks. However we have found that piecewise affine matrix multiplications work well across a range of convolutional architectures. Table shows the results of training five different non-transformer networks on CIFAR-10 10 using piecewise affine matrix multiplications with the approximate bwd pass, replacing all linear and convolutional layers.
14

---

Table 5: Top-1 Test Accuracy on CIFAR- 10 for different networks when trained with standard matrix multiplications piecewise affne matrix multiplications (using approximate bwd). Each value the average-tstd for three runs with different seeds. Brackets show the difference from the baseline.
NETWORK
BASELINE
PA- PA-MATMUL
VGG-13
92.9 + 0.3%
92.9 0.2%
RESNET-20
92.1 0.3%
92.0
= 0.2%
RESNET-110
94.2 1 0.1%
94.1
= 0.2%
RESNEXT-20 4x16
93.7 + 0.2%
93.8+0.11
= 0.2%
CONVMIXER-256/8
94.8 + 0.2%
94.8 0.0 0.1%
In each case we roughly match the baseline (within the run-to-run variance), without any adjustments the hyperparameters.
We selected the five models to demonstrate variety. Here are some of the ways in which they differ:
VGG-13 31 Plain CNN without skip connection or normalization layers. Contains several
fully connected layers the end.
ResNet-20 |I| Model with skip connections and normalization.
ResNet- Model of significant depth.
ResNeXt-20
4x
37
Uses bottleneck blocks and grouped convolutions.
ConvMixer-22667
33 Has a mixer style architecture and uses GeLU activations. The
training setup also uses heavier data augmentation than for the other networks.
The exact details of the training setup used in each case can be found in code.
D PAM with Narrower Mantissas
In this section we explore whether PAM can work with narrower mantissas which would decrease memory read costs and improve effective memory bandwidth. We simulate training with piecewise affine matrix multiplications (approximate bwd) using numerical formats with fewer mantissa bits than the 23 used in float32. We implement this by rounding the inputs and masking the extra mantissa bits, but do not change any other aspects of the training setup (i.e. no tuning special low precision tricks). The internal accumulation left unchanged similar to standard fpl6-fp32 mixed precision. We focus on the training for two tasks, the IWSLT transformer from Section 3.2 and the VGG-13 CIFAR- 10 network from Appendix C The results can be seen in Table 6
For both networks, we observe minimal to no discrepancy when training with 7 bits (equivalent to bfloat16). Mantissas narrow as 4 bits work well, providing comfortable margin for bfloat16 and offering promise for extensions into very narrow formats like 8-bit formats (although these might necessitate additional techniques to accommodate the narrow exponent). However, 3-bit mantissa noticeably impairs the transformer's performance and may marginally impact the VGG training.
Table 6: The impact of the mantissa size of the PAM inputs VGG-13 CIFAR-10 Test Accuracy and IWSLT14 BLEU Score for a small transformer. Each value is the average-Estd for three runs with different seeds.
MATMUL TYPE
C1FAR-10 TEST ACCURACY
IWSLT14 BLEU SCORE
FLOAT32
92.9 + 0.3%
34.4 + 0.1
PAM FLOAT32
92.9 + 0.2%
34.2 0.2
PAM BFLOAT
92.9 1 0.2%
34.4
PAM BIT MANTISSA
92.9 1 0.5%
34.2 0.1
PAM BIT MANTISSA
92.8 + 0.2%
29.4
E
Runtime
Since PAM is not natively supported by the GPUs we use for our experiments, we require multiple instructions for each operation and can not make use of special hardware features such as the tensor
15

---

cores. We can also not use the highly optimized cuDNN and cuBLAS libraries at all, having to write the kernels required ourselves. Overall this can easily slow training down significantly compared to well optimized baselines that fully benefit from the GPU hardware including tensor cores. Here we want emphasize that this not a limitation of the method or our implementation but rather the lack of hardware support for the operation. We would incur a similar slowdown if we wanted to simulate training in a new custom floating point format, like some variant of float16, using only int and float32 operations, A significant effort went into enabling our experiments run at the scale report.
IWSLT14 DE-EN: The baseline runtime is around hour on V100 GPU. With PAM approximate matrix multiplications this number is around 4.5 hours. Replacing all operations results in a runtime of around 5.5 hours.
DeiT ilk and CIFAR-10: The CIFAR-10 10 baseline runs about 4 hours on 4xV100 GPUs. The PAM approximate matrix multiplication version takes around 15 hours. The ImageNet version took 34 hours for the baseline vs 131 hours for PAM matrix multiplications on 6xA GPUs.
Convolutional Networks on CIFAR-10: The runtimes (baseline vs PAM matmuls) are roughly:
VGG-13: 20 min vs 4.5 hours
ResNet-20: 20 min vs 7 hours
ResNet-1100 10: 45 min 10 hours
ResNeXt-20 4x 66: 25 min 10 hours
ConvMixer-22665 20 min vs 5 hours
We note that we did not focus on speeding up convolutions, electing simply perform them as matrix multiplications using relatively inefficient folding operations.
F
Limitations
The scale of typical deep learing problem makes it hard to investigate new low-level hardware algorithms in this field. The existing hardware accelerators that enable common large workloads are also highly specialized and do not necessarily perform well when performing slightly different operations. In this study the scale of the problems we can study is somewhat limited due to the high cost of training. We have tried to address this by writing custom kernels that allow us to run larger problems a reduced cost.
Ideally, we could show direct hardware benefit from the piecewise-affine operations. However, we do not have the expertise to design efficient hardware implementation that fully reaps the hardware advantages. Without significant investments, such an implementation would also be unlikely to allow training the scale demonstrate here. Instead, have tried estimate the potential hardware benefits and view this work as algorithmic evidence to inspire further work in this area.
16


Reviews:
[{"review_id": "q18zcjK1MC", "reviewer": "Reviewer_DF7v", "summary": "This paper presents a method for training deep networks completely without multiplication, via approximating multiplication using piecewise affine operations. The authors show that their method can be used to train modern deep networks, including Transformers.", "questions": "1. What is the wallclock runtime of this method? How would it change with the equivalent of tensor core support for this approximation?", "limitations": "Limited discussion of wallclock characteristics on modern hardware.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper is **extremely** interesting. The ideas are great, and the findings are quite surprising. The results are preliminary but seem quite promising, and the idea is worth exploring in more depth. A future where all neural networks are trained without multiplication sounds very interesting and exciting!", "weaknesses": "Modern deep networks are supported by extensive hardware support, such as tensor cores for matrix multiplication. This means that the algorithms proposed in this paper, although theoretically more efficient, are not more efficient in practice. The paper would be stronger if it were more upfront with these limitations, and measured wallclock of the algorithms on modern hardware. The paper would be stronger with this comparison upfront, especially since \"Hardware-Efficient\" is in the title (an alternate framing, such as \"Multiplication-Free Transformer Training via Piecewise Affine Operations\" would not suffer from this same weakness).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the time spent reviewing our submission and as well as your feedback and suggestions!\n\nWe agree that it would likely have been better to de-emphasize the hardware efficiency and focus more on the multiplication-free aspect. We are unfortunately unable to change the title here, but will give this a serious consideration in the case it is not accepted here.\n\nWe try to discuss the theoretical hardware benefits and current runtime in Appendices B, D and E. Due to the lack of hardware support for PAM operations on GPUs we simulate the PAM arithmetic using multiple INT32 and FP32 instructions for each multiplication. This results in runtimes that are several times slower than an FP32 baseline on the GPUs used. We still think this is a relatively good runtime for a detailed simulation of arithmetic that is not supported in the hardware and spent considerable time on the kernels to enable this. With proper hardware support and a similar tensor core implementation we estimate that the multiplication itself would be on the order of 5-10x cheaper in terms of hardware area and energy cost compared to FP16 (Appendix B). This would allow packing more processors etc on a given chip which should result in increased speeds / wallclock runtime. Other hardware elements required (that we do not focus on here) such as the accumulation and the memory will reduce this number but we believe these can be addressed using orthogonal methods such as narrower floating point formats (global response) and the accumulation approaches discussed in Appendix B."}, {"review_id": "zX8EXqVmqP", "reviewer": "Reviewer_aJYh", "summary": "The paper introduces a novel approach that replaces all multiplications in Transformer training with a cost-effective piecewise affine approximation achieved by adding the bit representation of floating-point numbers. This method allows for a full multiplication-free training of Transformer models, covering linear and nonlinear operations in the forward, backward, and optimization phases. The authors demonstrate that this approximation leads to minimal accuracy degradation across different training scenarios and provide estimates of the potential savings in terms of area and power requirements.", "questions": "- Do authors have any insights on why the exact backward functions yield more training instability and worse performance than the approximated ones?", "limitations": "Please see the weakness section", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "* The paper introduces a new \"multiplication-free training\" scheme that can be applicable to Transformer models and other deep learning architectures. \n\n* Despite its simplicity, the approximation method shows only small gaps and minimal accuracy degradation compared to real values.\n\n* The paper provides a unique way of reducing training costs.", "weaknesses": "While the underlying motivation of replacing all the multiplications with simpler operations throughout the entire training procedure, and the proposed method is appealing, it entails some concerns:\n\n1. It looks like the general concept of piecewise affine approximation is not new and was introduced in Mogami. The authors stress (in L317-324) that the main difference from Mogami is the extension of the piecewise affine approximation to include forward, backward, and optimization, enabling a multiplication-free training procedure. However, the benefits of a multiplication-free network are not so clear for multiple reasons:\n\n  * (1-1) The benefit of applying multiplication-free approximation to non-linear operations is unclear. Non-linear operations are generally compute-bound and constitute only a small portion of the overall inference runtime. Since the proposed method can only reduce the compute cost (not the memory cost), the gain from carrying out those computations without multiplications can be minimal.\n   * (1-2) The suggested benefit of allowing the model to be deployed on hardware without multiplication support (L324) is unclear. The author should provide some real examples, or otherwise, it appears hypothetical. Furthermore, even if we were to design new multiplication-free hardware from scratch, it remains uncertain whether the advantages (in terms of saving area, power, and latency) would be substantial enough to outweigh the noticeable performance degradation from matrix-free optimization and loss computation, as indicated in Table 3. \nThat being said, the author should provide a more thorough comparison between computing linear operations without multiplication (as in Mogami - baseline) and computing the entire training process without multiplication to differentiate their work from prior research.\nOtherwise, it seems more favorable to run Mogami's partial PAM scheme on hybrid hardware with small multiplication units (just so that they can support a few non-heavy linear operations), which would offer a better trade-off between runtime costs and accuracy, as compared to the proposed methodology.\n   * (1-3) Furthermore, since the proposed methodology is targeting training  (where the device must support multiple models) rather than application-specific inference, designing new hardware would require flexibility. The proposed solution relies on multiplication-free hardware, which would restrict the broader applicability of training various/new model architectures (e.g. with new nonlinearity).\n\n\n\n2. The training cost comprises both compute operations and memory operations. Although the authors provide a reasonable estimate of how the proposed method reduces compute cost, it does not mitigate memory cost as all values are still stored in 32-bit precision.\nFor instance, in Figure 7 of [2], which serves as a reference for Table 4 in the paper, it is demonstrated that memory operations consume approximately two orders of magnitude more energy than arithmetic operations even when loading from SRAM. \nGiven that the memory operations can constitute a large portion of the overall runtime cost and the proposed method is not so effective at reducing the cost of memory load/store, the estimate of the overall energy saving provided in the paper remains unclear. \ni.e., If a significant portion of the end-to-end energy consumption comes from memory operations, the savings achieved through computation reduction might be minimal.\n\n3. Several methodologies have been proposed for efficient training using reduced-precision approaches (such as bfloat16, which has already been settled down as the norm [3], or integer-only training [4] even though it is not for Transformer training), and this should also be considered as the baseline to compare against. \nThese methods not only decrease compute costs but also reduce memory costs. \nIn terms of end-to-end energy and latency reduction, would the proposed method offer greater benefits compared to these existing methods? \nConsidering the additional requirement for kernel/hardware design of the proposed method (versus reduced-precision training), the author should provide enough evidence that proves the overall gain to be considerably better than those methods to convey its practical value.\n\n[1] Full Stack Optimization of Transformer Inference: a Survey, https://arxiv.org/pdf/2302.14017.pdf\n\n[2] A Survey of Quantization Methods for Efficient Neural Network Inference, https://arxiv.org/pdf/2103.13630.pdf\n\n[3] A Study of BFLOAT16 for Deep Learning Training, https://arxiv.org/pdf/1905.12322.pdf\n\n[4] NITI: Training Integer Neural Networks Using Integer-only Arithmetic, https://arxiv.org/pdf/2009.13108.pdf", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Many thanks for your time and the feedback you've given. Below we try to address the main concerns you list one by one.\n\n**Fully multiplication free (1)** You are correct that from a hardware perspective focusing on the matrix multiplications (on both the forward and backwards passes) may be sufficient to reap most of the benefits for certain network and hardware architectures. In this work we show an approach like this can work across a variety of architectures including transformers (which has not been shown previously) before extending it to fully multiplication-free training. We also release code to enable further exploration of this area. \n\nBeing fully multiplication free may in some ways be of more academic interest for now (for current hardware and architectures). We still believe it is a valid question to ask given the complete reliance of current hardware and training schemes on multiplications. We show that this does not need to be the case and training entirely without multiplications is in fact viable. Future networks and training schemes could enhance its practical relevance. For example, architectures with a more limited connectivity which skew the ratio of matrix computation to other operations might be of interest on new hardware. The benefit of depth-wise separable and grouped convolutions over their dense variants could indicate that this is the case. The loss function is the only significant contributor to the modest performance decrease from the fully multiplication free scheme and affects a network with standard multiplications the same way. Deviating further away from the standard loss function might mitigate this, e.g. using base 2 logarithms and exponents which we can approximate much better using the piecewise linear framework (we discuss this as a future direction in L345). The fully piece-wise affine approximations might also be of interest in other non-hardware related areas such as the network analysis brought up by Reviewer WjDg.\n\nIt is also correct that training hardware might need to support a variety of possible models. Hardware such as FPGA could potentially perform fully multiplication free training while still supporting a variety of architectures. The fully multiplication free approach also extends to inference applications where specialized accelerators may be more feasible.\n\n**Memory Costs and Reduced Bitwidths (2) and (3)** Thank you for pointing this out. We have added an experiment (see global response) that suggests that PAM can be used with narrower formats such as bfloat16 and even fewer mantissa bits. This should give memory access and bandwidth savings similar to other approaches as well as further reduce the computational costs. The area savings from the cheaper multiplication could also be used for other purposes such as memory.\n\n**Exact vs approximate bwd** The approximate backward functions seem to better approximate the gradients of true multiplication in some ways. The exact derivatives give unbiased gradient estimates (of true multiplication) but can deviate more at a given location. The approximate derivative is potentially biased but typically closer to the true multiplication derivative. Figure 3 (Appendix A) plots the two types of derivatives for a visual comparison. Since PAM approximates multiplication over the long term, the gradients of true multiplication could better describe how the loss surface changes over longer distances. These gradients, and by extension the approximate gradient, could therefore serve as a “smoothed” or denoised gradient that aids optimization.\n\n**General remark** In this manuscript, we have explored the question of whether neural networks can be trained in a fully multiplication-free fashion. We believe this is an interesting academic question in itself and could also hold practical relevance, whether by focusing solely on matrix multiplications (as demonstrated for various new architectures) or by fully eliminating all multiplications. The space savings achieved from the more economical multiplication replacements could be allocated to other purposes, including bandwidth and memory improvements. While we don't address every issue involved in the bigger picture, we believe our results present a viable path for future hardware improvements and are of interest to the community. We will include the results for the narrower floating-point formats in an appendix. If you feel that we have addressed some of your concerns, we would greatly appreciate it if you would consider slightly increasing your review score.\n"}, {"review_id": "qvxU8b4xto", "reviewer": "Reviewer_MZyL", "summary": "This paper proposes to replace all multiplications involved in a Transformer training process with bit additions of input floating-point representations. This is shown to be an approximation to the piecewise affine function that is again the approximation of common functions in Transformer training. Results show that this approximation will not cause obvious accuracy drop.", "questions": "Questions are listed together with the main concerns in the previous section.", "limitations": "The reviewer is not aware of any social impact of this paper.", "rating": 5, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "The idea of multiplication-free training is very interesting, and, if true, is significant. The bit-addition as an approximation is concise on both algorithm and hardware side.", "weaknesses": "My main concerns are detailed as follows:\n\n1. There needs to be a better presentation in Section 2.2 on how piecewise affine multiplication (PAM) is reduced to bit-addition. At least the paragraph of line 106 is not obvious to the reviewer. For example, when EA=5, EB=5, SA=SB=MA=MB=0, the two floating-point numbers (now actually integers) A * B = 32 * 32 = 1024, but EA+EB+MA+MB+SA+SB = 10, which clearly doesn't equal and the results have a large gap.\n\n2. In terms of performance (latency), is the bit-addition of floating-point representations (population count) better than multiplication? The Wallace tree implementation of multiplication has a time complexity of O(log(b)), seems like the same as the bit-addition.\n\n3. Is the proposed method compatible with low-precision integer/floating-point formats? What would be the comparison between a quantized matmul and PAM?\n\n4. The setup of results in Table 2 is confusing. It reports the training accuracy with only the matmul replaced with PAM, which is the same as the prior work Mogami (2020). What are the results with all layers replaced with PAM, especially with all optimizer ops replaced?\n\n5. For Table 3 machine translation results, what are the model architecture details, e.g., number of parameters, layers, heads, etc.? What is the activation function used in the FFN (GELU or ReLU)? Is it replaced with PAM as well? It is also better to report loss values besides BLEU since BLEU is typically noisy.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and effort in reviewing our paper! Below we try to address your concerns and feedback.\n\n**(1) PAM as bit addition** We apologize that this can be misunderstood and propose rephrasing this paragraph as: We observe that Aˆ· B is roughly achieved by adding the signs (Equation 6), exponents (Equation 7), and mantissas (Equation 8) of A and B. If we add the floating point representations of A and B given in Equation 3 together as integers, the extra term of 1{M_A + M_B>1} in Equations 7 and 8 corresponds to an overflow of the resulting $\\bar{M}$ into $\\bar{E}$. Piecewise affine multiplication can therefore be performed by an int32 addition of the floating point representations, barring some technical details we discuss next.\n\nWe hope this clarifies that in your example the addition would be carried out as PAM([0, 5, 0], [0, 5, 0]) = [0+0, 5+5, 0+0] = [0, 10, 0] = 1024 which gives the exact result (this is generally the case when one operand is an exact power of two).\n\n**(2) Latency** This is not our area of expertise so we apologize if we misunderstood your point or if there are errors in the following answer. If we understand correctly, a Wallace tree implementation concerns the implementation of an integer multiplication through a tree-like reduction of the partial products. The depth of the tree is O(log2(b)) where b is the bit width of the integers. Each addition in the tree operates on integer inputs with a width of at least b. The PAM operation (for floats) can be expressed as a single full width int addition (similar to one level of the Wallace tree) followed by a fix of the exponent (int8 addition) and handling for underflow / overflow of the exponent. In Appendix B we approximate the total cost as being around 2 full-width integer additions. If this holds, the latency could perhaps be modeled as around 2 levels of the Wallace tree resulting in a lower latency. Even if this turns out not to be the case, the resulting area savings would still be beneficial by freeing up area for other uses.\n\n**(3) Lower precision floats** Yes, we believe the method should work with lower width floats such as bfloat16. We have added a global response to discuss additional experiments that support this. We believe for 16 bit formats PAM should be roughly 5-10x cheaper than standard multiplication.\n\n**(4) Table 2** In Section 3.2 and Table 2 we only replace the matrix multiplication. This allows us to compare directly to AdderAddention, an alternative approach for replacing multiplications in transformer training, showing better performance while replacing more multiplications. In Section 3.3, 3.4 and Table 3 we extend this, studying the impact of replacing all operations individually and cumulatively. This is done on a computationally cheaper task allowing us to run different combinations and obtain error bars.\n\n**(5) Table 3** In the manuscript we describe the setup used in this experiment in Lines 204-213. The network is based on the original transformer architecture and has 6 encoder and 6 decoder layers with ReLU activations. Thank you for the suggestion of additionally reporting the loss. It seems like a good idea in general but in this we think it could potentially be misleading since we use a different loss function for some of the table entries (i.e. the piecewise affine approximation).\n\nWe will incorporate your feedback, clarifying the points and adding the results for lower bit widths. If you feel we have sufficiently addressed some of your concerns, we would greatly appreciate it if you would consider raising your review score.\n"}, {"review_id": "8FwYRiSXUQ", "reviewer": "Reviewer_WjDg", "summary": "This paper argues that multiplications are the main bottleneck in modern neural network training and inference, and proposes to reduce the cost by replacing them with a cheap piecewise affine approximation. This can eliminate all multiplications in the training and inference process as claimed.", "questions": "* Such a piece-wise linear approximation of multiplications can be seen as an approximation of a network. There are also other works that leverage piece-wise linear approximation to visualize and analyze the decision boundary or spline subdivisions. Are there any connections between these kinds of works? E.g., https://arxiv.org/abs/2302.12828, https://arxiv.org/abs/2101.02338", "limitations": "This paper gives an analysis of the limitation on the GPU speedups.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "* I think that this work has its value. It is a new type of multiplication-free network following addernets, shiftnets, or shiftaddnets. And it can be applied to both inference and training.\n\n* The author has implemented a customized CUDA kernel for supporting their claims. And the final results are similar to the original networks.", "weaknesses": "* This paper claims to be the first work to reveal that a neural network has been trained entirely without standard multiplications. In my opinion, it overclaims as there are other multiplication-free networks with no multiplication involved during training or inference.\n\n* The author only compares the accuracy but does not report the latency or efficiency metrics. That looks weird as the main motivation for adopting multiplication-free networks is to reduce the training or inference costs.\n\nI also wonder about the speed comparison of the customized CUDA kernel and origin networks. Which will be faster (even for the FPGA case)? As in modern hardware, the computation is no longer the bottleneck as compared to data movements.\n\n* How is the performance as compared to other multiplication-free/reduced networks in terms of accuracy and efficiency, e.g., addernet, deepshift, shiftaddnas, Ecoformer, and other binary neural networks?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the time spent reviewing our submission as well as your feedback and suggestions! Below we try to address your concerns and questions.\n\n**Other multiplication-free works** We apologize if this is an overclaim, that was definitely not our intention. We are aware of other works e.g. AdderNet that can be multiplication free at inference which we mention in the paper. For training specifically, we are not aware of other schemes that are 100% multiplication free. We would be grateful if you can provide a reference and will include it in the paper and tone our claims down accordingly. Regarding the specific references you mention later in your review, although they are impressive works and able to remove most multiplications, they do include some leftover multiplications during training. They seem to use standard optimizers with the associated multiplications and do not try to address the multiplication in e.g. normalization when used. AdderNet relies on Batch Normalization including the learnable affine transformation. Deepshift can eliminate the multiplications involving the weights but if we understand correctly the computation of the gradient for a weight requires standard matrix multiplication. We believe ShiftAddNAS inherits this from the other papers. EcoFormer seems to address the attention matrix multiplication specifically but leaves the others unchanged. We will add these as references when we discuss related work.\n\n**Latency or efficiency metrics metrics** This is something we would have liked to include but the current lack of hardware support for these operations prevents us from giving a meaningful comparison. We currently simulate the arithmetic on GPUs using fp32 and int32 operations which will always be slower than the standard baseline. Note that this is not a limitation of the method itself, accurately simulating e.g. bfloat16 multiplication on hardware that only supports fp32 multiplications would also result in a similar slowdown. With proper hardware support we estimate a PAM operation to be around 5-10x cheaper than an fp16 multiplication in terms of energy and area (Appendix B). Other hardware elements required (that we do not focus on here) such as the accumulation and the memory will reduce the overall gains.\n\n**Comparison with other methods** While we can’t do an exhaustive comparison with all these methods we do compare to AdderAttention which is an extension of AdderNet for transformers (Section 3.2, Table 2). The AdderNet approach is very interesting and deviates from the traditional networks in a more drastic way. However, the PAM approach replaces more multiplications (all matrix multiplications), uses a cheaper replacement operation (integer additions instead of floating point) while resulting in a higher accuracy. We discuss some differences with the other works in the “other multiplication-free works” paragraph.\n\n**Memory Characteristics** Thank you for bringing this up. You are correct that our method only focuses on the cost of multiplication itself but other aspects of computation such as memory accesses also contribute to the overall cost. In the global response we discuss additional experiments that suggest that PAM is compatible with lower precision floating point formats that would result in memory savings as well as further computational savings. The large area savings from PAM could also be used for other purposes including additional memory.\n\n**Relation to other piece-wise linear works** This is a very interesting connection, thank you for pointing this out. Although their methods can already handle standard multiplications, it seems they are limited to piece-wise linear non-linearities such as leaky ReLUs. The piece-wise affine approximations like those we use for normalization layers and softmax might expand the applicability of their work to a broader range of architectures such as transformers, although we are not sure about the computational tractability in practice."}]

Author rebuttal:
# Global Response
We are grateful to the reviewers for their efforts, insightful comments and constructive suggestions. We respond to all reviews individually. In this response we discuss the compatibility of PAM with lower precision formats, a question raised by several reviewers. In the manuscript we mention that we believe PAM should work with narrower mantissas but did not perform experiments to validate this. Narrower mantissas would yield further computational savings as well as memory savings (including storage, read costs and bandwidth).

To address this concern we have performed an additional experiment where we simulate training with piecewise affine matrix multiplications (approximate bwd) using numerical formats with fewer mantissa bits than float32. We achieve this by rounding the inputs and masking the extra mantissa bits but do not change any other aspects of the training setup (i.e. no tuning or special low precision tricks). The internal accumulation is left unchanged similar to standard fp16-fp32 mixed precision. We focus on the training for two tasks, the IWSLT transformer from Section 3.2 and the VGG-13 CIFAR-10 network from Appendix C. The results can be seen in the table below (average±std for three runs).

For both networks, we observe minimal to no discrepancy when training with 7 bits (equivalent to bfloat16). Mantissas as narrow as 4 bits work well, providing a comfortable margin for bfloat16 and offering promise for extensions into very narrow formats like 8-bit formats (although these might necessitate additional techniques to accommodate the narrow exponent). However, a 3-bit mantissa noticeably impairs the transformer's performance and may marginally impact VGG training.

| Matmul Type      | VGG-13 Test Accuracy | IWSLT14 BLEU Score |
| ----------- | ----------- | ----------- |
| float32 | 92.9±0.3% | 34.4±0.1 |
| PAM float32 | 92.9±0.2% | 34.2±0.2 |
| PAM bloat16 | 92.9±0.2% | 34.4±0.2 |
| PAM 4 bit mantissa | 92.9±0.5% | 34.2±0.1 |
| PAM 3 bit mantissa | 92.8±0.2% | 29.4±0.5 | 

We will add these results to a new appendix section.


Meta-review: The reviewers all recommend acceptance. Having looked at the paper, reviews, and rebuttal, we are accepting this paper. The authors are encouraged to improve the final paper version by following reviewer recommendations.
Decision: Accept (poster)