# NF4 Isn’t Information Theoretically Optimal (and that’s Good)

Davis Yoshida
Toyota Technological Institute at Chicago, IL, USA, 60637
<EMAIL_ADDRESS>
###### Abstract

This note shares some simple calculations and experiments related to absmax-
based blockwise quantization, as used in Dettmers et al. (2023). Their
proposed NF4 data type is said to be information theoretically optimal for
representing normally distributed weights. I show that this can’t quite be the
case, as the distribution of the values to be quantized depends on the block-
size. I attempt to apply these insights to derive an improved code based on
minimizing the expected L1 reconstruction error, rather than the quantile
based method. This leads to improved performance for larger quantization block
sizes, while both codes perform similarly at smaller block sizes.

##  1 Introduction

Figure 1: For varying $B$, the 16 values of AF4-$B$, a code based on
minimizing expected L1 quantization error. At higher block sizes the values to
be quantized will cluster more tightly around the origin, so the code values
should as well. Horizontal lines are the NF4 (Dettmers et al., 2023) code
values, the vertical line shows the default NF4 block size of 64.

This note will go over some theoretical calculations and empirical findings
regarding quantization using the NF4 data type of Dettmers et al. (2023). I
want to stress that while I am pointing out some theoretical issues, they
don’t have any bearing on the _empirical_ results of Dettmers et al. (2023),
since all that matters at the end of day is how well a model performs post-
quantization.

A brief summary of my findings is: (1) The distribution of values to be
quantized depends on the quantization block size, so an optimal code should
vary with block size (2) NF4 does not assign an equal proportion of inputs to
each code value (3) Codes which _do_ have that property are not as good as NF4
for quantizing language models.

In Section 5, I propose a code (shown in Figure 1), which takes these facts
into account, but it only consistently outperforms NF4 for larger block sizes
in preliminary experiments.

##  2 Background

The NF4 datatype is used to quantize values in the interval $[-1,1]$. Since
NF4 is a 4-bit code, it consists of 16 values, $q_{1},\dots,q_{16}\in[-1,1]$.
Each block of $B$ values of a matrix $W$ is quantized into NF4 values:

  1. 1.

Given $w_{1},\dots,w_{B}$, calculate the _absmax_ : $M=\max\limits_{i}|w_{i}|$

  2. 2.

Calculate a code index, $c_{i}$ for each parameter by mapping each $w_{i}$ to
the nearest $q_{j}$ after downscaling by $M$:

$c_{i}=\operatorname*{argmin}\limits_{j}|q_{j}-w_{i}/M|$

In addition to the 4-bit NF4 values, the absmax $M$ is stored for each block.
When $W$ is used in a computation, blocks are dequantized by computing
$w_{i}\approx q_{c_{i}}M$.

Dettmers et al. (2023) show that neural network parameters are approximately
normally distributed. Motivated by this, they calculate the values of $q_{j}$
based on the quantiles of the normal distribution. Their construction
is:111The implementation can been found here in the create_normal_map
function.

  1. 1.

Set $\delta=\frac{1}{2}\left(\frac{1}{32}+\frac{1}{30}\right)$.

  2. 2.

Compute 8 evenly spaced probability values $p_{1},\dots,p_{8}$ such that
$p_{1}=\delta$ and $p_{8}=1/2$.

  3. 3.

Find their pre-images under the Gaussian CDF, $\Phi$:
$\tilde{q}_{i}=\Phi^{-1}(p_{i})$ for $i=0,\dots,8$.

  4. 4.

Compute 9 even spaced probability values $r_{8},\dots,r_{16}$ such that
$r_{8}=1/2$ and $r_{16}=1-\delta$.

  5. 5.

Set $\tilde{q}_{i}=\Phi^{-1}(r_{i})$ for $i=9,\dots,16$ (note that $r_{8}$ is
unused since $\tilde{q}_{8}$ was already set to 0)

  6. 6.

Normalize the $\tilde{q}$s to the range $[-1,1]$ to get the final code:
$q_{i}=\frac{\tilde{q}_{i}}{\max\limits_{i}|\tilde{q}_{i}|}$.

This results the NF4 code: a set of values in $[-1,1]$, with $q_{1}=-1$,
$q_{8}=0$, $q_{16}=1$.222The reason the the values are computed in two
asymmetric groups is that 0 would not be included in a symmetric code. The
largest $\tilde{q}$ value is $\Phi^{-1}(1-\delta)\approx 1.848$, so the final
$q$ values are quantiles of an
$\mathcal{N}\left(0,\frac{1}{\Phi^{-1}(1-\delta)}\right)$ distribution.

##  3 Increased block size concentrates the inputs

Figure 2: Estimates of the density of $X_{i}$ for varying values of $B$. Each
plot uses $2^{20}$ draws of $B$ values.

To allow theoretical analysis of this quantization method, consider the
following generative story for $X_{1},\dots,X_{B}$:

$\displaystyle Z_{1},\dots,Z_{B}$ $\displaystyle\sim\mathcal{N}(0,1)$
$\displaystyle M$ $\displaystyle=\max\limits_{i}|Z_{i}|$ $\displaystyle X_{i}$
$\displaystyle=\frac{Z_{i}}{M}$ (1)

This models quantizing samples from a normal distribution in groups of $B$.
The $X_{i}$ are identically distributed, but there is dependence introduced by
the division by $M$.333E.g. $P(X_{1}{=}1)=1/2B$, but
$P\left[X_{1}=1\>\middle|\>X_{2}=1\right]=0$

###  3.1 One code cannot be optimal for all block sizes

The 16 NF4 codepoints do not depend on $B$, but the distribution of the
$X_{i}$s above does. Figure 2 shows estimates of the density of this
distribution for various values of $B$. The distribution is a mixed
distribution, since with probability 1 exactly one $X_{i}$ obtains either the
value -1 or 1. So, each $X_{i}$ (non-independently) has a probability of
$1/2B$ of falling on one of those two values. More importantly, the
distribution concentrates around the origin as $B$ is increased.

The relationship of this to the selection of code values can be seen through a
brief example. Consider using a block size of 4096, which corresponds to one
row of an attention projection matrix in the LLaMA-7B model (Touvron et al.,
2023). We can show that the larger code values such as $q_{15}$ will barely be
used at all.

Let $\operatorname{\text{\TH}}(\cdot)$ be the CDF of the half-normal
distribution444“Þ” is the chracter “thorn”. $M$ has CDF
$\operatorname{\text{\TH}}^{4096}(\cdot)$, which may be used to compute its
median, $m_{B}$:

$\displaystyle m_{B}$
$\displaystyle=\operatorname{\text{\TH}}^{-1}\left(\left(\frac{1}{2}\right)^{1/4096}\right)$
$\displaystyle\approx 3.76$

The largest value in $[-1,1]$ which is assigned to $q_{14}$ in the NF4 code is
slightly smaller than 0.65. When $M$ attains its median value, the fraction of
samples assigned to $q_{15}$ and $q_{16}$ will be:

$\displaystyle P$ $\displaystyle\left[X_{i}>0.65\>\middle|\>M=3.76,X_{i}\neq
M\right]$
$\displaystyle=P\left[Z_{i}>\left(0.65\right)\left(3.76\right)\>\middle|\>-3.76<Z_{i}<3.76\right]$
$\displaystyle=\frac{P\left[\left(0.65\right)\left(3.76\right)<Z_{i}<3.76\right]}{P(-3.76<Z_{i}<3.76)}$
$\displaystyle=\frac{\Phi(3.76)-\Phi\left((0.65)(3.76)\right)}{\Phi(3.76)-\Phi(-3.76)}$
$\displaystyle\approx 0.007$

So when using a block size of 4096, the expected number of samples assigned to
code values $q_{15}$ and $q_{16}$ will be less than 1%, whenever $M$ obtains
its median value or higher.

One can generalize the above calculation to show that for any fixed code, a
large enough block size will lead all but the smallest code values being used
extremely infrequently.

###  3.2 The exact distribution of $X_{i}$

As mentioned earlier, $X_{i}$ follows a mixture distribution, with mass $1/B$
being assigned uniformly to $\\{-1,1\\}$, and mass $(B-1)/B$ spread across
$(0,1)$. I’m keeping the index on $X_{i}$ to remind the reader that it comes
from a sample which contains other values of which it is not independent. To
avoid needing to carry all these $B$’s around, I’ll condition on $|X_{i}|\neq
1$, i.e. the corresponding $Z_{i}$ is not the maximal sample in the block.

For a fixed value of $M$, the conditional CDF is:

$\displaystyle P\left[X_{i}\leq x\>\middle|\>|X_{i}|<1,M=m\right]$
$\displaystyle=P\left[Z_{i}<mx\>\middle|\>|Z_{i}|<m\right]$
$\displaystyle=\frac{\Phi(mx)-\Phi(-m)}{\Phi(m)-\Phi(-m)}$
$\displaystyle=\Psi(mx;m,1)$ (2)

where $\Psi(\cdot;m,\sigma)$ is the CDF of a truncated normal distribution
with limits $[-M,M]$, mean $0$, and standard deviation $\sigma$.

To compute integrate out the conditioning on $M$, we need to calculate its
PDF, $p_{m}$. Differentiating its CDF, $F_{M}$:

$\displaystyle F_{M}(m)$
$\displaystyle=\operatorname{\text{\TH}}^{B}\left(m\right)$ $\displaystyle
p_{m}(m)$
$\displaystyle=2B\operatorname{\text{\TH}}^{(B-1)}\left(m\right)\varphi(m)$

where $\varphi(\cdot)$ is the Gaussian PDF.

Combining this expression with Equation 2, define $G_{B}$ to be the CDF of the
continuous portion of $X_{i}$’s distribution:

$\displaystyle P\left[X_{i}<x\>\middle|\>|X_{i}|<1\right]$
$\displaystyle=G_{B}(x)$
$\displaystyle=2B\int_{0}^{\infty}\operatorname{\text{\TH}}^{(B-1)}\left(m\right)\varphi(m)\Psi\left(x;m,1\right)dm$

There’s a good approximation of $G_{B}$ (See AppendixA), but to avoid worrying
about the quality of approximation, I’ll just use numerical integration to
calculate it directly.

Combining this with the discrete distribution for the endpoints, the CDF of
$X_{i}$ with block size $B$, $F_{X}(x;B)$, is:

$\displaystyle F_{X}(x$ $\displaystyle;B)=P\left[X_{i}\leq x\right]$
$\displaystyle=\begin{cases}0&x<-1\\\ \frac{1}{2B}&x=-1\\\
\frac{1}{2B}+G_{B}(x)&-1<x<1\\\ 1&x\geq 1\end{cases}$ (3)

##  4 Quibbles about quantiles

Dettmers et al. (2023) say that the defining property of NF4 is that it “has
equal expected number of values in each quantization bin.”. I’ll show in this
section that this is not the case, and how to construct a code with that
property. However, it turns out that such codes generally perform worse than
$NF4$, implying that one should not use this as a criterion for constructing
codes for quantization (See Appendix B).

There is one minor ambiguity which needs to be cleared up before moving
forward. In Dettmers et al. (2023), the method given for constructing NF4 is
to compute the average of quantile values, e.g.:

