On the quantization of recurrent neural networks

Matrix multiplication ("matmul") is a basic operation in neural networks, including the LSTM. It can be defined as a binary operation on two input matrices to produce a third one such that $c_{(}i_{k})=a_{ij}b_{jk}$ where $j$ is accumulated over for all possible values of $i$ and $k$. Relevant to our work is that its overflow behavior can be modeled via a random walk, and a safe accumulation depth can be calculated. For example, in a typical "matmul" operation with inputs comprised of signed 8 bit integers (int8) that accumulate into a resulting signed 32 bit integer (int32), there is no possibility of overflowing in $2^{15}$ steps. However, a 24 bit accumulator has only a safe accumulation depth to $2^{7}$.

Thus, so as long as the dimension of the tensors in the model are smaller than that upper limit of steps, then the "matmul" computations used to execute the model are safe from accumulator overflowing. Empirically we have found that, with constraints of "matmul" operations on int8 values to a int32 accumulator, most models [6, 21, 7] are safe from overflow.

When overflows do occur, in some cases, saturation can solve the overflow issue. For example, when the operation is followed by a sigmoid function, clamping error due to saturation is negligibly small outside a proper range such as $[-8,8]$ (see section 3.2.1). However, in other cases, overflow can harm accuracy and should be avoided. Common ways to avoid overflow (though not entirely guaranteed) are using quantization simulation during training [7, 22], or by selecting a good calibration dataset when post-training quantization is used [23].

The main take away we want to convey here is that overflow and saturation behaviour needs to be modeled carefully, and thus is a key driver of the decisions (described later in the document) in our proposed quantization strategy.

While in Equation 8 we define the scale as a real number, in practice we approximate them as rational numbers defined as power-of-two scales to operate in the fixed-point domain, and because computation involving power-of-two values can be more efficiently implemented in digital computers as bitwise operations.

We make use of the $Q_{m.n}$ number format [24], where the integer numbers $m$ and $n$ represent the number of integer and fractional bits, respectively. More specifically, in this work $Q$ itself denotes signed fixed-point numbers and follows the conversion that $m+n+1$ equals the bit-width of the type.

This means that $Q_{m.n}$ can represent floating-point values within range of [$-(2^{m})$, $2^{m}-2^{-n}$], with a resolution of $2^{-n}$.

Non-linear activation functions $\sigma$ (see eq 1, eq 2, eq 5) and $g$ (see eq 4) have restrictions on input and output scales so their scales need to be decided first.

For the activation functions, we utilize 16 bits since we found that given their scalar nature we need the higher precision to ensure the overall accuracy of the LSTM across different types of models and tasks. Additionally, $Q_{m.15-m}$ is used as the input and output scale for activations.

For the output of activation functions, $Q_{0,15}$ is selected since it maps nicely to the output range of $\sigma$ and $tanh$. The output values are slightly clamped at $[-1,\frac{32767}{32768}]$ and experimentally no accuracy loss is observed (see section 5 for more details).

There are clamping errors and resolutions for activations. The max of clamping error is $f(\infty)-f(2^{m})$. Take $tanh$ as an example, if we restrict the input of $tanh$ to $[-8,8]$ ($Q_{3.12}$), there is a clamping error of $1-tanh(8)=2.35e-7$. Resolution error is the error from representing all values in the quantization "bucket" with one quantized value. The maximum value of resolution error is $2^{-n}max(f^{\prime}(x))$, where $max(f^{\prime}(x))$ is the max value of the derivitive of $f$. Take $tanh$ as an example, the max resolution error happens at $x=0$ (max gradient) with values $tanh(2^{-12})=2.44e-4$.

When $m$ becomes bigger, clamping error is reduced but resolution error is increased and becomes dominating; when $m$ becomes smaller, clamping error is dominating. The value $m$ in $Q_{m.15-m}$ for input of activations is determined by balancing the two errors. Working out the math for both $tanh$ and $sigma$, $Q_{3.12}$ has the lowest error.

Cell state $c$ is the internal memory of LSTM cell. Because it persisits accross multiple invocations and mainly involves scalar operations, 16 bits is needed to preserve accuracy.

Cell state is used in 3 places:

• •

  as input to elementwise $tanh$.

• •

  as input to elementwise multiplication with forget gate.

• •

  as input to elementwise multiplication for peephole connection.

We cannot clamp cell state to $[-8,8]$ because it is also used in multiplications. Instead, we extend the measured range to the next power-of-two values and symmetrically quantize it to 16 bits. For example, suppose cell is measured to be in the range of $[-3.2,10]$, we extend that to $[-16,16)$, which leads to quantization with $Q_{4.11}$. And in this case, even though $Q_{3.12}$ is still the best input format for $tanh$, we can directly use $Q_{4.11}$ as input to $tanh$ to remove the unnecessary rescaling.

Peephole connection $P\odot c^{t-1}$ is the optional connection from cell state to gates (see fig 1). Since the multiplication between the 16 bit state and the peephole coefficients are elementwise, we symmetrically quantize the peephole coefficients to $[-32767,32767]$ with scale $s=\frac{range(max(P))}{32767}$ and store it as int16. The lack of 16bit-8bit multiplication instruction in ARM neon further deminish the need to quantize peephole weights to 8 bits.

