Packing: Towards 2x NLP BERT Acceleration
Authors: Matej Kosec
Sheng Fu
Mario Michael Krell
Venue: NeurIPS 2021 Submitted (2021)
Keywords: deep learning
BERT
IPU
GPU
hardware-acceleration
padding
Wikipedia
NLP

Abstract: We find that at sequence length 512 padding tokens represent in excess of $50\%$ of the Wikipedia dataset used for pretraining BERT (Bidirectional Encoder Representations from Transformers). Therefore by removing all padding we achieve a 2x speed-up in terms of sequences/sec. To exploit this characteristic of the dataset, we develop and contrast two deterministic packing algorithms. Both algorithms rely on the assumption that sequences are interchangeable and therefore packing can be performed on the histogram of sequence lengths, rather than per sample. This transformation of the problem leads to algorithms which are fast and have linear complexity in dataset size. The shortest-pack-first histogram-packing (SPFHP) algorithm determines the packing order for the Wikipedia dataset of over $16$M sequences in $0.02$ seconds. The non-negative least-squares histogram-packing (NNLSHP) algorithm converges in $28.4$ seconds but produces solutions which are more depth efficient, managing to get near optimal packing by combining a maximum of $3$ sequences in one sample. Using the dataset with multiple sequences per sample requires additional masking in the attention layer and a modification of the MLM loss function. We demonstrate that both of these changes are straightforward to implement and have relatively little impact on the achievable performance gain on modern hardware. Finally, we pretrain BERT-Large using the packed dataset, demonstrating no loss of convergence and the desired 2x speed-up.