$\tilde{q}_{1}=\frac{1}{2}\left(\Phi^{-1}(1/16)+\Phi^{-1}(2/16)\right)$

On the other hand, the method used in the implementation is to compute the
quantile function applied to averaged inputs:

$\tilde{q}_{1}=\Phi^{-1}\left(\frac{1}{2}\left(1/16+2/16\right)\right)$

These values are not equal because $\Phi^{-1}$ is nonlinear. However, the
final outcome differs by less than 0.001, so it is unlikely to have a
noticeable effect.

$x$$F^{-1}(0.1)$$F^{-1}(0.2)$$F^{-1}(0.3)$$a$$b$Closer to $a$$P\neq 0.1$
Figure 3: Two bins of probability mass $0.1$ for a distribution with CDF $F$.
They have unequal widths, so using their centers, $a$ and $b$, as code values
will lead to too much mass being assigned to $a$. If $F^{-1}(0.2)$ itself is
used as a code value, the mass it encodes will depend on the distribution of
mass within the bins to either side. Figure 4: Usage of each NF4 code value
for (a) Samples from the generative process in Equation 1 (b) Weights from the
LLaMA-13B model. (Quantization block size $B=64$)

Regardless, neither of these strategies leads to a code which allocates equal
probability mass to all quantization bins. Figure 3 demonstrates the general
issue, namely that non-linearity in the CDF will cause quantile-based methods
to miss the mark.

Figure 4 shows the actual usage of NF4 code values for weights from LLaMA-13B,
and samples from the process defined in Equation 1. Rather than each value
being used with probability 6.25%, usages range between 2% and 9%.

###  4.1 Constructing uniformly used codes

Here’s a way to construct a code which has bins $[b_{1},b_{2}]$,
$[b_{2},b_{3}]$, etc. ($b_{1}$ may be $-\infty$):

  1. 1.

Choose an initial code value $q_{1}\in[b_{1},b_{2}]$.

  2. 2.

For $k=2,3,\dots k_{\text{max}}$:

$q_{k}\leftarrow 2b_{k}-q_{k-1}$

This will ensure that $(q_{k}+q_{k+1})/2=b_{k+1}$, i.e. $b_{k+1}$ will be a
quantization bin endpoint. (Because $q_{1}$ was free to vary, this describes a
set of codes rather than a single unique code).

In preliminary experiments, I found that these codes performed quite badly for
quantizing actual neural networks (See Appendix B). This indicates that
uniform usage of code values is not the idea target to aim for.

###  4.2 Minimizing reconstruction error

A single quantization error in a matrix causes a change in the output of
multiplications by that matrix proportional to the size of the error. Because
of this, directly minimizing the absolute value of the expected quantization
error seems like a promising approach.555This is a bit of a post hoc
justification. I initially tried minimizing the expected squared error, but
that led to worse LM performance.

Given a random variable $Y$ which is to be quantized, this we are searching
for the values $a_{1}<a_{2}<\dots<a_{16}$ which solve the following problem:

$\min\limits_{a_{1},\dots,a_{16}}E\left[\min_{j}\left|Y-a_{j}\right|\right]$

This is a 1-dimensional k-medians problem, over a mixed probability
distribution rather than a finite sample.

If $Y$ is continuous, it’s easy to calculate the following stationarity
condition for the optimal $j$-th code point for $1<j<16$:

$\displaystyle P\biggl{[}\frac{a_{j-1}+a_{j}}{2}$
$\displaystyle<Y<a_{j}\biggl{]}$ $\displaystyle=$ (4) $\displaystyle
P\biggl{[}a_{j}<Y<$ $\displaystyle\frac{a_{j}+a_{j+1}}{2}\biggl{]}$

This condition simply says that each code point should be the median of the
values mapped to it. It is a generalization of the well-known fact that the
median of a univariate distribution minimizes the expected distance from a
sample.

This constraint allows one to derive the value of $a_{j+1}$ from $a_{j}$ and
$a_{j-1}$ as follows:

$\displaystyle F_{Y}$
$\displaystyle(a_{j})-F_{Y}\left(\frac{a_{j-1}+a_{j}}{2}\right)=$
$\displaystyle F_{Y}\left(\frac{a_{j}+a_{j+1}}{2}\right)-F_{Y}(a_{j})$

So,

$a_{j+1}=2F_{Y}^{-1}\left(\rho_{j}\right)-a_{j}$ (5)

where

$\rho_{j}=2F_{Y}(a_{j})-F_{Y}\left(\frac{a_{j-1}+a_{j}}{2}\right)$

Given any two consecutive code values, the remainder of the values may be
determined using this rule. If we instead of two non-consecutive code values
such as $a_{1}=-1$ and $a_{8}=0$ (as in NF4), we can search for a value of
$a_{2}$ such that $a_{7}$ is stationary:

$\displaystyle a_{8}=2F^{-1}_{X}(\rho_{7})-a_{7}$ (6)

$a_{9:15}\in(0,1)$ may be found analogously if $a_{16}=1$ is fixed as well.

##  5 AF4: 4-bit AbnormalFloat

In order to see whether the above calculations are of more than theoretical
interest, I apply the method from the previous section to the $F_{X}(x;B)$ as
defined in Equation 3. The result is a code which I will call the 4-bit
AbnormalFloat datatype with block size $B$ (AF4-$B$). The three fixed values
used for the construction are: $a_{1}=-1$, $a_{8}=0$, and $a_{16}=1$, which
are also included in NF4. A script for producing these codes is available at
https://github.com/davisyoshida/abnormal-floats.

Figure 1 shows the result of using this process to produce AF4-$B$ codes for a
variety of block sizes. As expected, higher values of $B$ lead to codes more
tightly clustered around 0 as the distribution of $X_{i}$ becomes more peaked.

One thing which I should emphasize is that AF4 is _not_ the code which
globally minimizes the expected reconstruction error. Requiring the code to
include -1, 0, and 1 makes the average reconstruction error worse, but
including these values in the code is essential for quantization performance.

An interesting point is that the outermost NF4 values happen to nearly
coincide with AF4-64, and 64 is the default block size for using NF4. The
combination of this, the importance of including -1/0/+1, and the fact that
uniform binning codes perform poorly, suggests that representing these larger
values is important even if they occur less frequently.

##  6 Experiments

In order to check whether the reasoning above might be of more than
theoretical interest, I have run some experiments on language modeling and
zero-shot classification. The high-level summary is that the AF4 code
construction method does not consistently improve over NF4, except for at very
large block sizes. This validates the claim that NF4 is not optimal at all
block sizes. However, at small block sizes their performance is very
comparable, so this does not lead to a path to improving over the results of
Dettmers et al. (2023).

The experiments are the cross product of the following:

  1. 1.

Models: LLaMA-7B/13B/30B (Touvron et al., 2023), GPT-2-XL (Radford et al.,
2019), GPT-Neo-2.7B (Gao et al., 2020). The latter two models are the
HuggingFace Flax implementations (Wolf et al., 2019; Heek et al., 2023) while
the LLaMa models are reimplementations of the original using JAX + Haiku
(Bradbury et al., 2018; Hennigan et al., 2020).

  2. 2.

Datasets: The WikiText-103 validation set (Merity et al., 2016), a subset of
the PG-19 validation set (Rae et al., 2019), the LAMBADA cloze prediction
validation set (Paperno et al., 2016).

  3. 3.

Quantization methods: No quantization, NF4 quantization, AF4 quantization

Language modeling details. In the interest of reducing the computation
required, all experiments were run using disjoint inputs of length 512, rather
than using the maximum attention context and a sliding window. This leads to
higher perplexities, but it is a fair setting for comparing degradation due to
quantization. Perplexities have been renormalized to be word-based rather than
token-based using NLTK.

The LLaMA models were run using float16, and GPT-2 and GPT-Neo were run using
bfloat16. All experiments were run on one NVIDIA Quadro RTX 6000, except for
the LLaMA-13B baselines and LLaMA-30B runs, which used an NVIDIA RTX A6000.

Quantization details. All of the models were quantized using a JAX
transformation666This will be uploaded at
https://github.com/davisyoshida/abnormal-floats as well, so the model code was
unmodified. For matrices $W$ which are right-multiplied with the activations
(i.e. $xW$), quantization is performed on column-wise blocks, while row-wise
blocks are used for those which are left-multiplied777Of the models used here,
only GPT-2 uses left multiplication.

###  6.1 Results

Figure 5: Perplexity on WikiText-103 validation set

Language modeling. Results are shown in Figures 5, 6, and 7. For 8 out of 10
model/dataset pairs except for GPT-2 and LLaMA-13B on PG-19, AF4 leads to at
least slightly lower perplexity for a block size of $B=4096$. The
LLaMA-13B/30B models show extremely little dependence on the choice of code,
which is surprising given how different NF4 and AF4-4096 are.

For NF4’s default block size of $B=64$, AF4 is only better in 6 out of 10
dataset/model pairs, but the only model it performs significantly better for
at low block sizes is gpt-neo.

Zero-shot LAMBADA. Accuracy on the LAMBADA validation set is shown in Figures
8 and 9. The results here seem extremely noisy. For instance AF4-4096 leads to
a better accuracy than FP16 for the LLaMA-13B model, which must be random
chance rather than a meaningful measurement.

Similar to language modeling, there’s some indication that AF4 may be better
at large block sizes but even that is inconsistent. NF4 leads to better
accuracy with 3/5 models at its preferred block size of 64.

###  6.2 Discussion

A future investigation could use more models of size comparable to LLaMA-30B,
and more classification datasets to attempt to average out the noisy results
here. However, these experiments do provide some evidence that it is possible
to improve on NF4 for quantization at larger block sizes. Since NF4 may be
used at a small block size using the double quantization method of Dettmers et
al. (2023), this is mostly of theoretical interest.

As minimization of expected quantization error and uniformity of code value
usage both fail to lead to codes which perform better across the board, it is
an open question what criterion _should_ be used when selecting codes for data
free quantization.

##  7 Conclusion

The main takeaway here should be that when doing block-wise quantization, the
distribution of values to be quantized will depend on the block size. This
applies to quantization which uses a scale and an offset as well, although all
the calculations here were for the scale-only case.

One also shouldn’t try to aim for uniform usage of code values, since
minimization of expected quantization error seems to be a better target. The
question of exactly why including the -1, 0, and 1 values is important despite
worsening quantization error will hopefully be resolved by future work.

## Acknowledgements

Thank you to sekstini in the EleutherAI Discord for many productive
conversations on this topic, and to Tim Dettmers for feedback on the first
draft.

Figure 6: Perplexity on PG-19 validation set (subset)

Figure 7: LLaMA-30B language modeling results Figure 8: Accuracy on LAMBADA
validation set

Figure 9: Accuracy of LLaMA-30B on LAMBADA validation set

.