There are four gates in one LSTM cell: input (eq 1), forget(eq 2), update(eq 3) and output(eq 5). Without layer normalization, gate calculation is $Wx^{t}+Rh^{t-1}+P\odot c^{t-1}+b$. As disucssed above, $P$ and $c^{t-1}$ are 16 bits. For the matrix multiplication operations, 8 bit values and operations are sufficient because the quantization errors are expected to statistically cancel during the accumulation. $W$ and $R$ are symmetrically quantized to [-127, 127] with scale $s_{W}=\frac{max(abs())}{127}$ and stored as int8. $x$ and $h$ are asymmetrically quantized to [-128, 127] with scale $s_{x}=\frac{max()-min()}{255}$ and stored as int8. In practice, to ensure float zero point is mapped to an integer, $max(x)$ and $min(x)$ are lightly nudged [7] in the asymmetric case.

$Wx^{t}$ and $Rh^{t-1}$ are accumulations over the product of two int8 so int32 is used to accumulate the result. For $P\odot c^{t-1}+b$, even though there is no accmulation, int32 is needed for the product of two int16. So the results of $Wx$, $Rh$ and $P\odot c$ are stored using three 32 bit accumulators and they have different scales.

Bias is elementwise added to the accumulator so we choose to qunatize that to 32 bits. Quantized bias needed to be added before rescaling and it can use scale of any of the 3 accumulators. In the models we tested on, $s_{R}s_{h}$ is the smallest out of $s_{W}s_{x}$, $s_{R}s_{h}$ and $s_{P}s_{c}$ so it provides the best resolution. So bias is symmetrically quantized with scale $s_{R}s_{h}$ to $[-(2^{31}-1),2^{31}-1]$ and stored as int32.

As discussed in the activation 3.2.1, without layer normalization, the overall $Wx^{t}+Rh^{t-1}+P\odot c^{t-1}+b$ uses $Q_{3.12}$ as scales so it’s symmetrically quantized with scale $s=2^{-12}$ to $[-32768,32767]$ and stored as int16.

Figure 2 shows the quantization details of the gates.

The three int32 accmulators need to be rescaled to the output scale $s=2^{-12}$ before being added together. To rescale the accumulators, an effective scale is calculated $s_{effx}=2^{12}s_{W}s_{x}$ which is the ratio between the accmulator scale and the output scale. Similarly $s_{effh}=2^{12}s_{R}s_{h}$ and $s_{effc}=2^{12}s_{P}s_{c}$ can be calculated.

The gate integer execution becomes $\textsf{rescale}(W(x+zp),s_{effx})+\textsf{rescale}(R(h+zp)+b,s_{effh})+\textsf{rescale}(Pc,s_{effc})$. This is visualized in figure 3.

In the presence of layer normalizatoin, the gate calculation becomes $Wx+Rh+P\odot c$ and the bias is applied after normalization. Same as the cases without layer normalization $W$, $x$, $R$, $h$ are quantized to 8 bit and $P$ and $c$ are quantized to 16 bit. Because the output of the gate is not consumed by activations, we cannot use $2^{-12}$ as the output scale. Instead the output scale is calculated from measured values: $s=\frac{max(abs(Wx+Rh+P\odot c))}{32767}$. The quantized values are mapped to [-32767, 32767] and stored as int16. The quantization is shown in figure 5.

Same as the non layer normalization case, three effective scales ($s_{effx}$, $s_{effh}$, $s_{effc}$) are calculated. Integer execution is $\textsf{rescale}(W(x+zp),s_{effx})+\textsf{rescale}(R(h+zp),s_{effh})+\textsf{rescale}(Pc,s_{effc})$, which can be visualized in figure 6.

Layer normalization [20] $norm()\odot L+b$ is widely used in streaming use cases. It normalizes the activation vector therefore prevents the model from overall shifts caused by the gate matrix multiplication, which is one of the primary source of accuracy degradation for LSTM cell quantization.

Layer normalization normalize $x$ to $x^{\prime}$ with zero mean and unity standard deviation and then applies layer normalization coefficients and bias.

	$\displaystyle\bar{x}=\frac{\sum_{i=1}^{n}(x_{i})}{n}$		(10)
	$\displaystyle x_{i}^{{}^{\prime}}=\frac{(x_{i}-\bar{x})}{\sqrt{\frac{\sum_{i=1}^{n}(x_{i}^{2}-\bar{x}_{i}^{2})}{n}}}$		(11)
	$\displaystyle y_{i}=x_{i}^{{}^{\prime}}*L_{i}+b_{i}$		(12)

The float calculation is shown in fig 7

The output of normalization $x^{\prime}$ is limited to a small range. Assuming normal distribution, 99.7% of values in $x_{i}^{{}^{\prime}}$ is confined between $[-3.0,3.0]$ which is roughly 2.8 bits in the integer presentation. This leads to catastrophic accuracy degradation in the model. Increasing bits and/or adjusting scales of the input of normalization would not help because any scale would be cancelled since it appears in both the numerator and denominitor in the calculation of $x_{i}^{{}^{\prime}}$.