Packing: Towards 2x NLP BERT Acceleration
Anonymous
Abstract
We find that at sequence length 512 padding tokens represent in excess of 50% the Wikipedia dataset used for pretraining BERT (Bidirectional Encoder Represen- tations from Transformers). Therefore by removing all padding we achieve a 2x speed-up in terms of sequences/sec. To exploit this characteristic of the dataset, we develop and contrast two deterministic packing algorithms. Both algorithms rely the assumption that sequences interchangeable and therefore packing can be performed on the histogram of sequence lengths, rather than per sample. This transformation of the problem leads to algorithms which are fast and have linear complexity in dataset size. The shortest-pack-fin algorithm determines the packing order for the Wikipedia dataset of over 16M sequences in 0.02 seconds. The non-negative least-squares histogram packing (NNLSHP) algorithm converges in 28.4 seconds but produces solutions which are more depth efficient, managing to get near optimal packing by combining maxi- mum of sequences in one sample. Using the dataset with multiple sequences per sample requires additional masking in the attention layer and a modification of the MLM loss function. We demonstrate that both of these changes are straightforward to implement and have relatively little impact on the achievable performance gain on modern hardware. Finally, we pretrain BERT-Large using the packed dataset, demonstrating no loss of convergence and the desired 2x speed-up.
eattgram-packing (SPFHP)
histogram-packing
Introduction
Since its introduction in 2019, BERT 5 has been the backbone driving the most exciting advances in Natural Language Processing (NLP). Pre-training BERT from scratch requires substantial compu- tational resources which may be out of reach for researchers and industry professionals. To some extent this has been addressed by the public release of pre-trained models of different sizes and depths [20] Available sizes range from tiny (2 layers with hidden size 128) to large (24 layers with hidden size 6 [5] The introduction of ALBERT 14 further improved the accessibility of larger models. However, the dependence on pre-trained models limits the ability of researchers to explore new backbone architectures. Furthermore, limits the extent to which practitioners in industry can leverage internal datasets and adapt the model to their particular needs. Hence, any approach that speeds up the pre-training process desirable from an economical as well as environmental perspective.
In this paper, we present some methods to enable researchers accelerate the pre-training BERT by as much as 2x. The de-facto pre- trainini dataset Wikipedia, well as many other NLP datasets, show a positively skewed distribution of sequence lengths. We show that padding tokens (wasted compute) represent 50% of all tokens of the Wikipedia pre-training dataset at sequence length 512. Overall, the sample lengths range between tokens up 512 (see Figure Tb. Samples of length 512 represent only 23.5% of the dataset.
While processing the padding tokens wastes compute, is the most standard approach for leveraging modern massively-paralle compute especially on GPUs. These are most efficient when applying the same operation each sequence in batch. By padding all sequences the same maximum sequence length, they can easily be batched. The most obvious way to reduce the extent of padding
Preprint. Under review.

---

in the dataset is to group samples by size before batching, i.e., process the shorter samples together and longer samples together. Typically such an approach would still involve padding but less than padding all sequences to the same maximum length. For example BERT [S] is pre-trained in two phases, where the first phase uses sequence length 128 for 900K steps and the second phase uses sequence length 512 for 100K steps. However even by splitting the training in this way, the wasted compute due to padding is approximately 20% (see Figure D) Another example of this approach is Faster Transformer [8] which groups samples of similar size together in one batch and fills up with padding only to the maximum length in this batch.
More advanced approaches for reducing the padding overhead rely on custom computational kernels. Loosely these are referred as "un-padding" approaches. In Effective Transformer 4 the input batch is provided as a padded matrix but padding values are dynamically removed and restored during different calculation stages. While un-padding implementations are highly sophisticated and are able to completely circumvent the processing of padding tokens, they introduce a significant overhead due to the multiple GPU kernel launches (i.e. one kernel per sequence rather than one kernel per batch). Additionally the time to process each batch will fluctuate depending on the sequence lengths in each batch i.e. batches with only shorter sequences will typically be processed faster. When working with more than one accelerator, this variability in throughput results in all devices in the cluster waiting for the device with the most compute intensive batch to finish processing. As such, un un-padding approaches are not appropriate for deployment on large clusters.
The "packing" based approach introduced in this paper offers significant advantages over un- un-padding approaches. Firstly, packing is implemented directly at the framework level and requires no additional custom kernel implementations. Secondly, the processing time for each batch independent of the content of the batch, allowing the packing based approach to maintain the same speed-up whether running on a single device or thousands. Third, each batch now contains a consistent number of real tokens.
While we demonstrate the effectiveness of packing specifically on the Wikipedia dataset, packing SQUaD 19 or GLUE datasets [22 p3 for BERT also leads to significant speed-ups (some in excess of 9x) II (sections
A and B}. The effectiveness of packing is a result of both the length distribution of the documents in the source datasets as well as the different text preprocessing steps for BERT The use of bi-directional self-attention in BERT implies that the input sequences should contain complete sentences. If a sentence is abruptly cut short, the hidden state on other (preceding) tokens in the sequence will be affected. Language models with causal attention (only attending to previous tokens in the input) do not have this issue. For such models, if sequence is cut short at an arbitrary token, the other tokens (which occur earlier in the sequence) will not be affected. This ability to cut sequences arbitrarily completely trivializes the packing problem. For instance, GPT-3 K is trained with a maximum sequence length of 2048 where a single sequence may contain multiple segments separated by a special end of segment token. The last segment in each sequence is simply cut to meet the sequence length requirement. In the interest of computational efficiency GPT-3 does not mask the attention between different segments in sequence. In contrast, the packing approach presented in this paper introduces a mask in the attention layer (see Section 3.2) to prevent cross-contamination between examples in pack. This ensures that the characteristics of the original dataset and model are matched as closely as possible.
In summary, the contributions of the paper are as follows. In Section 2 we produce histograms of the Wikipedia pre-training dataset showing the high percentage of padding tokens. We present two new deterministic packing algorithms which easily pack datasets with millions of sequences in matter of seconds (or less). We empirically show that the proposed packing algorithms produce a nearly-optimal packing scheme for Wikipedia pre- pre-training dataset. We show how to compute the per-sequence loss by incxpensively un -n-packing the loss. We provide code for building an attention mask which prevents attention between tokens of different sequences in the pack. We demonstrate that the convergence of the BERT large model on the packed dataset is equivalent to that on the un- un- packed dataset. We show that with the packed dataset, we able to achieve nearly 2x throughput increase on the Wikipedia sequence length 512 pre-training dataset.
2

---

2 Wikipedia BERT pre-training dataset
BERT is pre-trained using masked-language modelling and next-sentence prediction on large corpus of Wikipedia articles [.. Each sequence is composed of one <CLS> token followed by the first part of sentences, followed by a <SEP> token, and then finally the second part of sentences. Because parts are created in sentence-level increments there no token-level control of sequence length. Together with already short parts, empirically, this leads to significant levels of padding, especially for longer maximum sequence lengths (see Figure D At sequence length 128 (commonly used in phase 1 of pre-training) the theoretical speed-up is around 1.2, at sequence length 384 this increases to 1.7, and finally at sequence length 512 (commonly used for phase 2 of pre-training) it is 2.0. Despite the widespread use of the Wikipedia dataset for pre-training BERT such histograms have, to the best of our knowledge, not been published previously. This has perhaps lead to the underestimation of the speed-up opportunity available. To things into perspective, the sequence length 512 dataset contains 8.33 billion tokens, of which 4.17 billion are padding tokens.
max. sequence length: theoretical max. speed-up: 1.210
max. sequence length: 384
max. sequence length 512 theoretical max. speed-up up: 2.001
theoretical max. speed-up: 1.742
0.005
0.005
0.005
30.6%
23.5%
probability density
0.004
0.004
0.003
0.003
0.002
0.001
25
50
75
100
125
100
200
300
400
0
100
200
300
400
500
sequence length
sequence length
Sequence length
Figure 1: Wikipedia BERT pre-training dataset sequence length histograms (token count excluding padding) for different maximum sequence lengths. Based the Wikipedia article dump from October 1st 2020. The theoretical speed-up relates to not using any padding tokens and not having any overhead from processing the different lengths.
Methods
Our approach consists of three distinct components. Firstly, we pack the data efficiently during pre-
processing make full of the sequence length (Sections 3.1.1 and 3.1.2 see also 1 Section D) Secondly, we adapt the self-attention mask to prevent the model from attending between different sequences in the same pack (Section 3.2). Other components of the model, such as the feed-forward layer [21], operate on a per-token basis and do not require any modification. Thirdly, we compute the loss and accuracy on a per-sequence basis to match the canonical BERT implementation (Section (.3 This is achieved by unpacking the per-pack loss at the framework level, without the use of custom kernels. Additionally, we provide suggestions for hyperparameter adjustment (Section 3.4) that lead to analogous convergence behavior between the packed and un un-aacked BERT implementations.
3.1 Packing algorithms
The problem of optimally concatenating multiple sequences of different length until maximum combined length is reached can be directly framed as bin bin-packing or stock cutting problem. Since an exact solution strongly NP-complete [33, we propose two new heuristic algorithms that are tailored to this particular instance. A detailed introduction to packing is provided in (Section D)
3.1.1 Shortest-pack-fin eestogram-packingg (SPFHP)
Shortest-pack-firs histogram-packing (SPFHP) consists of three main components. First, the packing algorithm works on the bins in the sequence length histogram (with bin size 1) rather than the individual samples. Second, we operate on the sorted data from longest to shortest sequences. This comes basically for free due to the use of histograms. Third, we apply the worst-fit fit algorithm [ 26

---

onto this histogram, where the currently observed sample goes to the pack that has the most space left to reach maximum packing depth ("shortest-pack-ins first". If the sample does not fit, a new pack is created. A variant is to limit the packing depth, in other words the maximum number of sequences that are allowed in a pack. Therefore, we only extend an existing pack if it is not already at maximum packing depth. The detailed code for the algorithm is provided in [ (listing 3)
3.1.2 Non-negative least squares histogram-packing (NNLSHP)
The proposed NNLSHP algorithm is based on re-stating the packing problem (weighted) non- negative least squares problem (NNLS) 2 of the form WAr = wb where x 2 O. The vector b is the histogram containing the counts of all the sequence lengths in the dataset. Next, we define the A matrix (the "packing matrix") by first generating list of all possible sequence length combinations ("strategies") that add up exactly to the maximum sequence length. We focus specifically on strategies that consist of at most 3 sequences per pack (independent of b) and encode each strategy of the sparse matrix A. For example, a strategy consisting of the sequence length 128, 128, and 256 in represented column vector that has the value 2 at the 128th row, the value 1 at the 256th row, and zero at all other rows. The variable describes the non-negative repetition count for each strategy. So 24 in the ith row of z means that the strategy represented by the ith column of A should repeat 24 times. Moreover, in the un- un-weighted setting, Az states that we would like to "mix" the pre-defined strategies (columns of A) such that the number of samples matches the histogram b, and where each strategy is used x 2 0 times. We use the residual weight w to control the penalization of the Ar b residual on different sequence lengths (different rows of b). Heuristically, the weight of 0.09 for all sequences of length 8 or smaller because they are considered acceptable padding sequences. All other sequence lengths get weight 1. After solving wAr = wb for 0 using an off-the-shed solver we obtain a floating point solution, which means that the repetition round counts not necessarily integers. Since we cannot use non-natural number of strategies, the solution å to the nearest integer. The error introduced by this rounding is found to be negligible. Further details are provided in (Section D.4
column
set
3.2 Attention masking for packed sequences
To maintain an implementation that is consistent with the un-packed version, we need to able to prevent attention between tokens in the pack which belong to different sequences. Other imple- mentations use custom attention kernels which reconstruct padding. Instead, we propose directly masking the attention matrix with block-diagonal mask to be applied before the attention. This is straightforward to implement in modern frameworks (see Figure 2). Naturally, there is a cost to both the mask construction and applying it to the attention matrix (see Table Section
mask up ([I,
2]])
imput
prtooone_aeek eg.eq (zack, mast.
0, nask
a for use with sortnaz: softnax wask tf. (zero__2 onn pask, 0, -000)
Figure 2: Attention mask code sample [left] and example zero-one mask [right].
3.3 Calculating per-sequence loss and accuracy
Canonical implementations of BERT compute the cross-entropp loss for the masked language model on per-sequence basis. Simply feeding packs of sequences to the same implementation of cross- entropy would consequently result in per-pack weighting of the loss. In other words, the overall loss on the micro-batch would sum-up the losses the individual packs, rather than individual sequences. As a result the packed BERT model would converge to a different optimum. For instance, a pack of a single sequence would contribute to the loss the same extent as a pack of three sequences. In other words, the long sequence (single per pack) is given the same weight as the three shorter sequences in the pack of three. Empirically, degradation of masked-language modelling accuracy on shorter sequences is indeed observed when not modifying the loss to account for packing.
We avoid the ambiguous terms "bin" and "sample/seqqence"" and us "pack" instead for the entity that the document parts get aggregated in during packing. We use bin for the histogram and sequence could be a document part.

---

To recover the per-sequence averaging behavior of the canonical un un-packed BERT implementation. it is not sufficient to simply weight the loss (accuracy) on each pack by the number of sequences contains, because the sequences in the pack have different lengths and therefore should not use the same weight.
To implement per-sequence loss, we effectively "unpack" the incoming logits and labels by working with the per-token loss. We compute the loss on all tokens belonging the first sequence, then all tokens belonging to the second sequence, and so on. However, rather than looping through the sequences index in this way, we compute on all indexes in parallel. This minimizes the latency overhead of un in-packing the loss calculation. We use the "masked Im weight" [ input tensor to represent which sequence a given masked token belongs to (0, 1, 2 and so on). This is consistent with the canonical BERT implementation where this input takes value of either I (belonging to the sequence) or O (belonging to padding) as detailed in Listing T to the
The same methodology can be applied
prediction loss and accuracy.
Listing I: Loss calculation
aequences
say vazy
xequences_in. in_bacchhh tf.rreduce_nn eun (tf..rddce......... reduce_ Inn -13)
asquences_in, in_binnahhhhhhe ca.caxt (anquanses, intpeenee__n_atttlleee if if..foat32)
# Create the 0/1 nask that will be used to un-packed sequencea
lr. rta.rra (naaked_
sequecca,anlection
resbappp rangea. ses_sqqunnssssprrpppe 1). [1, -1, 13)
7 reuucce_celection. tf. (n,
- sepuesce,colecstnn, tf..lost32)
Apply the rank un-pack the loss
all_per_tokes_ tf.reshage (nlk.per_kee,, [6,
10 all_per_eepoece requenco_celectton nil_.per.toeen
11 # Narnalize the par-aaquance loxs by the nanber of aln-tokans in the xequence (ax ix standard)
12 attempted
(t.reecc,,uun(xqqqe selleette.electioo.. -1, kespdita-Prue)
dividing by attempted 15 E Average par-hatch less (so contributions frox different batchez are conparable)
13 abtenpted attenpted (attepttttterped
ffl
prevent
14 all_gar__nquancs
16 la.loss re. sun (nl1. rergueeene)) requence//sesseeneess /eegseeeeseeeeeeeeeeeeeeeeeeeeee batch
3.4 Hyperparameter adjustment
In terms of convergence behavior, the primary consequence packing an increase in the effective batch size (with respect to sequences and tokens) with some variation over different iterations. For instance, if each pack on average contains two sequences, the batch size (per optimization step) is effectively doubled on average. While one could subsequently reduce the computational batch size by the packing factor (average number of sequences per pack) and keep using the same hyperparameters, this is typically not desirable as it might imply under-utilizing the memory/compute.
Instead, we propose an approximate heuristic for updating the decay parameters of the LAMB optimizer 225 For a packed dataset with a packing factor p. we update the decay parameters as: 31 = 8r B2 S.. For p 2, this corresponds the exact parameters for calculating momentum and velocity. when updating with the same gradient twice [[Sectio E). A common approach is to scale the learning rate with the batch size. Note however, that we take the mean gradient instead of an accumulated sum and have already a correction by the number of samples in that regard.
Since these adjustments are only heuristics the convergence of the model will be comparable but not identical. In particular, it is unlikely that simply adjusting the hyperparameters will fully undo the impact of the increased batch size. However, with these adjustments, researchers should be able to continue to use existing configurations.
Experiments
4.1 Bin-packing algorithm comparison
We evaluate our algorithms using the following metrics: number of packs, number of all tokens, number of padding tokens, solution time of the packing algorithm (after histogram and strategy creation), number of strategies used, packing efficiency (the fraction of non-padding tokens in the packed dataset), the speed-up achieved compared to not packing (depth 1), and the average number of sequences per sample (packing factor). For SPFHP, we analyse different (maximum) packing depth, since packing is less efficient with smaller depth and we want to get general understanding on how the packing depth influences the processing time. For NNI SHP, we focus on packing depth because it packs the data sufficiently well.
5

---

For the speed-up up analysis, we focus on the intelligence processing unit (IPU) [10] (IPU-M2000, 16 accelerator chips). A GPU dynamically loads the code into the accelerator; in contrast, the IPU works with static precompiled kernel that gets loaded onto the chip only at the beginning. While other approaches result excessive padding or continuous changes of the code, our approach can work with the same code for the whole dataset. So in this setting the IPU architecture would especially benefit from our approach since it avoids code changes. Nevertheless, it can be applied to any implementation on GPU or TPU. For determining the speed-up, we take advantage of the precompiled kernel. Since time measurements are quite noisy, we can profile the kernel and how many cycles it takes for processing a batch. That way, from processing the additional attention masking and for unpacking the loss. Combining overhead and packing factor, get the speed-up estimate. No experiment repetitions are required since the algorithms and measurements are deterministic.
determine the overhead (in cycles)
The main results for the performance metric evaluation are displayed in Table The processing time for SBFHP was around 0.03s and independent from the packing depth. We see that the overhead slightly increases with packing depth but that the benefits of packing outweigh the cost. The best speed-up is obtained with NNLSHP at depth 3. With a value of 1.913, it is close to the theoretical upper bound of 2.001. The results show that efficiency, packing factor, and speed-up can be viewed changealan. The amount of time needed to process a sample (a pack of sequences) is barely changed relative to the un packee implementation. The packing factor the improvement in efficiency effectively provide an accurate estimate of the speed-up.
pack. depth
pack. algo.
# packs
efficiency
pack.
overhead
realized
[M]
(%)
factor
(%)
speed-up
none
16.280
49.97
1,000
0.000
1.000
2
SPFHP
10.102
80.52
1.612
4.283
1.544
3
SPFHP
9.095
89.44
1.790
4.287
1.716
3
NNLSHP
8.155
99.75
1.996
4.287
1.913
4
SPFHP
8.659
93.94
1.880
4.294
1.803
8
SPFHP
8.225
98.90
1.979
4.481
1.895
16/max
SPFHP
8.168
99.60
1.993
4.477
1.905
Table 1: Key performance results of proposed packing algorithms (SPFHP and NNLSHP).
Packing depth describes the maximum number of packed sequences. Packing depth 1 the baseline BERT implementation. Setting no limit resulted in maximum packing depth of 16. The number of packs describes the length the new packed dataset. Efficiency the percentage of real tokens in the packed dataset. The packing factor describes the resulting potential speed-up compared to packing depth With overhead, we denote the percentage decrease throughput due to changes to the model to enable packing (such as the masking scheme introduced in Section B.2). The realized
speed-up is the combination of the speed-up due to packing (the packing factor) and the decrease in throughput due to the overhead. It is used to measure the relative speed-up in throughput and the overhead from masking and loss adjustment.
4.2 Learning Curves and Hyperparameter Adjustment
For depth (classic BERT) and NNLSHP with depth 3, we additionally evaluate on the MLPerf 0.7 BERT pre-training benchmark 15 Briefly, this involves training from a standard checkpoint to masked-language model accuracy of 71.2% using million sequences with a maximum length of 512 tokens (refer to [16 for details). Following this standardized benchmark supports reproduction of results even on other systems and makes sure that the reproduction effort is moderate and setup rules clearly documented. We compare the resulting speed-up as well as the respective learning curves by evaluating the data on a held-out validation dataset. The objective of this additional evaluation is to analyse if convergence behavior is changed by the packing strategy and if the theoretical speed-up can be achieved in practice.
With packing, we effectively increase the average batch size by the packing factor (== 2). However, with a different batch size, different hyperparameters are required (see Section 3.4 and there is no mapping that will generate exact matching of results but only heuristics. In a first comparison, we use the same hyperparameters when comparing packed and unpacked training except for cutting the accumulation count by half. This way, make sure that the batch size is constant on average.

---

In the second comparison, we evaluate our heuristics and how they compensate the difference in batch size. This setup more desirable because is beneficial to use the hardware its full potential and cutting the batch size by half usually reduces throughput. In the third comparison, we compare two optimized setups.
The learning curves are displayed in Figure S In the first setup, we see the curves almost matching perfectly when normalizing by the numbers of samples processed. Differences can be explained by the variation of the number of sequences in the packing batch, and general noise in the training process. Especially after the initial phase, the curves show a mear-identical match.
The second setup shows bigger differences since changing the batch size and hyperparameters changes the training dynamics. We observe slower convergence early in training due to the increased batch size. This is expected. The adjustment of the learning rate actually decreases performance probably because we correct for the increased number of sequences already in the modified loss. With the adjustment of the decay parameter of LAMB, we see matching performance at the later training stages. However, is not feasible to completely recover the early convergence behavior of the smaller batch size by adjusting the hyperparameters. For instance doubling the batch size of unpacked BERT to 3000 and adjusting the LAMB decay parameters leads to more of a slow down in convergence than when running packed BERT with a batch size of 1500 and a packing factor of 2. Overall, in practice we observe higher acceleration than the estimated 1.913 that goes beyond 2x. We explain this with slightly better fitting hyperparameters and improved data transfer.
3.5
classic bs: 1500, bete: 0.81
classic, beta: 0.81
3.5
clessic. bs: 1500, bete: 0.51 cassic, 3000, beta:
3.0
packed, 768*2, beta. 0.81
Booming bass
pecked, bela: 0.66, double Ir
packed,
San 100
3.0
packed. ebs: 1500*2. beto: 0.66
packed double
2.5
2.5
2.0
2.0
1.5
0.5
1.5
2.0
samples
1e6
samples
1e6
relative time
Figure 3: Comparison of learning curves for packed and unpacked processing with [left] same effective batch size (ebs is batch size times packing factor), [middle] different heuristic adjustments of the hyperparameters (batch size 1500 for all runs, such that ebs for packed runs is 1500 * 2), and [right] realized conveeeecoeeeeeeeee speed-up from packing.
4.3 Scaling Analysis: Impact of the number of accelerators
A further advantage of packing over competing un-padding approaches is the inherent load balancing provided by packing. So called un-padding approaches rely on dynamically launching custom kernels that ignore padding. A stated advantage of such implementations is the ability to avoid computing the complete (512 x 512) attention matrix. This provides additional computational savings compared to packing, where the attention matrix is computed in its entirety and then masked. Because of these additional savings, un-padding can exceed the theoretical upper bound for speed-up from packing (2.013 on Wikipedia). As result of the dynamic nature of the approach, the processing time with un un-padding is different for each sequence in the batch, and the amount of time required to process a batch of sequences will be determined by the processing time of the longest sequence in the batch (with the sequences being processed in parallel). Furthermore, in the multiple accelerator setting the processing time on each device will vary depending on the sequences in the batch that it receives. Devices which finish early have to wait for the slowest device to finish before exchanging gradients. This load -eadlimbllance between the devices (and inside the batch) leads a considerable decrease in the speed-up from un- un-padding as the number of accelerators is increased (see Figure D.
In contrast, packing (our approach) is inherently load-balanced. The processing time each accelerator is independent of the content inside the batch received by the device. Any number of accelerators can therefore operate in unison without having to wait for the slowest batch to process (all per-device batches are equally fast).
To demonstrate the severity of the load-imbalance issue, we consider the scaling of an un-padding approach with a per-device batch size of 32 running on eight devices 17.. From there, we readily extrapolate the performance to both larger and smaller cluster sizes by fitting a Gumbel distribution
7

---

to the observed processing times [ (Section F. On a single device with batch size 32 un un-padding outperforms packing and exceeds the theoretical upper-bound for packing.
As the number of devices increases to two or more, the proposed packing approach outperforms the dynamic un-padding approach. On cluster with 32 accelerators the speed-up from un-padding drops to 50% and with 2048 devices the speed-up is only 30%. In contrast, the speed-up due to packing independent of the number of accelerators and stays at 1.913. Switching smaller batch size would reduce the load-imbalance issue to some extent, but would also result in under-utilization of the available memory and compute.
1913
1.70
1800
1.400
1.30
theorinical upper-bound
packing tour spproach! ur-pedding padding
1100
1000
32
25b
2048
Figure 4: Comparison of the theoretical speed-up achievable as the number of accelerators is increased.
5
Conclusion
We showed that packing can be easily implemented without the need for any custom kernels while still providing 2x speed-up. Additionally, showed that any additional speed-ups resulting from dynamic un-padding approaches diminish for even moderate batch sizes or when additional accelerators are added. In contrast, packing is baad-balanced and maintains the 2x throughput when scaling to large numbers of accelerators.
Furthermore, the computational overhead introduced by the attention mask and the packed per- sequence loss are small compared to the achieved acceleration. This overhead remains below 5% for all tested packing depths. The efficient packing algorithms presented in this paper enable us to pack millions of sequences in a matter of seconds. Compared to both the pre-processing time for the Wikipedia dataset and the training runtime, this overhead is negligible. Furthermore, showed that performing packing as pre-processing step does not significantly impact the training convergence. Our proposed hyperparameter adjustment scheme additionally helps practitioners casily modify existing validated optimizer settings for use with packed BERT. Further exploration of hyperparameter selection is left to future work.
When performing packing as pre- rre-processing step, the proposed NNLSHP and SPFHP methods achieve optimal compression efficiency. In this offline setting, we able to build a histogram of the dataset, and thus achieve linear time complexity with respect to the number of samples. This makes packing modern datasets with millions of sequences possible. In the future, it would be interesting to extend SPFHP to the online setting where a histogram of the entire dataset cannot be built. Another interesting direction is the packing of images of different sizes help accelerate computer-vision applications. This is especially relevant given the recent advances in the use of transformer-based approaches in the computer vision domain, for example the visual transformer 24 Masking out the self-attention within transformers is casier to implement than avoiding cross- cooss-onttamiatioon of convolutions applied to packed images. Finally, packing could potentially eliminate the need for two phase pre- vre-training of BERT. Using short sequences in the first phase to reduce the waste from padding no longer attractive for packed sequence BERT where the padding essentially negligible proportion of the tokens. Furthermore, the argument that the model should first learn short-term dependencies by training on short sequences neglects the fact that these same short-term patterns can be learned from longer sequences. In fact, longer-sequences may contain multiple short patterns, while also maintaining long-range consistency. Future work should explore training packed BERT from scratch and the impact of packing fine-tuned performance.

---

Broader Impact
We showed that when pre-training BERT on Wikipedia, the computational overhead taken to process padding tokens is roughly 50%. By eliminating this wasted computational time, the approach presented in this paper paves a way to halving the carbon footprint of training BERT-based models.
Furthermore, our approach circumvents the need for custom kernels, making the benefits of packing readily accessible broader audience of NLP practitioners. As such will have a positive impact on the NLP community, and do not see any disadvantage of using this approach.
hopeful the research
Future work would need to investigate the applicability of packing on text produced by different cultures and in different languages. We have already shown that the speed-up resulting from using our methods does not only occur when pre-training BERT on Wikipedia but also on other datasets such SQUaD and GLUE. Furthermore, the sentence length distribution of the original English language text shows similar characteristics. Our research leads us to believe that compressible distributions arise naturally in language tasks and beyond, for instance in DNA sequence lengths [9] and protein lengths 8. Many such sequence modelling workloads are based on variations of the /raa//ransrorm architecture and would therefore easily benefit from our acceleration.
Failures NLP can have a big impact on society; many technologies, such as Alexa, Siri, and Google Home, rely on them. Whilst any enrors arising from our approach can be avoided, one potential source of eтrоr comes from the implementation. Both the attention mask and the per-sequence loss need be modified to support packing. These changes are significantly smaller than those required by custom kernels, however they may still be time consuming to implement and debug. To help mitigate the risk of any implementation errors, share reference implementations of the required changes in the supplemental material [
References
[1] ANONYMOUS. Supplemental Material for "Packing: Towards 2x NLP BERT Acceleration", 2021.
[2] BRO, R., AND DE JONG, S. A fast non--neaaivity-coosttrnnee least squares algorithm. Journal of Chemometrics 11, 5 (sep 1997), 393-401.
[3] BROWN, T. B., MANN, B., RYDER, N., SUBBIAH, M., KAPLAN, J., DHARIWAL. P.,
NEELAKANTAN, A., SHYAM, P., SASTRY, G., ASKELL, A., AGARWAL, S., HERBERT-VON VOSs, A., KRUEGER, G., HENIGHAAN, T., CIILLD, R., RAMESII, A., ZIEGLER, D. M., WU, J., WINTER, C., HESSE, C., CIEN, M., SIGLER, E., LITWIN, M., GRAY, S., CHESS, B., CLARK. J., BERNER, C., McCANDLISII S., RADFORD, A., SUTSKEVER, I., AND AMODEI, D. Language Models are Few-Shot Learners. In Advances in Neural Information Processing Systems 33 pre- pre-proces (NeurIPS 2020) (may 2020).
[4] BYTEDANCE INC. Effective Transformer. https: httes:://ittuubccoom wttp:/uuw..oomm/yeeeannonaaaaaaa eff.etttiieceeeccciieii.......e transformer 2021.
[5] DEVLIN, J., CHANG, M. W., LEE, K., AND TOUTANOVA, K. BERT: Pre-training of deep bidirectional transformers for language understanding. NAACL HILT 2019 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies Proceedings of the Conference (oct 2019), 4171-4186.
[6] DEVLIN, J., CHANG, M. W., LEE, K., AND TOUTANOVA, K. BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding. https://github. com/ roggle-research/bere 2019.
[7] DEVLIN, J., CHANG, M. W., LEE. K. AND TOUTANOVA, K. Pre-training data cre- ation script for BERT. https::/githi: com/ poeatt_pretraininggco www.dat.....a.... py#L243, 2019.
[8] GUILLAN, G., DIAZ-CAMINO, C., LOYOLA-TORRES C., APARICIO-FABRE, R., HERNÁNDEZ-LóPEZ, A., DiAZ-SÁNCHEZ, M., AND SANCHEZ, F. Detailed analysis of

---

putative genes encoding small proteins in legume genomes. Frontiers in Plant Science 4 (2013), 208.
[9] HANSEN, H. B., DAMGAARD, P. B., MARGARYAN, A., STENDERUP, J., LYNNERUP, N., WILLERSLEV, E., AND ALLENTOFT, M. E. Comparing ancient dna preservation in petrous bone and tooth cementum. PLOS ONE 12, 1 (01 2017), 1-18.
[10] JIA, Z., TILLMAN, B., MAGGIONI, M., AND SCARPAZZA. D. P. Dissecting the Grapheore IPU architecture via microhenchmarking. ArXiv abs/1912.03443 (2019).
[11] JOHNSSN, D. S. Near-optimal bin packing algorithms. PhD thesis, Massachusetts Institute of Technology. 1973.
[12] JOHNSON, D. S., AND GAREY, M. R. A 7160 theorem for bin packing. Journal of Complexity (oct 1985), 65-106.
[13] KORTE, B., AND VYGEN, J. Combinatorial Optimization, vol. 21 of Algorithms and Combina- torics. Springer Berlin Heidelberg, Berlin, Heidelberg, 2012.
[14] LAN, Z., CIIE,, M., GOODMAN, S., GIMPEL, K., SUARMA,, P., AND SORICUT, R. ALBERT: A lite BERT for supervid learning of language representations. CoRR abs/1909.11942 (2019).
[15] MATTSON, P., REDDI, V. J., CHENG, C., COLEMAN, C., DIAMOS, G., KANTER, D., MICIKEVICIUS, P., PATTERSON, D., SCHMUELLING, G., TANG, H., WEI, G., AND WU, C. MLPerf: An Industry Standard Benchmark Suite for Machine Learning Performance. IEEE Micro 40, 2 (2020), 8-16.
[16] MLCOMMONS. v0.7 Results. https://mlccomonn wxgg/en/tranning nore-ooomaallll - 07/ 2020. Result not verified by MLPerf. Throughpuu/speccup is the primary metric of MLPerf. MLPerf name and logo are trademarks. See www. www.m..p.rf...m org for more information.
[17] NVIDIA. Reference numbers for BERT un-padding results.
https://github.cm com/
ml Doommons/brainingg.n ngc20. 06 wyytorcchbberrreeultt0 txt, 2020. Throughput/speedup is not the primary metric of MLPerf. MLPerf name and logo are trademarks. See www www.mlperf.cm . org for more information.
v0.
dgxat00
[18] NVIDIA. Faster Transformer. htttp://gittub. http:://gghhaao.oooo///////aaaap http:///////.bbbbeeeeeaaaaainaa. Lree///atter/PPttt///ssssoooor
2021.
[19] RAJPURKAR, P., ZHANG, J., LOPYREV, K., AND LIANG, P. SQuAD: 100,000+ questions for machine comprehension text. In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing (Austin, Texas, Nov. 2016), Association for Computational Linguistics, pp. 2383-2392.
[20] TURC, I., CHANG, M.-W., LEF, K., AND TOUTANOVA, K. Well-read students learn better: On the importance of pre-training compact models. arXiv preprint hwtp::9980..22550 (2019).
[21] VASWANI, A., SHAZEER, N., PARMAR, N., USZKOREIT, J., JONES, L., GOMEZ, A. N., KAISER, U., AND POLOSUKHIN, Attention is all you need. In Proceedings of the 31st International Conference on Neural Information Processing Systems (Red Hook, NY, USA, 2017), NIPS' 17, Curran Associates Inc., p. 6000-6010.
[22] WANG, A., SINGH, A., MICHAEL, J., HILL, F., LEVY, O., AND BOWMAN, S. GLUE: A multi-task benchmark and analysis platform for natural language understanding. In Proceedings of the 2018 EMNLP Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP (Brussels, Belgium, Nov. 2018), Association for Computational Linguistics, pp. 353-355.
[23] WARSTADT, A., SINGH, A., AND BOWMAN, R. Neural network acceptability judgments. arXiv preprint 1805: /247/ (2018).
[24] WU, B., XU, C., DAI, X., WAN, A., ZHANG, P., YAN, Z., TOMIZUKA, M., GONZALEZ, J., KEUTZER, K., AND VAJDA, Visual transformers: TTokenbbase image representation and processing for computer vision, 2020.
10

---

[25] YOU, Y., J., REDDI, S., HSEU, J., KUMAR, S., BHOIANAPALLI, S., SONG, X., DEMMEL, J., KEUTZER, K., AND HSIEH, C.-J. Large Batch Optimization for Deep Learning: Training BERT in 76 minutes, arXiv (apr 2019).
[26] YUE, M., AND ZIIANG, L. A simple proof of the inequality MFFD(L) < 71/600PT(L) +
1, for the MFFD bin-packing algorithm. Acta Mathematicae Applicatae Sinica 11, 3 (jul 1995), 318-330.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] Our paper has three main claims. First, in Figure right] we show the distribution of the Wikipedia and the excessive padding that it requires. Second, in Section 4.1 we show that we can efficiently pack the data which can be casily reproduced with the shared data and code [. Third, in Figure riight) we clearly show the 2x performance gain from packing and the related hyperparameter adjustment scheme.
(b) Did you describe the limitations of your work? [Yes] We see three potential limitations that we discuss the paper. First, as stated in the broader impact section, our approach is clearly dependent on the sequence length distribution of the dataset. However, looked into several other datasets beyond Wikipedia and observed even higher potential for acceleration. Second, explain
focus the IPU hardware with static precompiled kernel in Section 4.1 Our theoretical analysis in Section 4.3 indicates that approach benefits also other hardware. Third, changes to the network with modified attention mask and loss calculation come with some overhead. This is addressed in Table 0 [overhead column] in Section 4.1
(c) Did you discuss any potential negative societal impacts your work? [Yes] We address this point in the "Broader Impact" Section, third paragraph.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] Detailed algorithm explanations. clarifications of assumptions, and proofs are provided in the supplemental material [I]
(b) Did you include complete proofs of all theoretical results? [Yes] Section D.5, E, F in the supplemental material [I] provide the necessary derivations on theoretical results.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed reproduce the main exper- imental results (either in the supplemental material or as a URL)? [N/A] To ensure results are easily reproducible, we follow the MLPerf 0.7 benchmark rules and im- plementation. Additionally the main packing code is provided in the supplemental material, along with histograms of the datasets, which can be used to confirm the efficiency of the packing algorithms. We are solely relying on open source datasets. The full code related to the changes to BERT will be provided with a future software release, currently anticipated in July. Simplified reference code is provided directly in the paper.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] We follow the MLPerf 0.7 benchmark rules. We document the parameters that we changed and why we change them.
(c) Did you report error bars (c.g., with respect to the random seed after running experi- ments multiple times)? [N/A] The packing algorithms are deterministic and have no error. Other experiments are only once to compare convergence curves.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] We used 16 Graphcore IPUs for acceleration internal cluster.

---

4. If you are using existing assets (e.g., code, data, models) or curating/releasngg new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] Appropriate references to the BERT authors, all datasets, and the code snippet from the HugginFace inc. appropriately referenced with citations and links.
(b) Did you mention the license of the assets? [Yes] For the only taken code snippet, the license is part of the file [Listing 6 in the appendix].
(c) Did you include any new assets either the supplemental material or as URL? [Yes] New materials like packing code and histograms will be provided under an MIT license and are already listed and linked at the end of the supplemental material.
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A] We did not curate other people" data. We only provide very high level aggregate of the used data.
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A] We did not curate other people's 's data.
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A] Our experiments did not include crowdsourcing or human subjects. (b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A] Our experiments did not include crowdsourcing or human subjects.
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A] Our experiments did not include crowd- sourcing or human subjects.
12


Reviews:
[{"review_id": "eVl7RVhH-un", "reviewer": "Reviewer_QSu8", "summary": "This paper proposed two algorithms of packing (batching) variable-length sequences in training deep NLP models, SPFHP and NNLSHP. Experiment shows that these algorithms can accelerate BERT training by 2x compared with naive padding strategies and that they are also more scalable than un-padding strategies.", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Padding and packing (batching) is an important detail in large-scale NLP model training, but it has long been ignored by many NLP researchers and practitioners. The topic of this paper is both innovative and highly practical. Two packing algorithms proposed by the authors are also very close to the optimal, so the author almost \"solves\" this problem entirely. The proposed algorithms only add little overhead to the whole training process, and they are also more scalable and flexible than un-padding methods. The paper also discussed how to tune hyperparameters given the new packing strategy to achieve good performance.\n\nStill, I think there are still many problems in this paper. There are two major issues and two minor issues.\n\nSurprisingly, **packing is not a problem in masked language model (BERT) pre-training**. The RoBERTa paper (https://arxiv.org/pdf/1907.11692v1.pdf) has talked about this problem in detail. Table 2 of the RoBERTa paper shows that the sentence-pair scheme used by the original BERT codebase is worse than \"Full-Sentences\" or \"Doc-Sentences\", where multiple contiguous sentences are packed into a single sequence, such that the total sequence length is at most 512 tokens. **Language pre-training never requires each sequence to be a single sentence**; instead, it can be a concatenation of an arbitrary number of contiguous sentences. Therefore, the discussions in Section 3.2 (attention masking) and Section 3.3 (calculating per-sequence loss) seem useless, since cross-contamination between contiguous sentences is not harmful but even beneficial (as is shown in the RoBERTa paper). Although the proposed strategies are perhaps useless in language pre-training, **they can still be useful in other NLP tasks**, where the training dataset is a noncontiguous set of variable-length sentences. These tasks are machine translation, sentence classification, QA tasks, and so forth.\n\nHowever, in some of these tasks, **practitioners are already using packing strategies better than naive batching**. For example, the fairseq codebase (https://github.com/pytorch/fairseq/blob/f2146bdc7abf293186de9449bfa2272775e39e1d/fairseq/tasks/fairseq_task.py#L208) for machine translation uses following packing strategy:\n\n1. Sort sentences in the training dataset w.r.t. their lengths.\n2. Iterate over sentences in the sorted dataset and try to add sentences greedily into the current batch.\n    - If the resulting batch has more than n_tokens (a preset hyperparameter), finish the current batch and put this sentence into a new batch. Otherwise, add the sentence to the current batch.\n3. Pad all batches so that all sentences have the same length as the longest sentence in the batch. Since sentences in the same batch are contiguous sentences in the sorted dataset, they have similar lengths. Thus we will not end up adding too many padding tokens.\n4. This batching strategy also prevents cross-contamination automatically (since different sentences are not even in the same sequence), and it is even easier to calculate the per-token loss.\n\nAlthough this strategy is probably never published, it is widely used in many NLP projects (https://github.com/pytorch/fairseq#pre-trained-models-and-examples), especially machine translation (https://github.com/pytorch/fairseq/blob/master/examples/translation/README.md). Unfortunately, **the author of this paper ignores this extremely commonly used baseline**. Instead, the author compares their algorithms with *naive padding*. However, except for small downstream NLP tasks, naive padding is almost only used by the vanilla BERT codebase and some projects using the Huggingface *transformers* codebase, probably for compatibility with Google's TPU instead of efficiency.\n\nWriting is one of the minor issues. The description of the algorithm and TensorFlow source codes are informative and clear. However, unlike other algorithm papers, this paper has no derivation of (sequential) time complexity, parallel time complexity, and space complexity of their algorithms.\n\nAnother minor issue is that the author fails to explain how they have chosen *the weight of 0.09 for all sequences of length 8* for NNLSHP. If these hyperparameters are manually tuned, it would be better to add a sensitivity analysis showing whether the efficiency depends on a specific choice of this hyperparameter.\n\nTo summarize, this paper chooses an interesting topic and tries to solve this problem instead of making incremental improvements. The proposed methods are efficient and scalable. However, the author tries to solve a non-existent problem in BERT pre-training, although they may still be helpful in other NLP tasks other than LM pre-training. Also, the author only compares the methods with the weakest baseline, ignoring a very commonly used strong baseline. Therefore, I think this paper needs to be reworked.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N/A", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "XlCe2Qo9WI", "reviewer": "Reviewer_b88q", "summary": "Authors found that at sequence length 512 padding tokens represent in excess of 50% of the Wikipedia dataset used for pretraining BERT (Bidirectional Encoder Representations from Transformers). Authors pre-train BERT-Large using the packed dataset,\ndemonstrating no loss of convergence and the desired 2x speed-up.", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Authors showed that packing can be easily implemented without the need for any custom kernels while still providing a 2x speed-up. Additionally, we showed that any additional speed-ups resulting from dynamic un-padding approaches diminish for even moderate batch sizes or when additional accelerators are added. In contrast, packing is load-balanced and maintains the 2x throughput when\nscaling to large numbers of accelerators.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes authors addressed the limitations and potential negative societal impact of their work. Failures in NLP can have a big impact on society; many technologies, such as Alexa, Siri, and Google Home, rely on them. Whilst any errors arising from our approach can be avoided, one potential source of error comes from the implementation. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3 hrs"}, "extra_text": {}}, {"review_id": "RkCi_vPtI-2", "reviewer": "Reviewer_Sn5a", "summary": "This paper proposes a simple and effective approach to accelerate the standard BERT pretraining by packing multiple sentences to a single training sample with fixed length, in order to reduce padding tokens and fully utilize the computation. The packing algorithms itself are very efficient and the overhead introduced in training (attention mask and loss calculation) is limited (below 5%). Experiments show that with hyperparameter adjustment, the BERT pretrained with packed data can result in nearly 2x speed up. Compared to the unpadding approach with custom computational kernels, the packing approach is inherently load-balanced and thus scale better to multiple distributed accelerators. Overall, I believe this is a quite general approach that can be applied to large-scale training with data having variable lengths.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper with its supplementary document is general well designed with solid experiments and analysis. To me, the idea of packing data with different lengths is not new, has perhaps arguably been tried by researchers or engineers in their working on accelerating BERT training, but not published. Even in the original code of BERT, the preprocessing step considers concatenating multiple segments into one a long sequence, although a significant portion of padding tokens are still introduced.\n\nThe paper can be further improved in the following aspects:\n* Section 3.1 (packing algorithms) is hard to understand, especially to the readers with little background of packing algorithm. It will be better to have a formal definition of the problem, rather only explaining in words.\n* Section 3.3 (calculating per-sequence loss) has the similar problem. It is unclear to me how the losses are computed and aggregated. It would be better to have some formula and figure to present the process, rather than the code snippet.\n* In the packed data, how are the positional encodings configured? The positions of multiple sentence in one sample may have influence to the model behavior.\n* The proposed method are only evaluated in terms of the pretraining loss, while in practice it may be more important to evaluated the performance of the model (packed BERT) finetuned on downstream tasks. I am wondering whether there will be differences with original BERT on certain tasks.\n* “Empirically, a degradation of masked-language modelling accuracy on shorter sequences is indeed observed when not modifying the loss to account for packing”, what is exactly the drop of accuracy in the experiment?\n* “packing could potentially eliminate the need for two phase pre-training of BERT.” It will be better to valid this argument, since the two stages pretraining could have the effective of curriculum learning which can speed the coveragence. \n\nOverall, I think the paper provide a simple and effective method to accelerate BERT training, although the idea could be employed by other practitioners. Some part of the paper is not easy to follow and could be improved with better formulation or graphs. Experiments are generally solid, but lack of experiments on the downstream tasks and analysis on the positional embedding.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes, the author has addressed this issue in the paper. I think this work have positive impact since it can save the carbon footprint in training the large-scale models.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": ["I don’t know"], "time_spent_reviewing": "6"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Packing is an extremely underrated technique for drastically improving NLP training times. In my experience (on datasets other than Wikipedia), packing typically speeds up convergence times by 10x. Therefore this paper adds visibility and acts as a user-guide to a technique that has largely been under-discussed or taken for granted in the sequence modeling community, perhaps because it is often treated as *just* an engineering trick. I thoroughly enjoyed reading the paper and the rigor it provides to this useful technique.

This paper provides two novel and well-optimized algorithms for packing that deserve merit. That said, QSu8 points out correctly that packing has been done in common frameworks for a while even if there has been no publication on it. Thus many of the ideas in this paper are not originated from this paper. For clarity, the paper should make these distinctions. These ideas include
1. The greedy packing algorithm outlined in QSu8's initial review and implemented in frameworks such as fairseq and lingvo
2. The handling of positional embeddings as discussed in the response to Sn5a
3. The masking of attention matrices to eliminate cross-contamination

I have carefully read the discussions and will summarize my remaining concerns here by way of (hopefully) constructive feedback. Basically I agree with Sn5a and QSu8 that more experimental comparisons are needed.
1. Ablation study on attention masking. I.e. what if you didn't have the attention mask and allowed for cross-contamination? There is a plausible reason for this to still work since the 
 token demarcates the different segments. It would be interesting to know how much quality is actually hindered.
2. Direct comparison with RoBERTa as suggested by QSu8.
3. Sorted batch padding. I concur with QSu8 that overfitting to the sequence lengths is not an issue in practice given the large datasets. I disagree with the move to disregard doing the comparison based on the idea that variable batch sizes are hard to implement  though. This technique is widely used in the lingvo sequence library (implemented here https://github.com/tensorflow/lingvo/blob/22fa0a004b568477b8814195c199cce2717f1f5b/lingvo/core/datasource.py#L608-L617, and an LM that defines the bucket sizes here https://github.com/tensorflow/lingvo/blob/master/lingvo/tasks/lm/params/one_billion_wds.py#L53-L54). For recurrent architectures, the variable batch size can significantly reduce the amount of padding.
4. Finally, while not required, I think experiments with packing on downstream tasks would strengthen the paper even more since that's where the speedup would be greatest  (>>2x) as pointed out by Sn5a.

As it stands, given the high standards of NeurIPS, I hesitate to give an accept until the additional comparisons above are conducted and incorporated into the paper. I am very optimistic about the direction of this paper and encourage authors to revise and resubmit to the next conference.

Decision: Reject