## References

  * Bradbury et al. (2018) James Bradbury, Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Wanderman-Milne, and Qiao Zhang. 2018.  JAX: composable transformations of Python+NumPy programs.
  * Dettmers et al. (2023) Tim Dettmers, Artidoro Pagnoni, Ari Holtzman, and Luke Zettlemoyer. 2023.  Qlora: Efficient finetuning of quantized llms.  _arXiv preprint arXiv:2305.14314_.
  * Gao et al. (2020) Leo Gao, Stella Biderman, Sid Black, Laurence Golding, Travis Hoppe, Charles Foster, Jason Phang, Horace He, Anish Thite, Noa Nabeshima, et al. 2020.  The pile: An 800gb dataset of diverse text for language modeling.  _arXiv preprint arXiv:2101.00027_.
  * Heek et al. (2023) Jonathan Heek, Anselm Levskaya, Avital Oliver, Marvin Ritter, Bertrand Rondepierre, Andreas Steiner, and Marc van Zee. 2023.  Flax: A neural network library and ecosystem for JAX.
  * Hennigan et al. (2020) Tom Hennigan, Trevor Cai, Tamara Norman, and Igor Babuschkin. 2020.  Haiku: Sonnet for JAX.
  * Merity et al. (2016) Stephen Merity, Caiming Xiong, James Bradbury, and Richard Socher. 2016.  Pointer sentinel mixture models.
  * Paperno et al. (2016) Denis Paperno, Germán Kruszewski, Angeliki Lazaridou, Ngoc-Quan Pham, Raffaella Bernardi, Sandro Pezzelle, Marco Baroni, Gemma Boleda, and Raquel Fernández. 2016.  The lambada dataset: Word prediction requiring a broad discourse context.  In _Proceedings of the 54th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 1525–1534.
  * Radford et al. (2019) Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. 2019.  Language models are unsupervised multitask learners.
  * Rae et al. (2019) Jack W Rae, Anna Potapenko, Siddhant M Jayakumar, Chloe Hillier, and Timothy P Lillicrap. 2019.  Compressive transformers for long-range sequence modelling.  _arXiv preprint_.
  * Touvron et al. (2023) Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al. 2023.  Llama: Open and efficient foundation language models.  _arXiv preprint arXiv:2302.13971_.
  * Wolf et al. (2019) Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, et al. 2019.  Huggingface’s transformers: State-of-the-art natural language processing.  _arXiv preprint arXiv:1910.03771_.

##  Appendix A Approximating the distribution of $X_{i}$

The following approximation of the continuous part of $X_{i}$’s distribution
is based on a suggestion of user whuber on Cross
Validated888https://stats.stackexchange.com/questions/616752/does-the-
following-distribution-converge-to-anything:

$\displaystyle P$ $\displaystyle\left[X_{i}\leq
x\>\middle|\>-1<X_{i}<1\right]$ $\displaystyle\approx
P\left[Z_{i}<xm_{0}\>\middle|\>|Z_{i}|<m_{0}\right]$
$\displaystyle=\Psi(xm_{0};m_{0},1)$ (7)

Where $m_{0}=\operatorname{\text{\TH}}^{-1}\left(2^{-1/B}\right)$ and
$\Psi(\cdot;a,\sigma)$ is a centered truncated normal distribution as before.
This is the same as the true CDF (Equation 3), but using a constant estimate
of $M$ since it will concentrate around its median for large $B$.

Figure 10: Comparison of empirical CDF of $X_{i}$ ($B=32$) and the
approximation given in Equation 7. $B=32$.

Even for the smallest block size used here, $B=32$, this approximation appears
to be quite close. Figure 10 shows a comparison of the predicted CDF compared
to an empirical CDF generated from $2^{33}$ samples999$2^{28}$ independent
blocks of size 32. The empirical result and approximation are so close that I
thought perhaps the integral worked out to just yield a truncated normal, but
they turn out to differ slightly. The approximate CDF predicts:

$P[X_{i}\leq 1/2]\approx 0.8712$

While drawing $2^{30}$ blocks of 32 and using one sample from each to estimate
a 95% confidence interval leads to:

$P[X_{i}\leq 1/2]\approx 0.8728\pm 2\times 10^{-5}$

##  Appendix B Codes with uniform usage

Figure 11: Each vertical slice represents a particular code which leads to
uniform bin usage for $B=64$. The dashed lines are quantiles. Notice that in
general the spacing is non-monotone with respect to distance from zero.

To justify the parenthetical in the title, I’ll briefly discuss what happens
if one does try to optimize for uniform code value usage. Using the method
described in Section 4.1, it’s easy to construct a set of codes with this
property for all values of $B$. As mentioned, the construction yields a
variety of different codes depending on the selected $q_{1}$ value, which is
illustrated in Figure 11.

Figure 12: Usage of code values when absmax quantizing blocks of 4096 normal
samples. “Balanced” shows successful construction of a code in which each
value is used equally. “Balanced w/ endpoints” is a variant in which -1, 0,
and 1 are included as code values. Figure 13: Perplexity on WikiText-103
validation set. Uniform code value usage does not lead to better quantization.

Figure 12 compares the relative usage of code values between several different
codes. Despite the fact that “Balanced w/ endpoints” leads to less uniform
usage of values than the exactly balanced code, including -1, 0, and 1 is
necessary to achieve remotely acceptable quantization. Figure 13 shows the
perplexity resulting from quantization with this code. It does about as well
as NF4 and AF4 for small block sizes, but is much worse at large block sizes.
This clearly demonstrates that uniform code usage is not a sufficient code
construction criterion.