Instead, we solve the challenge by adding a scaling factor $s^{\prime}$ to $x^{\prime}$ in the computational graph. With $x_{i}^{{}^{\prime}}=q_{i}^{{}^{\prime}}s^{\prime}$, the quantized value $q_{i}^{{}^{\prime}}$ can now be expressed as $q_{i}^{{}^{\prime}}=\frac{x_{i}^{{}^{\prime}}}{s^{\prime}}=\frac{(q_{i}-\bar{q})}{\sqrt{\frac{\sum_{i=1}^{n}(q_{i}^{2}-\bar{q}_{i}^{2})}{n}}}\times\frac{1}{s^{\prime}}$. $s^{\prime}$ is chosen to be the smallest power-of-two number that won’t cause overflows in $q_{i}^{{}^{\prime}}$, which is $2^{-10}$ in our experiments. With $s^{\prime}$ determined, the integer inference becomes [21]:

	$\displaystyle\bar{q}=round(\frac{\sum_{i=1}^{n}(2^{10}q_{i})}{n})$		(13)
	$\displaystyle\sigma=\sqrt{\frac{\sum_{i=1}^{n}(2^{20}q_{i}^{2}-\bar{q}_{i}^{2})}{n}}=\sqrt{\frac{2^{20}}{n}\sum_{i=1}^{n}q_{i}^{2}-\bar{q}_{i}^{2}}$		(14)
	$\displaystyle q_{i}^{{}^{\prime}}=round(\frac{(2^{10}q_{i}-\bar{q})}{\sigma})$		(15)
	$\displaystyle q_{i}^{{}^{\prime\prime}}=round(\frac{q_{i}^{{}^{\prime}}q_{Li}+q_{bi}}{2^{10}})$		(16)

$q_{L}$ is the quantized value of weight and $q_{b}$ is quantized value of bias. Layer normalization weights are symmetrically quantized with scale $s_{L}=\frac{range(L)}{32767}$ to [-32767, 32767] and stored as int16. Bias is symmetrically quantized with scale $s_{b}=2^{-10}s_{L}$ to $[-(2^{31}-1),2^{31}-1]$ and stored as int32. The quantization of layer normalization is shown in fig 8 and the integer execution is shown in fig 9.

The new cell state $c^{t}$ is calculated using the old cell state $c^{t-1}$ and input gate, forget gate and update gate through $c^{t}=i^{t}\odot z^{t}+f^{t}\odot c^{t-1}$. As shown in fig 11, the 3 gates all have $Q_{0.15}$ as scale and cell has $Q_{m.15-m}$ as scale. The quantized execution from gate to cell is $c^{t}=\textsf{shift}(i^{t}\odot z^{t},30-m)+\textsf{shift}(f^{t}\odot c^{t-1},15)$

Hidden state $m^{t}=o^{t}\odot g(c^{t})$ is the element wise product between the output gate and cell state. Hidden state is mathmatically bounded to $[-1,1]$ because it is the product of two values that are bounded to $[-1,1]$. Experimentally we have observed that using the measured range instead of $[-1,1]$ improves accuracy. So the hidden state is quantized asymmetrically with scale $s_{m}=range(m)/255$ to [-128, 127] and stored as int8.

From cell to hidden state $m$, an effective scale of $s_{eff}=2^{-30}/s_{m}$ is calculated and the integer execution is $m=\textsf{rescale}(o\odot g(c),s_{eff})-zp$. The overallinteger execution from gate to hidden state is shown in fig 12.

Projection $h^{t}=W_{proj}m^{t}+b_{proj}$ is the optional connection that projects the hidden statee $m$ to output $h$. $W$ is symmetrically quantized with scale $s_{w}=max(abs(W_{proj}))/127$ to [-127, 127] and stored as int8. Bias $b_{proj}$ is symmerically quantized with scale $s_{b}=s_{w}*s_{m}$ to $[-(2^{31}-1),2^{31}-1]$ and stored as int32. $h$ is asymmetrically quantized with scale $s_{h}=range(h)/255$ to [-128, 127] and stored as int8. This is shown in fig 14.

Similarly, with effective scale $s_{eff}=s_{W_{proj}}*s_{m}/s_{h}$, the integer execution is $h=\textsf{rescale}(W_{proj}(m+m_{zp})+b,s_{eff})-h_{zp}$ and is shown in fig 15.

With CIFG, the input gate and forget gate are coupled: $i^{t}=1-f^{t}$. In the quantized case, because input and forget gate have $2^{-15}$ as scale, the coupling becomes $i^{t}=max(32768-f^{t},32767)$. The extra clamping is to make sure the result can fit in int16. And becasue the forget gate is clamped slightly to $[0,\frac{32767}{32768}]$ (instead of $[0,1]$), input gate is clamped to $[\frac{1}{32768},\frac{32767}{32768}]$ for CIFG.