* [309] D. M. Mathew, H. Kattan, C. Weis, J. Henkel, N. Wehn, and H. Amrouch, “Thermoelectric Cooling to Survive Commodity DRAMs in Harsh Environment Automotive Electronics,” _IEEE Access_ , 2021.
  * [310] K. Kobayashi, “Highly-reliable Integrated Circuits for Ground and Space Applications,” _ASICON_ , 2017.
  * [311] J. Kim, M. Sullivan, S. Lym, and M. Erez, “All-Inclusive ECC: Thorough End-to-End Protection for Reliable Computer Memory,” in _ISCA_ , 2016.
  * [312] S. Lee, N. S. Kim, and D. Kim, “Exploiting OS-Level Memory Offlining for DRAM Power Management,” _CAL_ , 2019.
  * [313] T. K. Moon, _Error Correction Coding: Mathematical Methods and Algorithms_. John Wiley & Sons, 2005\.
  * [314] T. Richardson and R. Urbanke, _Modern Coding Theory_. Cambridge University Press, 2008.
  * [315] R. M. Roth, _Introduction to Coding Theory_. Cambridge University Press, 2006.
  * [316] G. C. Clark Jr and J. B. Cain, _Error-Correction Coding for Digital Communications_. Springer SBM, 2013.
  * [317] D. J. Costello and S. Lin, _Error Control Coding: Fundamentals and Applications_. Prentice Hall, 1982.
  * [318] S. Lin and D. J. Costello, _Error Control Coding: Fundamentals and Applications_ , 2004.
  * [319] I. Alam, “Lightweight Opportunistic Memory Resilience,” Ph.D. dissertation, University of California, Los Angeles, 2021.
  * [320] S. Jeong, S. Kang, and J.-S. Yang, “PAIR: Pin-aligned In-DRAM ECC architecture using expandability of Reed-Solomon code,” in _DAC_ , 2020\.
  * [321] S.-L. Gong, J. Kim, S. Lym, M. Sullivan, H. David, and M. Erez, “DUO: Exposing On-Chip Redundancy to Rank-Level ECC for High Reliability,” in _HPCA_ , 2018.
  * [322] S.-I. Pae, V. Kozhikkottu, D. Somasekar, W. Wu, S. G. Ramasubramanian, M. Dadual, H. Cho, and K.-W. Kwon, “Minimal Aliasing Single-Error-Correction Codes for DRAM Reliability Improvement,” _IEEE Access_ , 2021.
  * [323] Y. Luo, S. Govindan, B. Sharma, M. Santaniello, J. Meza, A. Kansal, J. Liu, B. Khessib, K. Vaid, and O. Mutlu, “Characterizing Application Memory Error Vulnerability to Optimize Datacenter Cost via Heterogeneous-Reliability Memory,” in _DSN_ , 2014.
  * [324] M. Patel, G. F. de Oliveira, and O. Mutlu, “HARP: Practically and Effectively Identifying Uncorrectable Errors in Memory Chips That Use On-Die Error-Correcting Codes,” in _MICRO_ , 2021.
  * [325] D.-T. Nguyen, N.-M. Ho, M.-S. Le, W.-F. Wong, and I.-J. Chang, “ZEM: Zero-Cycle Bit-Masking Module for Deep Learning Refresh-Less DRAM,” _IEEE Access_ , 2021.
  * [326] J. Gómez-Luna, J. El Hajj, I. Fernandez, and C. Giannoula, “Benchmarking a New Paradigm: Understanding a Modern Processing-in-Memory Architecture,” in _arXiv:2105.03814_ , 2021.
  * [327] J. Gómez-Luna, I. El Hajj, I. Fernandez, C. Giannoula, G. F. Oliveira, and O. Mutlu, “Benchmarking Memory-Centric Computing Systems: Analysis of Real Processing-in-Memory Hardware,” in _CUT_ , 2021.
  * [328] C. Giannoula, I. Fernandez, J. Gómez-Luna, N. Koziris, G. Goumas, and O. Mutlu, “Towards Efficient Sparse Matrix Vector Multiplication on Real Processing-in-Memory Architectures,” _SIGMETRICS_ , 2022.
  * [329] J. S. Kim, “Improving DRAM Performance, Security, and Reliability by Understanding and Exploiting DRAM Timing Parameter Margins,” Ph.D. dissertation, Carnegie Mellon University, 2020.
  * [330] D. Lee, S. Ghose, G. Pekhimenko, S. Khan, and O. Mutlu, “Simultaneous Multi-Layer Access: Improving 3D-Stacked Memory Bandwidth at Low Cost,” _TACO_ , 2016.
  * [331] V. Seshadri and O. Mutlu, “Simple Operations in Memory to Reduce Data Movement,” in _Advances in Computers_ , 2017.
  * [332] V. Seshadri and O. Mutlu, “In-DRAM Bulk Bitwise Execution Engine,” _Advances in Computers_ , 2020.
  * [333] M. Yue, N. Karimian, W. Yan, N. A. Anagnostopoulos, and F. Tehranipoor, “DRAM-Based Authentication Using Deep Convolutional Neural Networks,” _IEEE Consumer Electronics Magazine_ , 2020.
  * [334] M. S. Hashemian, B. Singh, F. Wolff, D. Weyer, S. Clay, and C. Papachristou, “A Robust Authentication Methodology Using Physically Unclonable Functions in DRAM Arrays,” in _DATE_ , 2015.
  * [335] A. Schaller, W. Xiong, N. A. Anagnostopoulos, M. U. Saleem, S. Gabmeyer, B. Škorić, S. Katzenbeisser, and J. Szefer, “Decay-Based DRAM PUFs in Commodity Devices,” _TDSC_ , 2018.
  * [336] B. B. Talukder, B. Ray, D. Forte, and M. T. Rahman, “PreLatPUF: Exploiting DRAM Latency Variations For Generating Robust Device Signatures,” _IEEE Access_ , 2019.
  * [337] T. Bennett, S. Saroiu, A. Wolman, and L. Cojocar, “Panopticon: A Complete In-DRAM Rowhammer Mitigation,” in _DRAMSec_ , 2021.
  * [338] Y. Kim, V. Seshadri, D. Lee, J. Liu, and O. Mutlu, “A Case for Exploiting Subarray-Level Parallelism (SALP) in DRAM,” in _ISCA_ , 2012.
  * [339] K. Park, C. Lim, D. Yun, and S. Baeg, “Experiments and Root Cause Analysis for Active-Precharge Hammering Fault In DDR3 SDRAM Under 3$\times$ Nm Technology,” _Microelectronics Reliability_ , 2016.
  * [340] D. Yun, M. Park, C. Lim, and S. Baeg, “Study of TID Effects on One Row Hammering using Gamma in DDR4 SDRAMs,” in _IRPS_ , 2018.
  * [341] C. Lim, K. Park, and S. Baeg, “Active Precharge Hammering to Monitor Displacement Damage using High-Energy Protons in 3x-nm SDRAM,” _IEEE Trans. Nucl. Sci._ , 2016.
  * [342] A. Tatar, C. Giuffrida, H. Bos, and K. Razavi, “Defeating Software Mitigations Against Rowhammer: A Surgical Precision Hammer,” in _RAID_ , 2018.
  * [343] A. J. Walker, S. Lee, and D. Beery, “On DRAM Rowhammer and the Physics of Insecurity,” _TED_ , 2021.
  * [344] T. Baker, “Opening Up Ada-Tasking,” _ACM SIGAda Ada Letters_ , 1990.
  * [345] K. Duganapalli, “Modelling and Test Generation for Crosstalk Faults in DSM Chips,” Ph.D. dissertation, Universität Bremen, 2016.
  * [346] L. Cojocar, K. Loughlin, S. Saroiu, B. Kasikci, and A. Wolman, “mFIT: A Bump-in-the-Wire Tool for Plug-and-Play Analysis of Rowhammer Susceptibility Factors,” 2021.
  * [347] L. Borucki, G. Schindlbeck, and C. Slayman, “Comparison of Accelerated DRAM Soft Error Rates Measured at Component and System Level,” in _IEEE IRPS_ , 2008.
  * [348] A. G. Yağlıkçı, H. Luo, A. Olgun, G. F. de Oliveira Junior, J. Park, M. Patel, H. Hassan, L. Orosa, J. Kim, and O. Mutlu, “Understanding the RowHammer Vulnerability Under Reduced Wordline Voltage: An Experimental Study Using Real Devices,” in _DSN_ , 2022.
  * [349] B. Schroeder, E. Pinheiro, and W.-D. Weber, “DRAM Errors in the Wild: a Large-Scale Field Study,” in _SIGMETRICS_ , 2009.
  * [350] Q. Salman, K. Yoongu, B. Nicolas, S. Eric, and N. Mattias, “Half-Double: Next-Row-Over Assisted Rowhammer,” 2021.
  * [351] J. Kim and M. C. Papaefthymiou, “Block-Based Multi-Period Refresh For Energy Efficient Dynamic Memory,” in _IEEE International ASIC/SOC Conference_ , 2001.
  * [352] S. Levy, K. B. Ferreira, N. DeBardeleben, T. Siddiqua, V. Sridharan, and E. Baseman, “Lessons Learned from Memory Errors Observed Over the Lifetime of Cielo,” in _SC_ , 2018.
  * [353] F. Wang and V. D. Agrawal, “Soft Error Rates with Inertial and Logical Masking,” in _VLSI_ , 2009.
  * [354] Micron Technology, “DRAM,” https://www.micron.com/products/dram/.
  * [355] ISSI, “DDR4 SDRAM,” https://www.issi.com/US/product-dram-ddr4.shtml.
  * [356] ISSI, “NT5AD256M16E4-JR,” https://www.nanya.com/en/Product/4596/NT5AD256M16E4-JR.
  * [357] F. Devaux, “The True Processing in Memory Accelerator,” in _HCS_ , 2019\.
  * [358] Y.-C. Kwon, S. H. Lee, J. Lee, S.-H. Kwon, J. M. Ryu, J.-P. Son, O. Seongil, H.-S. Yu, H. Lee, S. Y. Kim, Y. Cho, J. G. Kim, J. Choi, H.-S. Shin, J. Kim, B. Phuah, H. Kim, M. J. Song, A. Choi, D. Kim, S. Kim, E.-B. Kim, D. Wang, S. Kang, Y. Ro, S. Seo, J. Song, J. Youn, K. Sohn, and N. S. Kim, “25.4 A 20nm 6GB Function-In-Memory DRAM, Based on HBM2 with a 1.2 TFLOPS Programmable Computing Unit Using Bank-Level Parallelism, for Machine Learning Applications,” in _ISSCC_ , 2021.
  * [359] M. He, C. Song, I. Kim, C. Jeong, S. Kim, I. Park, M. Thottethodi, and T. Vijaykumar, “Newton: A DRAM-Maker’s Accelerator-In-Memory (AiM) Architecture for Machine Learning,” in _MICRO_ , 2020.
  * [360] D. Niu, S. Li, Y. Wang, W. Han, Z. Zhang, Y. Guan, T. Guan, F. Sun, F. Xue, L. Duan, Y. Fang, H. Zheng, X. Jiang, S. Wang, F. Zuo, Y. Wang, B. Yu, Q. Ren, and Y. Xie, “184QPS/W 64Mb/mm 2 3D Logic-to-DRAM Hybrid Bonding with Process-Near-Memory Engine for Recommendation System,” in _ISSCC_ , 2022.
  * [361] J. Ahn, S. Hong, S. Yoo, O. Mutlu, and K. Choi, “A Scalable Processing-In-Memory Accelerator for Parallel Graph Processing,” _ISCA_ , 2016.
  * [362] S. Lee, K. Kim, S. Oh, J. Park, G. Hong, D. Ka, K. Hwang, J. Park, K. Kang, J. Kim _et al._ , “A 1ynm 1.25 V 8Gb, 16Gb/s/pin GDDR6-based Accelerator-in-Memory supporting 1TFLOPS MAC Operation and Various Activation Functions for Deep-Learning Applications,” in _ISSCC_ , 2022.
  * [363] R. Balasubramonian, “Innovations in the Memory System,” _Synthesis Lectures on Computer Architecture_ , 2019.
  * [364] R. Balasubramonian, “A DRAM Refresh Tutorial,” http://utaharch.blogspot.com/2013/11/a-dram-refresh-tutorial.html, 2013\.
  * [365] W.-K. Cheng, P.-Y. Shen, and X.-L. Li, “Retention-Aware DRAM Auto-Refresh Scheme for Energy and Performance Efficiency,” _Micromachines_ , 2019.

##  Appendix A DRAM Trends Survey

We survey manufacturer-recommended DRAM operating parameters as specified in
commodity DRAM chip datasheets in order to understand how the parameters have
evolved over time. We extract values from 58 independent DRAM chip datasheets
from across 19 different DRAM manufacturers with datasheet publishing dates
between 1970 and 2021. Appendix B lists each datasheet and the details of the
DRAM chip that it corresponds to. We openly release our full dataset on GitHub
[35], which provides a spreadsheet with all of the raw data used in this
paper, including each timing and current parameter value, and additional
fields (e.g., clock frequencies, package pin counts, remaining IDD values)
that are not presented here.

###  A.1 DRAM Access Timing Trends

We survey the evolution of the following four DRAM timing parameters that are
directly related to DRAM chip performance.

  * •

_tRCD_ : time between issuing a row command (i.e., row activation) and a
column command (e.g., read) to the row.

  * •

_CAS Latency (or tAA)_ : time between issuing an access to a given column
address and the data being ready to access.

  * •

_tRAS_ : time between issuing a row command (i.e., row activation) and a
precharge command.

  * •

_tRC_ : time between accessing two different rows.

Figure 3 shows how key DRAM timing parameters have evolved across DRAM chips
of different years (top) and capacities (bottom). Timing values are shown in
log scale to better distinguish small values in newer DRAM chips. Each type of
marker illustrates DRAM chips of different DRAM standards.

Figure 3: Evolution of four key DRAM timing parameters (shown in log scale)
across years (top) and chip capacities (bottom) separated by DRAM standard.

We make three qualitative observations. First, while all four DRAM timing
values have roughly decreased over time, improvements have been relatively
stagnant for the last two decades (note the logarithmic Y-axis). The bulk of
the improvement in timing parameter values occurred during the period of
asynchronous DRAM, and following the introduction of SDRAM and DDR _n_ DRAM
chips, little to no improvements have been made despite, or possibly as a
result of, continual increases in overall chip storage density. Second, CAS
latency and tRCD converged to roughly the same values following the
introduction of synchronous DRAM. We hypothesize that this is because similar
factors affect the latency of these operations, including a long command and
data communication latency between the external DRAM bus and the internal
storage array [3]. Third, the DDR5 data points appear to worsen relative to
previous DDR _n_ points. However, we believe this might be because DDR5 chips
are new at the time of writing this article and have not yet been fully
optimized (e.g., through die revisions and other process improvements).

To quantify the changes in access timings, we aggregate the data points from
Figure 3 by three different categories: time, DRAM standard, and chip
capacity. Figure 4, shows the minimum, median, and maximum of the timing
parameter values (in log scale) for each 5-year period (top) and DRAM standard
(bottom). The data shows that the median tRCD/CAS Latency/tRAS/tRC reduced by
2.66/3.11/2.89/2.89% per year on average between 1970 and 2000 but only
0.81/0.97/1.33/1.53% between 2000 and 2015141414We omit the 2020 data point
because 2020 shows a regression in CAS latency due to first-generation DDR5
chips, which we believe is not representative because of its immature
technology. for an overall decrease of 1.83/2.10/1.99/2.00% between 1970 and
2015.

Figure 4: Evolution of the minimum, median, and maximum values of key DRAM
timing parameters (shown in log scale) for each 5-year period (top) and DRAM
standard (bottom). Figure 5: Evolution of the minimum, median, and maximum
values of key DRAM timing parameters (shown in log scale) grouped by DRAM chip
storage capacity.

Figure 5 shows the minimum, median, and maximum of the timing parameter values
(in log scale) grouped by DRAM chip storage capacity.151515We omit tRCD and
tRAS for the 1 Kib chips because they do not use a row address strobe (RAS)
signal. We find that the timings follow similar trends as in Figure 4 because
higher-capacity DRAM chips are typically introduced more recently and follow
newer DRAM standards.

###  A.2 Current Consumption Trends

We review the evolution of the following key DRAM current consumption
measurements, which are standardized by JEDEC and are provided by
manufacturers in their datasheets.

  * •

_IDD0_ : current consumption with continuous row activation and precharge
commands issued to only one bank.

  * •

_IDD4R_ : current consumption when issuing back-to-back read operations to all
banks.

  * •

_IDD5B_ : current consumption when issuing continuous burst refresh
operations.

Figure 6 shows how key DRAM current consumption values (in log scale) have
evolved across DRAM chips of different years (top) and capacities (bottom). We
use different markers to show data points from chips of different DRAM
standards. We qualitatively observe that current consumption increased
exponentially up until approximately the year 2000, which is about the time at
which improvements in access timings slowed down (as seen in Figure 3). After
this point, different current consumption measurements diverged as IDD0 values
decreased while IDD4R and IDD5B stabilized or increased. We explain this
behavior by a change in the way DRAM chips were refreshed as DRAM capacities
continued to increase. Earlier DRAM chips refreshed rows using individual row
accesses (e.g., RAS-only refresh), which result in comparable behavior for
access and refresh operations. In contrast, newer DRAM chips aggressively
refresh _multiple_ rows per refresh operation (e.g., burst refresh), which
differentiates refresh operations from normal row accesses [186, 363, 364].

We quantify the current consumption values by aggregating the data points from
Figure 6 by time and DRAM standard. Figure 7 shows the minimum, median, and
maximum values (in log scale) across each 5-year period (top) and DRAM
standard (bottom). The data shows that the median IDD0/IDD4R/IDD5B increased
by 12.22/20.91/26.97% per year on average between 1970 and 2000 but
_decreased_ by 4.62/1.00/0.13% between 2000 and 2015161616Similar to Section
A.1, we omit the 2020 data point because the first-generation DDR5 chips
exhibit outlying data values (e.g., no data reported for IDD5B in the
datasheets). for an overall increase of 0.96/11.5/17.5% between 1970 and 2015.

Figure 6: Evolution of key DRAM current consumption values (shown in log
scale) across years (top) and chip capacities (bottom) separated by DRAM
standard.

###  A.3 Relationship Between Timings and Currents

Finally, we examine the high-level relationship between the timing parameter
and current consumption values. We find that the two are generally inversely
related, which follows from the general principle that faster DRAM chips
(i.e., lower timing parameters) require more power (i.e., increased current
consumption values). Figure 8 illustrates this relationship for the four
timing parameters studied in Section A.1 relative to IDD4R (i.e., the current
consumption of read operations).

###  A.4 DRAM Refresh Timing Trends

DRAM refresh is governed by two key timing parameters:

  * •

_tREFI_ (refresh interval): time between consecutive refresh commands sent by
the memory controller.

  * •

_tRFC_ : duration of a single refresh command.

Figure 7: Evolution of the minimum, median, and maximum of key DRAM current
consumption value (shown in log scale) for each 5-year period (top) and DRAM
standard (bottom).

Figure 9 shows how tREFI (left y-axis) and tRFC (right y-axis) evolved across
the DRAM chips in our study. We group chips by storage capacity because DRAM
refresh timings are closely related to capacity: higher-capacity chips using
the same technology require more time or more refresh operations to fully
refresh. The error bars show the minimum and maximum values observed across
all chips for any given chip capacity.

Figure 8: Relationship between the four timing parameters and IDD4R separated
by DRAM standard.

We make three observations. First, tREFI is shorter for higher-capacity DRAM
chips (e.g., 62.5 $\mu$s for an asynchronous 1 Kib chip versus 3.9 $\mu$s for
a 16 Gib DDR5 chip). This is consistent with the fact that higher-capacity
chips require more frequent refreshing. Second, tRFC first decreases with chip
capacity (e.g., 900 ns for an asynchronous 1 Kib chip versus 54 ns for a 32
Mib SDRAM chip) but then increases (e.g., to 350 ns for a 16 Gib DDR4 chip).
This is because rapid improvements in row access times (and therefore refresh
timings) initially outpaced the increase in storage capacity. However,
starting around 512 Mib chip sizes, row access times improved much more slowly
(as observed in Section A.1) while storage capacity continued to increase.
Third, the variation in tRFC across chips of each capacity (illustrated using
the error bars) decreased for higher-capacity chips. This is because higher-
capacity chips follow more recent DRAM standards (i.e., DDR _n_), which
standardize DRAM auto refresh timings. In contrast, older DRAM chips were
simply refreshed as quickly as their rows could be accessed (e.g., every tRC
using RAS-only refresh).

Figure 9: Evolution of tREFI (left y-axis) and tRFC (right y-axis) across DRAM
chips of increasing storage capacity.

Figure 10 shows the _refresh penalty_ [364, 363], which is defined as the
ratio between tRFC and tREFI, for DRAM chips of different storage capacities.
The refresh penalty represents the average time that a DRAM rank (or bank) is
unavailable for access due to refresh operations [364, 185, 363, 365, 188]. We
observe that the refresh penalty exhibits a similar trend to tRFC: the refresh
penalty worsens from a median of 1.04% for 1 Kib chips to 2.05% for 16 Kib
chips, then improves to 0.43% for 128 Mib chips, and finally worsens to a
median of 4.48% (worst-case of 7.56% for DDR5 chips) for 16 Gib chips.

Figure 10: Refresh penalty (computed as the ratio between tRFC and tREFI) for
DRAM chips of different storage capacities.

This non-monotonic trend is due to the relative improvements in DRAM access
times and storage capacities: DRAM capacities consistently improved while DRAM
access times did so only for older, lower-capacity chips (e.g., $\leq 128$ Mib
chips). This is consistent with trends observed in prior work [43, 77, 181,
187, 183, 82], which expect that future, higher-capacity DRAM chips will spend
an even larger proportion of time refreshing unless the DRAM refresh algorithm
and techniques can be improved.

##  Appendix B Survey Data Sources

Table 5 itemizes the 58 DRAM datasheets used for our survey in Appendix A. For
each datasheet, we show the DRAM chip manufacturer, model number, DRAM
standard, year, and capacity. Our full dataset is available online [35].

Year | Manufacturer | Model Number | Datasheet Source | DRAM Standard | Capacity per Chip (Kib)
---|---|---|---|---|---
1970 | Intel | 1103 |  ds_intel19701103 | Asynchronous | 1
1971 | Mostek | MK4006 |  ds_mostek1971mk4006 | Asynchronous | 1
1973 | Mostek | MK4096 |  ds_mostek1973mk4096 | Asynchronous | 4
1976 | Mostek | MK4027 |  ds_mostek1976mk4027 | PM | 4
1976 | Mostek | MK4116P |  ds_mostek1976mk4116p | PM | 16
1978 | Fairchild | F4116 |  ds_fairchild1978f4116 | PM | 16
1979 | Intel | 2118 |  ds_intel19792118 | PM | 16
1981 | Mitsubishi | M5K4164ANP |  ds_mitsubishi1981m5k4164anp | PM | 64
1982 | Mostek | MK4564 |  ds_mostek1982mk4564 | PM | 64
1984 | NTE | NTE4164 |  ds_nte1984nte4164 | PM | 64
1984 | Texas Instruments | TMS4416 |  ds_texas1984tms4416 | PM | 64
1985 | Mitsubishi | M5M4256P |  ds_mitsubishi1985m5m4256p | PM | 256
1987 | Samsung | KM41464A |  ds_samsung1987km41464a | PM | 256
1987 | Texas Instruments | TMS4464 |  ds_texas1987tms4464 | PM | 256
1989 | Texas Instruments | SMJ4464 |  ds_texas1989smj4464 | PM | 256
1990 | Intel | 21256 |  ds_intel199021256 | PM | 256
1991 | Mitsubishi | M5M44100 |  ds_mitsubishi1991m5m44100 | FPM | 4096
1993 | Mitsubishi | M5M44256B |  ds_mitsubishi1993m5m44256b | FPM | 1024
1993 | Mosel Vitelic | V404J8 |  ds_mosel1993v404j8 | FPM | 8192
1995 | Siemens | HYB511000BJ |  ds_siemens1995hyb511000bj | FPM | 1024
1997 | Hyundai | HY5118164B |  ds_hyundai1997hy5118164b | EDO | 16384
1997 | Samsung | KM48S2020CT |  ds_samsung1997km48s2020ct | SDRAM | 16384
1998 | Micron | MT48LC4M4A1 |  ds_micron1998mt48lc4m4a1 | SDRAM | 16384
1998 | Mosel Vitelic | V53C808H |  ds_mosel1998v53c808h | EDO | 8192
1998 | Siemens | HYB39S16400 |  ds_siemens1998hyb39s16400 | SDRAM | 16384
1999 | Samsung | K4S160822D |  ds_samsung1999k4s160822d | SDRAM | 16384
1999 | Samsung | K4S561632A |  ds_samsung1999k4s561632a | SDRAM | 262144
2000 | Amic | A416316B |  ds_amic2000a416316b | FPM | 1024
2000 | ISSI | IS41LV32256 |  ds_issi2000is41lv32256 | EDO | 8192
2000 | Samsung | K4D623237A5 |  ds_samsung2000k4d623237a5 | DDR | 65536
2001 | Alliance | AS4C256K16E0 |  ds_alliance2001as4c256k16e0 | EDO | 4096
2001 | Alliance | AS4C4M4FOQ |  ds_alliance2001as4c4m4foq | FPM | 16384
2001 | ISSI | IS41C4400X |  ds_issi2001is41c4400x | EDO | 16384
2001 | Micron | MT46V2M32 |  ds_micron2001mt46v2m32 | DDR | 65536
2001 | Micron | MT46V32M4 |  ds_micron2001mt46v32m4 | DDR | 131072
2001 | Mosel Vitelic | V58C265164S |  ds_mosel2001v58c265164s | DDR | 65536
2001 | TM Tech | T224160B |  ds_tm2001t224160b | FPM | 4096
2003 | Micron | MT46V64M4 |  ds_micron2003mt46v64m4 | DDR | 262144
2003 | Samsung | K4S560432E |  ds_samsung2003k4s560432e | SDRAM | 262144
2005 | Amic | A43L0632 |  ds_amic2005a43l0632 | SDRAM | 32768
2006 | Elite | M52S32321A |  ds_elite2006m52s32321a | SDRAM | 32768
2006 | ISSI | IS42S81600B |  ds_issi2006is42s81600b | SDRAM | 131072
2006 | Sasmung | K4T51043QC |  ds_sasmung2006k4t51043qc | DDR2 | 524288
2007 | Micron | MT47H256M4 |  ds_micron2007mt47h256m4 | DDR2 | 1048576
2010 | Samsung | K4B4G0446A |  ds_samsung2010k4b4g0446a | DDR3 | 4194304
2011 | Hynix | H5TQ4G43MFR |  ds_hynix2011h5tq4g43mfr | DDR3 | 4194304
2011 | Nanya | NT5CB512M |  ds_nanya2011nt5cb512m | DDR3 | 2097152
2013 | Samsung | K4B4G0446A |  ds_samsung2013k4b4g0446a | DDR3 | 4194304
2015 | Micron | MT40A2G |  ds_micron2015mt40a2g | DDR4 | 8388608
2016 | Hynix | H5AN4G4NAFR |  ds_hynix2016h5an4g4nafr | DDR4 | 4194304
2016 | Samsung | K4A8G165WC |  ds_samsung2016k4a8g165wc | DDR4 | 8388608
2017 | Hynix | H5AN8G4NAFR |  ds_hynix2017h5an8g4nafr | DDR4 | 8388608
2018 | Micron | MT40A |  ds_micron2018mt40a | DDR4 | 16777216
2019 | Hynix | H5AN8G4NCJR |  ds_hynix2019h5an8g4ncjr | DDR4 | 8388608
2019 | Samsung | K4AAG045WA |  ds_samsung2019k4aag045wa | DDR4 | 16777216
2020 | Samsung | K4AAG085WA |  ds_samsung2020k4aag085wa | DDR4 | 16777216
2021 | Hynix | HMCG66MEB |  ds_hynix2021hmcg66meb | DDR5 | 16777216
2021 | Micron | MT60B1G16 |  ds_micron2021mt60b1g16 | DDR5 | 16777216

Table 5: List of DRAM chip datasheets used in our DRAM trends survey.

IEEEtran references


# Structural Dropout for Model Width Compression

Julian Knodt
Princeton University
Princeton, NJ 08544
<EMAIL_ADDRESS>

###### Abstract

Existing ML models are known to be highly over-parametrized, and use
significantly more resources than required for a given task. Prior work has
explored compressing models offline, such as by distilling knowledge from
larger models into much smaller ones. This is effective for compression, but
does not give an empirical method for measuring how much the model can be
compressed, and requires additional training for each compressed model. We
propose a method that requires only a single training session for the original
model and a set of compressed models. The proposed approach is a “structural”
dropout that prunes all elements in the hidden state above a randomly chosen
index, forcing the model to learn an importance ordering over its features.
After learning this ordering, at inference time unimportant features can be
pruned while retaining most accuracy, reducing parameter size significantly.
In this work, we focus on Structural Dropout for fully-connected layers, but
the concept can be applied to any kind of layer with unordered features, such
as convolutional or attention layers. Structural Dropout requires no
additional pruning/retraining, but requires additional validation for each
possible hidden sizes. At inference time, a non-expert can select a memory
versus accuracy trade-off that best suits their needs, across a wide range of
highly compressed versus more accurate models.

##  1 Introduction

A neural network consists of some number of unstructured vector
transformations from some input to some output. By learning parameters for
these transformations, a neural net is able to optimize for a loss function,
using gradient descent. While it has been shown that an infinitely large
neural network can be a universal approximation for any function, it is not
clear how small neural networks can be, and how to efficiently find this size.
With enough time and resources, it is possible to perform an exhaustive grid
search to find hyper-parameters for model size, or use tools such as neural
architecture search. For an ML researcher, this may be infeasible, and they
will select hyper-parameters which are certainly too large, but definitely
provide enough capacity to learn the task at hand. While this is practical for
a researcher, for a user of these models they may be wasting computational
resources, in memory and run-time efficiency. Furthermore, the burden is
pushed onto the user to compress the model. To help compress models, there
have been a large number of non-intrusive techniques for shrinking the size of
models, such as quantization from 32 bit floating point numbers to 16 or even
8 bits, providing 2x and 4x memory savings respectively. There have also been
a number of other techniques, such as knowledge distillation, where a much
smaller student model is trained to match the output of a larger teacher
model.

While some of these methods work out of the box on existing models, such as
floating point quantization, other methods still leave choices such as the
size of the compressed model, and may introduce additional error by retraining
a new model. Thus, these methods may be non-starters for a user who wants to
deploy a model, where a given model is too large for their resource budget. A
better approach for model compression would allow for selecting from a
resource usage to accuracy table provided alongside a compressible model, with
no additional retraining. The reason that neural nets cannot simply be trimmed
is because of the unstructured nature of the internal hidden state. That is,
given some function $f(x)=g(h(x))$, where the target is
$h^{*}=\text{argmin}_{h}g(h(x))$ and $h(x)$ is the hidden state of a network,
and $h_{2}(x)\subset h_{1}(x)\subseteq h(x)$, it is not clear whether
$g(h_{2}(x))\stackrel{{\scriptstyle?}}{{<}}g(h_{1}(x))$. It would be possible
to evaluate this for all possible subsets, but this is computationally
infeasible, since there are $2^{|h(x)|}$ possible sub-networks. If we can
impose an ordering such that for some known choices of
$h_{1},h_{2}:h_{2}\subset h_{1}\implies
g(h_{2}(x))\stackrel{{\scriptstyle\text{likely}}}{{\leq}}g(h_{1}(x))$, then we
can prune the features $h_{1}\setminus h_{2}$, and measure the loss in
performance without needing an exhaustive search. In addition, if we find that
$g(h_{2}(x))\geq g(h_{1}(x))$, we can even compress the network without
accuracy loss.

We seek to learn such an ordering. For each hidden layer to compress, we would
like the following property to approximately hold:

$\forall k_{1},k_{2}\in Z_{+}:k_{1}<k_{2}\implies g(h_{0\ldots
k_{1}}(x))\lesssim g(h_{0\ldots k_{2}}(x))$

Where $h_{0\ldots k}(x)$ are the first $k$ features of $h(x)$. This property
can be thought of as being similar to integer encoding, where the higher bits
of an integer encode more of its magnitude. In order to learn this property,
we train the network using Structural Dropout (SD). Structural Dropout is
defined as follows:

$\text{SD}(x\in\mathbb{R}^{N},p\in[0,1],\text{lb}\in\mathbb{Z}_{+})=\begin{cases}x&\text{with
probability $1-p$}\\\
\frac{N}{i}x_{0...i}\oplus\vec{0},i\sim\mathbb{U}(\text{lb},N)&\text{otherwise}\\\
\end{cases}$ (1)

Where lb is some lower bound on the number of elements (defaulting to 1), $p$
is the dropout probability (defaulting to 0.5), and $i$ is an index chosen
uniformly from all indeces, after which all elements are zeroed. There is an
additional normalization constant $\frac{N}{i}$ so that $\mathbb{E}[x]$ is the
same regardless of the number of sampled elements, and this normalization is
applied both during training and inference. By randomly dropping out later
indices, the network is forced to encode important information at lower
indices, achieving the desired property. SD also retains some chance of
training the entire state, otherwise the highest indices would be trained
infrequently, and would not serve as supervision for the smaller layers, which
we demonstrate later in ablations.

Structural Dropout acts as a method for training an entire ensemble of
“matryoshka” networks, or networks that are nested within each other that
share weights. During inference, we can pick from these nested networks to
suit resource and accuracy constraints. Specifically, at inference time, we
can make Structural Dropout deterministic and only compute:

$\text{SD}_{\text{test}}(x,k\in[0,N])=\frac{N}{k}x_{0...i}\oplus\vec{0}$ (2)

For some desired $k\in[0,N]$. Since the higher indices are all $0$, it is easy
to prune layers. For example, if we have

$A\in\mathbb{R}^{m,n},B\in\mathbb{R}^{N,n},x\in\mathbb{R}^{N}$
$A(SD_{\text{test}}(Bx,k))=A[:,\text{:k}](\frac{N}{k}B[\text{:k},:]x)$

Where $A[\text{:k},:]$ is Python slicing notation. We are able to prune linear
layers applied before SD keeping $k$ rows, and prune linear layers after,
keeping $k$ columns. Thus, we find that while the original matrix
multiplications were $O(nN)+O(mn)$, we can reduce this to $O(kN)+O(mk)$. The
concept of SD can be applied to many different kinds of layers, such as
convolutional layers or self-attention layers, by dropping out later feature
channels or attention heads, but we leave analysis of these to future work and
focus only on expensive linear layers.

Figure 1: Visualization of Structural Dropout. Rather than randomly selecting
indices to prune, during training Structural Dropout prunes all nodes after a
uniformly randomly selected index, and normalizes the expectation based on the
number of features dropped. With some probability, we run the full network,
using it as supervision for the smaller networks indirectly.

To summarize, this work’s contributions are as follows:

  1. 1.

A variant of Dropout, Structural Dropout, that trains an ensemble of nested
networks, which can later be disentangled for compression without additional
retraining.

  2. 2.

A validation of Structural Dropout on 3 example tasks, demonstrating its
effectiveness across a variety of methods while retaining accuracy.

  3. 3.

An implementation of Structural Dropout, released at
https://github.com/JulianKnodt/structural_dropout.

##  2 Background

Structural Dropout can be understood as model compression using knowledge
distillation, but is heavily inspired by Dropout.

###  2.1 Dropout

Dropout [18] was originally proposed as a methodology to prevent networks from
overfitting by preventing neurons from strongly entangling information,
preventing memorization of training data to specific outputs. This is done by
replacing values in the hidden state with $0$ with probability $p$. The
original authors offer one interpretation of this as an ensemble approach,
where many smaller models are averaged together in order to achieve better
generalization. Regardless of interpretation, Dropout prevents overfitting,
and there have been a large number of variants of variants that extend Dropout
to convolutional neural nets [19, 8], and other variations of dropout [20, 22,
16]. Our work is a variant of Dropout, but varies from prior work in that our
goal is no longer generalization, but compression. Structural Dropout closely
resembles Stochastic Depth [12], but instead of varying depth, ours can be
considered an ensemble along model widths, and does not require additional
skip connections.

####  2.1.1 Targeted Dropout

SD also resembles Targeted Dropout [9], but instead of dropping independently
from higher indices, as SD drops everything above a given index, and retains
some probability for running the entire network. This leads to a few key
differences, as Targeted Dropout will not be safe for pruning to arbitrary
sizes, and it must be known ahead of time the target size to prune to. SD will
also be an ensemble of $N-\textit{lower bound}$ models, where as Targeted
Dropout will be an ensemble of $2^{N-k}$ models.

###  2.2 Model Compression

Model compression is important in the era of heterogenous computing, where ML
models may have to run on mobile devices, older machines, or even inside of
embedded micro-controllers. This conflicts with the continual increase of the
size of state-of-the-art models, as many users are unable to immediately use
them due to resource constraints.

For this work, we divide model compression into two forms: architectural
(factorization, and knowledge-distillation), and non-architectural (pruning
and quantization). We will mostly not focus on factorization, as it is not
closely related to this work.

####  2.2.1 Non-Architectural Compression

“Non-architectural” compression encompasses pruning and quantization, as they
can be done without model architecture changes. Pruning is using
regularization such as $\ell_{1}$ regularization in order to set many weights
of a learned network to 0, reducing parameter count.

Quantization [21, 10] is the use of different representations such as integers
or reduced bit floating point numbers to gain more efficiency at inference
time. This has the benefit of greatly reducing memory, at the cost of reduced
per operation accuracy. Some quantization, such as half-precision floating
point, can be used during training.

Non-architectural compression is non-intrusive and can be used without
modifying the training procedure while still providing a significant speed
boost. The downside is that they are limited in the amount of savings for a
given architecture. Quantization can only save a limited amount of memory, and
ad-hoc pruning can only remove so much without a significant drop in accuracy.

Non-architectural methods do not modify the architecture of a neural net and
are orthogonal to our approach, but we do not experiment with both.

####  2.2.2 Architectural Compression

Architectural compression compresses a neural net by modifying its
architecture. For example, the Lottery Ticket Hypothesis [4] finds small
networks inside of a larger network to find embedded “Lottery Ticket”
networks. Another methodology for architectural compression is the teacher-
student model, where a large teacher network is used as a reference for a
smaller student model. In Knowledge Distillation [11], a large network’s
output is used as a soft-target for a smaller network, achieving similar
accuracy and compressing the network. Since the networks are trained
independently, the smaller network’s architecture may be different from the
original network, or may just have smaller layers.

The benefit of architectural compression is that a network can be compressed
beyond the original architecture. On the other hand, it requires deeper
knowledge, such as selecting a new architecture for knowledge distillation, or
introducing bias by factorizing layers. It also may require additional
training, which for some users may be prohibitive.

####  2.2.3 Once-For-All

Once-For-All [2] is a similar approach to our work, performing compression on
convolutional layers, looking at accuracy on ImageNet [6]. Once-for-all
provides “elastic” width, depth and kernel-size, similar to SD which has
dynamic width. The elastic width of convolutions is most similar to our work,
but to determine which features are used in smaller networks, they rely on the
$\ell_{1}$ norm of a channel’s weight. Compared to Once-For-All, SD does not
bake a heuristic into compression, and lets the network move the features
around to best optimize the objective. Their approach is designed specifically
for CNNs, whereas this work focuses on SD for linear layers, but can be
dropped into any architecture. One other key difference of Once-For-All is
that it requires fully training the whole network, before allowing for
optimization of smaller networks. Instead of this, we stochastically sample
the original network, which removes the additional stage of selecting when to
prune and train smaller networks. Finally, SD trains all models jointly as
opposed to fine-tuning smaller models.

####  2.2.4 Slimmable Networks

Another similar approach to Structural Dropout is Slimmable Networks [26, 25,
24]. Instead of using Dropout for dynamic channel width, Slimmable Networks
uses batch normalization in order to be able to control the width of the
network at inference time. It introduces an additional set of batch-
normalization parameters for each target width, and a finite number of channel
widths are selected. As compared to Structural Dropout, Slimmable Networks
requires selecting a much smaller number of target widths, storing independent
batch-norm parameters for each width, and modifying the training procedure to
accumulate gradients across all chosen widths during each training iteration.
Structural Dropout, on the other hand, does not require selecting target
widths, adds no additional parameters, and is agnostic to the training
procedure. As compared to Slimmable Networks, Structural Dropout acts as a
drop-in layer into any architecture without any tuning, and is more flexible
in that it will enumerate all possible widths.

Structural Dropout trains a hierarchical ensemble of teacher-student networks
that learn jointly, without requiring hyper-parameter selection. This helps
achieve the non-intrusive ease of use that non-architectural methods use,
while allowing compression of the model architecture.

As compared to prior work, Structural Dropout makes a few key modifications:

  1. 1.

SD removes the need to use some heuristic such as the norm of the weight in
order to decide which layers are important, baking feature importance into the
training procedure.

  2. 2.

SD requires no hyper-parameter search for target sizes, enumerating many
smaller networks stochastically during training.

  3. 3.

SD can be dropped into an existing architecture, and does not require tuning
or deep knowledge of the prior architecture, and is task-agnostic.

  4. 4.

SD does not require modifying the training procedure.

##  3 Method

Structural Dropout is defined for training in Eq. 1 and inference in Eq. 2. A
diagram of Structural Dropout is shown in Fig. 1 We also provide a few more
implementations and usage details, which are not explicitly outlined in the
equations.

###  3.1 Training Efficiency with Structural Dropout

While training with Structural Dropout, we get the benefits of pruning that
are achieved during inference. In this work, we add SD between linear layers,
after activation functions. Since SD is applied after activation, even if an
activation function is non-zero preserving ($\sigma(0)\neq 0$) the sparsity of
the layer is retained, since the activation function cannot make the sparse
vector dense. Because the vectors are guaranteed to be sparse, during training
we can prune rows and columns from linear layers rather than explicitly
passing $0$, since they are identical operations. This reduces the average
cost of training the model.

###  3.2 Coarse Structural Dropout

Since Structural Dropout trains an ensemble of models, it may take longer to
converge than the original model. On top of learning weights, the network
learns to prioritize certain features over others, making the given task more
difficult, albeit only before it has ordered features. In order to prevent a
network from having to learn how to prioritize all features separately, it may
be easier to learn clusters of features. For example, instead of selecting
every value from 1 to $k$, SD takes a parameter to select every group of $n$
elements from 1 to $k$. This speeds up training since it reduces the number of
models in the ensemble, at the cost of having fewer selections for the final
model size.

###  3.3 Lower Bounds on Features

In many cases, it may be known to a practitioner that a certain number of
features are necessary. For example, in a classification task over $n$
classes, theoretically at least $n-1$ features are necessary to produce a
meaningful distribution over classes. By providing a lower bound on the cutoff
index, we focus training time on strictly necessary features. We note that the
network will only be slower to train if the cutoff is set too low, as the
network will still attempt to optimize a small set of features, but the rest
of the features will be unaffected since they were zeroed. Thus, lower
bounding the feature size is an opt-in hyper-parameter, and can be left at a
default of 1 without causing divergence.

###  3.4 Selecting p

The choice of hyper-parameter $p$ affects how much Structural Dropout seeks to
utilize the full model versus optimizing smaller models. Setting $p=0$, the
smaller models are never optimized, and only the larger model is never
trained, and is equivalent to not having dropout. Setting $p=1$, the full
model is only trained with probability $\frac{1}{N}$, and the higher-indexed
features get trained exponentially less. In expectation, $50$% of the hidden
features will be dropped out, which is contrast to standard Dropout which
would have no elements. We opt for setting $p=0.5$ as a default. Within our
experiments, we ablate setting $p=1$ to demonstrate that it is useful to
optimize the entire model, as well as setting $p=0.01$ to demonstrate that it
is necessary to have a higher $p$ to compress more.

###  3.5 Inference Width Selection

Because there are multiple layers with SD, it is computationally to expensive
to evaluate all permutations of widths for the models. Thus, we arbitrarily
choose to make all parameters equal: $w_{1}=w_{2}=\cdots=w_{n}$. This reduces
the number of possible models from $w^{n}$ to $w$, and we exhaustively
enumerate this set of models. We leave a better search for optimal widths to
future work.

##  4 Experiments

Since our method is a layer that can be put into many architectures, the focus
of this work is gaining an intuition and demonstrating its efficacy. To do so,
we demonstrate how it works on 3 different experiments: an intuition gaining
toy example with MNIST [7], a demonstrative example of how it may be effective
in compressing arbitrary architectures with PointNet [3] and ModelNet10 [23],
and a demonstration of how it may be used in the SOTA with Local Implicit
Image Functions (LIIF) [5] for SISR.

For all of our experiments, we run on a single Intel-i7 CPU, with one NVIDIA
GTX-1060. In all diagrams showing number of parameters, we add a line from the
minimum parameter count to the maximum as a reference, since many are almost
linear. All experiments are implemented in PyTorch [17].

###  4.1 MNIST

Figure 2: Architecture for MNIST with Structural Dropout. Structural Dropout
allows for variable width fully-connected layers. During training, $i,j$ are
independently and uniformly sampled from $[1,256]$, and at inference we set
$i=j=c$, where $c$ is some constant.

Figure 3:  Size reduction of variable-width multi-layer perceptrons in MNIST.
Since the hidden layer can vary both dimensions, reduction is more than
linear.

Figure 4:  Structural Dropout is able to maintain accuracy at much smaller
widths on MNIST in a single training procedure.

To gain an intuition for using SD, we first try it on a toy example with MNIST
[7]. Our architecture is a simple multi-layer perceptron with a hidden size of
256, shown in Fig. 4. This architecture contains two Structural Dropouts,
between two fully connected layers after their respective activation
functions. The network is over-parametrized, each hidden layer has 256
neurons, and we seek to shrink it down as much as possible without significant
accuracy degradation. We perform 100 epochs of training, using the Adam
optimizer with a learning rate of $8\text{\times}{10}^{-4}$, and standard
cross-entropy loss.

After training, we then iterate over possible hidden sizes, $k$, and compute
validation loss, to generate an accuracy versus resource trade-off comparison,
as shown in Fig. 4. In addition, we also show a comparison of $k$ to the total
number of elements, as an intuition for the size compression benefits.

With the full model, we see accuracy around 98%, and with smaller sizes there
is a steep increase in accuracy at around 15 parameters, from 10%, equivalent
to random chance, up to 80%. Above that size, we see a much slower increase to
98% accuracy on the test set. The optimal is not the model with all
parameters, giving “free” compression: higher accuracy and reduced model size.
We can also select a lower $k$, trading memory for accuracy. For example, we
can select the lower quartile of accuracy at 96%, with $\frac{1}{5}$ of the
memory cost.

###  4.2 PointNet

Figure 5: Architecture for PointNet with Structural Dropout. $\sigma$, is
LeakyReLU, BN is batch normalization, and FC is fully-connected. We denote
convolutional neural nets as black boxes, as we do not attempt to compress
them in this work.

To demonstrate that our method can work on many architectures, we test SD on
PointNet [3], a model for classifying point clouds. Since this task is not
common, the model has not needed to be compressed, demonstrating that our
method can work on arbitrary models without expensive grid search while using
the original training procedure. In this work, we ignore the convolutional
layers, and add additional SD layers where previously there were none. The
architecture used for PointNet is shown in Fig. 5, where we add SD between
linear layers. We experiment on ModelNet10 [23], classifying 10 choices and
optimizing with cross-entropy loss. Since batch normalization [13] is applied
per feature in the original model, it is easily adapted to sparse layers. We
train on ModelNet10 for 100 epochs, using the given train/test split.

Results from a run of the experiment are shown in Fig. 8. Surprisingly, we
find that we are able to get performance improvements with a much smaller
parameter size than the maximum budget, with 75% of the original parameters
without accuracy loss. We consider two possibilities for why. First, it may be
the case that by sampling more models, it’s more likely to find a better one
among the set of possibilities, which is agnostic to Structural Dropout.
Second, it could be that with online knowledge distillation smaller models
learn important features from larger teacher models.

We also perform ablation of the parameter $p$ on PointNet. We observe that
when $p=1$, there is a significant boost in compression without accuracy loss
compared to the original model, but the accuracy of larger models is
significantly degraded. When $p=0.5$, there is an accuracy boost, but requires
more parameters than $p=1$. When $p=0.01$, there is even more of an accuracy
boost, but at the cost of little compression. Specifically, we see better
compression at $p=1$ at the same accuracy as the median value for $p=0.01$.
Because we are able to achieve such high compression, it indicates that
PointNet was significantly over-parameterized in its linear layers. If
PointNet were to have to required all of its features, setting $p$ lower
ensures that the full set of features gets trained.

Figure 6: PointNet parameter savings are near linear.

Figure 7:  From left to right: $p=0.01,0.5,1$. Ablation of changing $p$ using
PointNet [3]. We find that Structural Dropout achieves better maximum accuracy
with lower $p=0.01$, and higher compression with higher $p=1$.

Figure 8:  Within PointNet, we find that the highest validation accuracy is
achieved with a much smaller number of parameters. We are thus able to reduce
parameters by $\frac{1}{2}\text{ to }\frac{3}{4}$, and improve performance.

###  4.3 LIIF

Finally, we demonstrate the effectiveness of Structural Dropout on a recent
SOTA approach to single-image super resolution, LIIF [5]. LIIF consists of an
encoder and decoder, where the encoder is another super resolution
architecture such as EDSR [15], and the decoder grid-samples some hidden state
of EDSR, and passs it through a multi-layer perceptron to recover a high-
resolution version of the original image. This approach is based off of recent
advances in neural rendering that use an MLP to output feature vectors from 2D
or 3D coordinates. One downside of using MLPs for low-dimensional inputs to
other low-dimensional outputs is that they are very expensive, especially when
they need to be queried at many different points. This motivates the need for
compressing them, since they are queried many times and are the bottleneck of
some pipelines for compute and memory.

To demonstrate SD for this use case, we modify LIIF in a few ways. First,
between each linear layer in the MLP, we add a SD layer, with a lower bound of
32 and $p=0.5$. The lower-bound is a conservative estimate on the minimum
features necessary, and $p=0.5$ is the default setting. We also find in
experimentation that adding skip connections to the original architecture
improves the convergence rate. Therefore, we add new sparse skip connections
to our network to increase convergence speed. We also choose to include them
to demonstrate how to adapt non-sparse structures to our approach, as many
MLPs may use them.

In order to have sparse skip connections, we interleave two vectors rather
than concatenate one after the other. Compared to normal stacking, if there
are $n$ vectors which are sparse and the least sparse vector has $k$ trailing
zeros, their interleaving will contain $nk$ trailing zeros.

Other than these modifications, we use the original architecture and train on
Div2K [1] at $\frac{1}{4}$ resolution, with the Adam [14] optimizer and
learning rate $=$3\text{\times}{10}^{-4}$$.

Figure 9:  Using Structural Dropout with LIIF, we remain within 1 PSNR of
accuracy at 80% of the cost. We visualize every $4$th hidden size, as it is
costly to validate all possible widths.

The original reported accuracy at $\times 4$ super resolution is 29 PSNR, and
with SD achieves within $0.25$ PSNR. With SD, we are able to retain within 1
PSNR at 80% compression, as shown in Fig. 9. We validate every 4th hidden
size, due to the large cost of validating all hidden sizes. In a deeper
network with skip connections and originally without Dropout, we are still
able to add in Structural Dropout and compress the model. SD thus works as
efficient compression as a drop-in layer or replacement for Dropout in
existing architectures.

We note that in training LIIF, it became more difficult to measure
performance, as sampling different model sizes lead to random accuracy jumps.

##  5 Discussion

Structural Dropout serves as a minimal addition to existing architectures to
perform hyper-parameter search and compression. Since it does not require
expensive retraining or additional domain knowledge, it is more easy to adopt
than domain specific modifications, and is orthogonal to pruning and
quantization.

Out of our experiments, it is clear that there is a steep cliff where
information saturates, and that a significant features, between $50-80\%$, of
features can be pruned with minimal accuracy change. When more aggressively
pruning using a higher dropout rate, up to $80$% can be pruned with no
accuracy loss, as seen on PointNet.

Structural Dropout also may help performance, as purely by sampling multiple
models, one of them may perform better on the given task.

##  6 Limitations

While our method is straightforward to add into existing architectures, there
are some downsides to it.

One significant downside is that SD increases the search space, making the
problem more difficult. Since the problem is more difficult, the training
session may take longer, despite the speed up of using fewer parameters. This
training time is not significantly longer than the original, but it is not
clear how much longer. On top of increased training time, comparing all
channel widths for validation loss is slow, since there are a large number of
models to test. This can be parallelized easily if resources are available, as
unlike training the model will be read-only, otherwise a sparse search can be
performed.

Another downside of SD is that it becomes more difficult to validate and track
convergence during training. Since the model may randomly have lower accuracy
during training due to low channel width, a model’s convergence becomes
difficult to determine. Thus, it makes sense to use SD for models which have
been trained before, and prior convergence parameters have already been set.
On these models, it can also be used as a way to perform hyper-parameter
search for channel width.

In addition, while we assume that all the SD sizes should be the same at
inference, in a larger model with a variety of layers this may not be the
case. To perform an exhaustive search over all possible choices of channel
size would be expensive, so an efficient search strategy is important. One
common assumption is that each choice can be made independently, but we leave
exploration of this to future work.

Finally, our method is unable to prune entire layers, as SD is limited to
changing the width of a neural network but cannot modify its depth. Thus, a
network where the performance bottleneck is depth will not be able to get as
much benefit.

##  7 Future Work

While we show Structural Dropout’s application on FC layers, the same
principle can be extended to other kinds of layers. For example, the same idea
is applicable along the channel dimension of CNNs, allowing for pruning of
features. Another possible extension is for transformers, where it is
important to select a number of attention heads. Structural Dropout could be
applied to both attention head size, and number of attention heads. We hope
that this work is extended to explore use of Structural Dropout in a broad
variety of architectures for practical and efficient compression.

##  8 Conclusion

Structural Dropout is a method for inference-time compression, and can be used
as a drop-in layer to existing architectures to achieve substantial
compression, with minimal accuracy loss. It is the first methodology that the
authors are aware of that allows for training many arbitrarily compressed
models in a single training session, and then being to deploy them all
jointly, at the cost of only deploying the largest model. From our
experiments, we hope that it is evident that Structural Dropout is a powerful
tool for compressing neural networks.

## Acknowledgments and Disclosure of Funding

No funding was received for this work.

## References

  * [1] Eirikur Agustsson and Radu Timofte.  Ntire 2017 challenge on single image super-resolution: Dataset and study.  In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR) Workshops, July 2017.
  * [2] Han Cai, Chuang Gan, Tianzhe Wang, Zhekai Zhang, and Song Han.  Once for all: Train one network and specialize it for efficient deployment.  In International Conference on Learning Representations, 2020.
  * [3] R. Qi Charles, Hao Su, Mo Kaichun, and Leonidas J. Guibas.  Pointnet: Deep learning on point sets for 3d classification and segmentation.  In 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 77–85, 2017.
  * [4] Tianlong Chen, Jonathan Frankle, Shiyu Chang, Sijia Liu, Yang Zhang, Zhangyang Wang, and Michael Carbin.  The lottery ticket hypothesis for pre-trained bert networks.  In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 15834–15846. Curran Associates, Inc., 2020.
  * [5] Yinbo Chen, Sifei Liu, and Xiaolong Wang.  Learning continuous image representation with local implicit image function.  In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 8628–8638, 2021.
  * [6] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei.  Imagenet: A large-scale hierarchical image database.  In 2009 IEEE Conference on Computer Vision and Pattern Recognition, pages 248–255, 2009.
  * [7] Li Deng.  The mnist database of handwritten digit images for machine learning research.  IEEE Signal Processing Magazine, 29(6):141–142, 2012.
  * [8] Terrance DeVries and Graham W Taylor.  Improved regularization of convolutional neural networks with cutout.  arXiv preprint arXiv:1708.04552, 2017.
  * [9] Aidan N. Gomez, Ivan Zhang, Kevin Swersky, Yarin Gal, and Geoffrey E. Hinton.  Learning sparse networks using targeted dropout.  CoRR, abs/1905.13678, 2019.
  * [10] Suyog Gupta, Ankur Agrawal, Kailash Gopalakrishnan, and Pritish Narayanan.  Deep learning with limited numerical precision.  In Proceedings of the 32nd International Conference on International Conference on Machine Learning - Volume 37, ICML’15, page 1737–1746. JMLR.org, 2015.
  * [11] Geoffrey Hinton, Oriol Vinyals, and Jeffrey Dean.  "distilling the knowledge in a neural network".  In NIPS Deep Learning and Representation Learning Workshop, 2015\.
  * [12] Gao Huang, Yu Sun, Zhuang Liu, Daniel Sedra, and Kilian Q. Weinberger.  Deep networks with stochastic depth.  In Bastian Leibe, Jiri Matas, Nicu Sebe, and Max Welling, editors, Computer Vision – ECCV 2016, pages 646–661, Cham, 2016. Springer International Publishing.
  * [13] Sergey Ioffe and Christian Szegedy.  Batch normalization: Accelerating deep network training by reducing internal covariate shift.  In Francis Bach and David Blei, editors, Proceedings of the 32nd International Conference on Machine Learning, volume 37 of Proceedings of Machine Learning Research, pages 448–456, Lille, France, 07–09 Jul 2015\. PMLR.
  * [14] Diederik P. Kingma and Jimmy Ba.  Adam: A method for stochastic optimization.  CoRR, abs/1412.6980, 2014.
  * [15] Bee Lim, Sanghyun Son, Heewon Kim, Seungjun Nah, and Kyoung Mu Lee.  Enhanced deep residual networks for single image super-resolution.  In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR) Workshops, July 2017.
  * [16] Dmitry Molchanov, Arsenii Ashukha, and Dmitry Vetrov.  Variational dropout sparsifies deep neural networks.  In Proceedings of the 34th International Conference on Machine Learning - Volume 70, ICML’17, page 2498–2507. JMLR.org, 2017.
  * [17] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala.  Pytorch: An imperative style, high-performance deep learning library.  In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems 32, pages 8024–8035. Curran Associates, Inc., 2019.
  * [18] Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov.  Dropout: A simple way to prevent neural networks from overfitting.  Journal of Machine Learning Research, 15(56):1929–1958, 2014.
  * [19] Jonathan Tompson, Ross Goroshin, Arjun Jain, Yann LeCun, and Christoph Bregler.  Efficient object localization using convolutional networks.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June 2015.
  * [20] Li Wan, Matthew Zeiler, Sixin Zhang, Yann Le Cun, and Rob Fergus.  Regularization of neural networks using dropconnect.  In Sanjoy Dasgupta and David McAllester, editors, Proceedings of the 30th International Conference on Machine Learning, volume 28 of Proceedings of Machine Learning Research, pages 1058–1066, Atlanta, Georgia, USA, 17–19 Jun 2013. PMLR.
  * [21] Naigang Wang, Jungwook Choi, Daniel Brand, Chia-Yu Chen, and Kailash Gopalakrishnan.  Training deep neural networks with 8-bit floating point numbers.  In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
  * [22] Sida Wang and Christopher Manning.  Fast dropout training.  In Sanjoy Dasgupta and David McAllester, editors, Proceedings of the 30th International Conference on Machine Learning, volume 28 of Proceedings of Machine Learning Research, pages 118–126, Atlanta, Georgia, USA, 17–19 Jun 2013. PMLR.
  * [23] Zhirong Wu, Shuran Song, Aditya Khosla, Fisher Yu, Linguang Zhang, Xiaoou Tang, and Jianxiong Xiao.  3d shapenets: A deep representation for volumetric shapes.  In 2015 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 1912–1920, 2015.
  * [24] Jiahui Yu and Thomas S. Huang.  Network slimming by slimmable networks: Towards one-shot architecture search for channel numbers.  CoRR, abs/1903.11728, 2019.
  * [25] Jiahui Yu and Thomas S. Huang.  Universally slimmable networks and improved training techniques.  In Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV), October 2019.
  * [26] Jiahui Yu, Linjie Yang, Ning Xu, Jianchao Yang, and Thomas Huang.  Slimmable neural networks.  2019\.  Publisher Copyright: © 7th International Conference on Learning Representations, ICLR 2019. All Rights Reserved.; 7th International Conference on Learning Representations, ICLR 2019 ; Conference date: 06-05-2019 Through 09-05-2019.