Efficient Packing: Towards 2x NLP Speed-Up without Loss of Accuracy for BERT
Authors: Matej Kosec
Sheng Fu
Mario Michael Krell
Venue: ICLR 2022 Submitted (2022)
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 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 a maximum of 3 sequences in one sample. Using the dataset with multiple sequences per sample requires adjusting the model and the hyperparameters. We demonstrate that 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.

Under review as a conference paper at ICLR 2022
EFFICIENT PACKING: TOWARDS 2x NLP SPEED-UP WITHOUT Loss OF ACCURACY FOR BERT
Anonymous authors Paper under double-blind review
ABSTRACT
We find that sequence length 512 padding tokens represent in excess of 50% of the Wikipedia dataset used for pretraining BERT (Bidirectional Encoder Repre- sentations 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 packing algorithms. Both algorithms rely 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 fast and have linear complexity in dataset size. The shortest-pack- algorithm determines the packing order for the Wikipedia dataset of over 16M sequences in 0.03 seconds. The non-negative least-squares histogram-ppckingg (NNLSHP) algorithm converges in 28.4 seconds but produces solutions which are more depth efficient, managing to get near optimal packing by combining a maxi- mum of sequences in one sample. Using the dataset with multiple sequences per sample requires adjusting the model and the hyperparameters to keep the predic- tive quality of the model. We demonstrate that 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.
sattoraa-ppckinnn (SPFHP)
INTRODUCTION
Since its introduction in 2019, BERT (Devlin ct al. 2019a) has been the backbone driving the most exciting advances Natural Language Processing (NLP). Pre-training BERT from scratch requires substantial computational resources which may be out of reach for researchers and industry pro- fessionals. To some extent this has been addressed by the public release of pre-trained models of different sizes and depths (Turc et al. 2019). The introduction of ALBERT (Lan et al. 2019) and Switch transformers (Fedus et al. (021) further improved the accessibility of larger models. How- the dependence pre-trained models limits the ability of researchers to explore new backbone architectures. Furthermore, limits the extent to which practitioners in industry can leverage inter- nal datasets and adapt the model to their particular needs. Hence, any approach that speeds up the pre-training process is desirable from an economical as well as environmental perspective.
In this paper, we present efficient methods to enable researchers to accelerate the pre-training of BERT by as much as 2x without loss of accuracy. The de-facto pre-training dataset Wikipedia, well as many other NLP datasets, have 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. Thus. by avoiding processing the padding tokens one can get 2x speed-up. Overall, the lengths range between 5 tokens up to 512 (see Figure D Samples of length 512 represent only 23.5% of the dataset, a surprising result given that the pre-processing in BERT attempts to "pack" together sentences so as to fill the sequence length as completely as possible (Devlin et al., 2019c). While processing the padding tokens wastes compute, it is still the most standard approach for leveraging modern massively-parall compute especially These are most efficient when applying the same operation to each sequence a batch. By padding all sequences to the same maximum sequence length, they can casily be batched. We note that this naive batching is the most widely used and provided in the vanilla BERT implementation as well as the Hugging Face framework (Wolf et al. 2020) and thus considered as our baseline for comparison.
GPUs.

---

Under review as a conference paper at ICLR 2022
max. sequence length:
max, sequence length: 384
max. sequence length 512
theoretical max. speed-up: 1.210
theoretical max. speed-up: 1.742
theoretical max. upeed-up: 2.001
0.005
0.005
0.005
59.3%
30.6%
23.5%
probablity dersity
0.004
0.004
0.003
0.003
0.002
0.002
0.002
0.001
0.001
0.001
0.000
25
50
75
100
125
100
200
300
400
0
200
200
300
400
500
sequence lengtt
sequence length
Sequence length
Figure I: Wikipedia BERT pre-training dataset sequence length histograms (token count excluding padding) for different maximum sequence lengths. Based on the Wikipedia article dump from Oc- tober 1st 2020. The theoretical speed-up relates to not using any padding tokens and not having any overhead from processing the different lengths.
The most obvious way to reduce the extent of padding in the dataset is to group samples by size be- fore batching (SORT), i.e., process the shorter samples together and longer samples together. BERT 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 train- ing in this way, the wasted compute due to padding is approximately 20% (see Figure Tp. Other examples of this "sorted batching" approach can be found in Faster Transformer (NVIDIA 202I), lingvo (Shen et al.) 2019) fairseq (Ott et al. 2019), and RoBERTa (Liu et al. (019), which group samples of similar size together in one batch and fill up with padding only to the maximum length in this batch. This approach can be highly efficient in cases where the dataset length is multiple orders of magnitude larger than the batch size and the number of different sequence lengths. Despite its high computational efficiency, this approach has multiple drawbacks. We outline these below and propose an alternative which maintains the high efficiency, while also circumventing the downsides. Firstly, sorting the data can reduce the overall convergence speed when the batch size is large be- cause it violates the i.i.d. assumption on the data distribution (Bottou et al. 2018 Meng et al. 2019). Secondly, processing batches with shorter sequence lengths under-utilizes the compute compared to running the same batch size with a longer sequence length. For GPUs, a common heuristic to miti- gate this effect is adjust the batch size keep the number processed tokens near constant (Ou) iet al.) [019 Liu et al. 2019). In general however, the relationship between the sequence length and the optimum batch size is more complex and maximizing compute utilization can require the model to be sharded differently across multiple accelerators. Avoiding this, often manual process, important for ease of use and the portability of methods across different hardware architectures. Thirdly, modern NLP applications are optimized and compiled for fixed tensor sizes using tools such as XLA (XLA) 202T Redus et al., 202T), which provides a Ra 7ar acceleration for BERT in MLPerfTM (Mattson al. 2020) compared to the -on baseline (XLA 2021). Changing the sequence length or batch size requires re-optimization of the computational graph and recompila- tion of the program for the new tensor shapes. For complex models such as BERT, optimization and recompilation take a non-negligible amount of time. Even if one pre-compiled and cached all combinations of batch size and sequence length, the kernels would still need to be re-uploaded to the device every time the shapes change. Depending on how frequently the tensor shapes change, the overhead from switching kernels adds up. To avoid these issues, it preferable (and common) to work with fixed tensor shapes for the entire duration of the training run.
More advanced approaches for reducing the padding overhead rely on custom computational kernels. Loosely these are referred to as "un "un-padding" approaches. In Effective Transformer (ByteDance Inc., 202T), the input batch is provided as a padded matrix but padding values are dynamically removed and restored during different calculation stages. While un- un-padding implementations are highly sophisticated and are able to completely circumvent the processing of padding tokens, they introduce significant overhead due to the multiple GPU kernel launches (i.e., one kernel per quence rather than one kernel per batch). Additionally the time to process each batch will fluctuate depending 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 inten-
2

---

Under review as a conference paper at ICLR 2022
sive batch to finish processing. As such, un-padding approaches not appropriate for deployment on large clusters. The "packing" based approach introduced in this paper offers sigmificant advan- tages over 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 is 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.
While we demonstrate the effectiveness of packing specifically on the Wikipedia dataset, pack- ing SQuAD (Rajpurkar et al. 2016) or GLUE datasets (Warstadt et al., 2018: Wang et al. (2018) for BERT also leads significant speed-ups (some excess of 9x) (Sections H and J]. 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 (Devlin et al., 2019c). The use of bi-directional self-attention in BERT implies that the input sequences should contain complete sentences. If sentence 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 to the same degree. For such models, if a 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 models based on causal at- tention. For instance, GPT-3 (Brown al., 2020) is trained with a maximum sequence length of 2048 where a single sequence may contain multiple segments of sentences separated by a special end of segment token. The last segment in each sequence is simply cut to meet the sequence length requirement making the packing problem trivial and avoiding any padding. In the interest of com- putational efficiency GPT-3 does not mask the attention between different segments in a sequence. In contrast, the packing approach presented in this paper introduces mask in the attention layer (see Section (.2.2) to prevent cross- contamiattiinnnnn between examples in pack. Note, we mask the interaction between different sequences and not between different sentences or segments in the same sequence. This ensures that the characteristics of the original dataset and model are matched as closely as possible. RoBERTa and many other models in production like T5 (Raffel et al.) 2019) use a similar packing approach as GPT-3, combining full sentences/sequences with GREEDY pack- ing (first come first concatenate) and also separation tokens additional padding. The RoBERTa ablation study shows that mixing of sentences from different documents reduces accuracy, but is used nonetheless for load balancing reasons which indicates that sorted batching is not sufficient.
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 and efficient packing algorithms which efficiently pack datasets with millions of sequences in a matter of seconds (or less) Section 3.1 We empirically show that the proposed packing algorithms produce a nearly-optimal packing scheme In Section (.2) and Section 3.3 we explain how the BERT model can be adjusted to show the same convergence behavior on packed and unpacked sequences. In Section 4.2 we demonstrate that the convergence of the BERT large model on the packed dataset is equivalent to that on the un- un-packed dataset with 2x throughput increase on the Wikipedia sequence length 512 pre-training dataset.
2 WIKIPEDIA BERT PRE-TRAINING DATASET
BERT is pre-trained using masked-language modelling and next-sentence prediction on a large cor- pus of Wikipedia articles. Each sequence is composed of one <CLS> token followed by the first "segment" of sentences, followed by a <SEP>> token, and then finally the second "segment" of sen- tences. Because these "segments" are created in sentence-level increments there is no token-level control of sequence length. Furthermore 10% (default value, (Devlin et al. (019b)) of sequences are intentionally cut short. This leads to significant levels of padding, especially for longer maximum sequence lengths (see [i. 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- pre-training BERT such histograms have, to the best of our knowl- edge, not been published previously. This has perhaps lead to the underestimation of the speed-up opportunity available. To put things into perspective, the sequence length 512 dataset contains 8.33 billion tokens, of which 4.17 billion padding tokens.
3

---

Under review as a conference paper at ICLR 2022
3 METHODS
Our approach consists of three distinct components. Firstly, we pack the n data samples efficiently during pre-processing to make full use of the maximum sequence length, Sm (Sections 3.1.1 3.1.2 and [ Secondly, we introduce a series of model changes in Section 3.2 that preserve the equiva- Ience with the original BERT implementation. The changes include a self-attention mask to prevent the model from attending between different sequences in the same pack (Section B.2.2), and an ad- justment of the the positional embeddings (Section 3.2.1) to handle packs of sequences. Other com- ponents of the model, such as the feed-forward layer Vaswani et al., 2017). operate on per-token basis and do not require modification for pre-training. In Section we also demonstrate how to compute a per-sequence loss and accuracy for NSP and downstream fine-tuning tasks. Thirdly, we provide suggestions for hyperparameter adjustment (Section 3.3) that lead to analogous convergence behavior between the packed and un-packed BERT implementations.
3.1 PACKING ALGORITHMS
The problem of optimally concatenating multiple sequences of different length until a maximum combined length reached can be directly framed a bin-packing problem. Since an exact solution is strongly NP-complete (Korte & Vygen 2012), we propose two new heuristic algorithms that are tailored to the NLP setting. A detailed introduction to packing provided in Section E
3.1.1 SHORTEST-PACK-FIE
HISTOGRAM-PACKE (SPFHP)
Shortest-pack prcisst--ac--ffrrss first histogram- histogram-packing (SPFHP) works on the bins in the sequence length histogram (with bin size 1) rather than the individual samples. The histogram is traversed in sorted order from longest to shortest sequences. Then, to pack the data during the traversal, algorithm [Jhnnson 1973; Yue & Zhang 1995) such that the histogram bin being processed goes to the "pack" that has the most space remaining ""shortest-pack-fing first")". If the histogram bin does not fit completely, a new pack is created. We also limit the packing depth, in other words the maximum number of sequences that are allowed in a pack. Therefore, an existing pack is only extended if is not already at maximum packing depth. The detailed code for the algorithm is provided in Listing The time and space complexity of the algorithm are O(n + x and (s2)) (Section F.2
apply the worst-fit
3.1.2 NON-NEGATIVE LEAST SQUARES HISTOGRAM PACKING (NNLSHP)
The proposed NNLSHP algorithm is based on re-stating the packing problem as a (weighted) non- negative least squares problem (NNLS) (Bro & De Jong 1997) of the form WAr = wb where x 2 O. The vector b 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 a 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 as a column of the sparse matrix A. For example, a strategy consisting of the sequence length 128, 128, and 256 in represented a column vector that has the value 2 at the 128th row, the value at the 256th row, and zero at all other rows. The variable x describes the non-negative repetition count for each strategy. So 24 in the ith row of means that the strategy represented by the ith column of A should repeat 24 times. Moreover, in the un-weighted setting, Az states that 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 O times. We use the residual weight w to control the penalization of the Ax b residual on different sequence lengths (different rows of b). Heuristically, we set the weight of 0.09 for all sequences of length 8 or smaller because they are considered acceptable padding sequences while all other sequence lengths get weight 1. We discuss this heuristic choice of parameters in Section E.4.5 and E.5 The overall efficiency of the packing is not greatly influenced by the weighing (less than 1% extra speed-up).
After solving wAr = wh for x 2 0 using an off- the-shelf solver, we obtain a floating point solution, which means that the repetition counts are not necessarily integers. Since we cannot use non- natural number of strategies, we round the solution å to the nearest integer. The error introduced
We avoid the ambiguous terms "hin" and "sample/sqquence and use "pack" instead to refer to the multiple sequences concatenated during packing.
4

---

Under review as a conference paper at ICLR 2022
by this rounding is found to be negligible (a few hundred sequences in the worst case) compared to the size of the dataset (millions of sequences). The time complexity and space complexity of the algorithm are On + s and ((s Further details are provided in Section E.4
3.2 PACKEDBERT; MODEL CHANGES
This section describes how any vanilla BERT implementation should be modified for packed se- quence processing, such that the behavior of the model is the same as when processing unpacked sequences. Preserving the mathematical equivalence is necessary to ensure existing BERT pre- training and fine-tuning practices remain valid, as well as being required by benchmarks such as MLPerfIM (Mattson et al. 2020)
3.2. POSITIONAL EMBEDDINGS FOR PACKED SEQUENCES
The BERT model uses three types of embeddings: token, segment, and positional embeddings. The latter is canonically implemented as a bias add operation, rather than a full embedding look-up. This is possible because the positional indices the packed data format the position index needs to be reset with each new packed sequence. For instance, when packing indexes that need to be picked up are [0, 1, 0, 1, 2]. To achieve this, the bias add needs to be replaced by an embedding look-up extract the correct positional embedding for each token in the pack. This also requires keeping an extra input which specifies the position of each token in its sequence. This adjustment has only a minor impact on absolute accuracy/loss but is required to reach the target accuracy (Section 4.2 and Cp.
the same for every sequence. However, when using
sequences of length 2 and one of length 3, the positional embedding
3.2.2 ATTENTION MASKING FOR PACKED SEQUENCES
To maintain an implementation that is consistent with the un-packed version, tokens from different sequences within a pack should not able to attend to each other. This is typically achieved in other implementations by unpacking the sequences using custom attention kernels and then doing the at- tention per-sequence (ByteDance Inc., 2021). Instead, we propose directly masking the attention matrix with block-diagonal mask before the attention softmax. This is straightforward to imple- ment in modern frameworks (see Figure 2 Naturally, there is cost to both the mask construction and applying it to the attention matrix (see Table Section 4.1) However, it is required keep the accuracy (Section 4.2 and C).
np.array
acro_ona_mast if.equal (nask, mask.I) C, nask
t zor use with sottmax:
nazcnax_naak EC. tC. (xeeeeeeeeeooocee_nnaa c, -1000)
Figure 2: Attention mask code sample [left] and example zero-one mask [right].
3.2.3 CALCULATING PER-SEQUENCE LOSS AND ACCURACY
Canonical implementations of BERT compute the cross-entropy loss for the masked language model on per-token basis. However other NLP tasks, such as SQuAD, compute the loss and accuracy on per-sequence basis. This section discusses how to handle such tasks when training with packed sequences. Simply feeding packs of sequences to the same implementation of cross-entropy would result in per-pack weighted loss. In other words, the overall loss on the micro-batch would sum- up the losses on the individual packs, rather than individual sequences. As a result, the model would converge to different optimum than when running with the un-packed implementation. For instance, a pack of a single sequence would contribute to the loss with the same weight as a pack of three sequences.
To recover the per- per-sequence averaging behavior of the canonical un un-packed BERT implementation, effectively "unpack" the incoming logits and labels. Once the sequences have been unpacked, we can compute the loss on each sequence separately as usual and then add up the losses. How- ever, rather than looping through the sequences index, compute all indexes in parallel (see
5

---

Under review as a conference paper at ICLR 2022
Figure 3). This minimizes the latency overhead of un-packing the loss calculation. As example, we show how per-sequence loss can be implemented for the pre-training task. We use the "masked Im weight" (Devlin et al., 2019b) input tensor to represent which sequence given masked token belongs to (0, 1, and so on). This is consistent with the canonical BERT implementation where this input takes value of either I (belonging the sequence) O (helonging to padding). The full methodology is detailed in Listing S and can be applied to other classification or pre-training tasks.
Urpack to pap-ing depth S
Loss/ACC
Aggregane
Figure 3: Vectorized unpacking of the sequence loss. White rectangles correspond to padding.
3.3 HYPERPARAMETER ADJUSTMENT
In terms of convergence behavior, the primary consequence of packing an increase in the effective batch size (with respect to number of sequences and real tokens) with some variation over different iterations. When the loss is averaged per-sequence, if each pack on average contains two sequences, the batch size (per optimization step) is effectively doubled on average. Similarly, for per-token averaged losses depends on the effectiveness of the compression. Reducing the fraction of padding tokens in the dataset from 50% to 0% results in there being twice many tokens in the batch i.e. the dataset compressed by 2x factor. 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 might imply under-utilizing the memory/com- pute.
Instead, we propose an approximate heuristic for updating the decay parameters of the LAMB op- timizer (You al., 2019). For packed dataset with packing factor p, update the decay parameters as: 31 = B B2 = 3y- For 2, this corresponds to the exact parameters for calcu- lating momentum and velocity, when updating with the same gradient twice (Section A). A common approach is to scale the learning rate with the batch size. However, our experiments in Section 4.2 show that this reduces convergence speed.
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 use existing configurations.
4 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- non-padding tokens in the packed dataset), the speed-up achieved compared 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 NNLSHP, we focus on packing depth 3 because it packs the data sufficiently well.
For the speed-up analysis, we focus the intelligence processing unit (IPU) (Jia et al. 2019) (IPU- M2000, 16 accelerator chips). A GPU dynamically loads the code into the accelerator; in contrast, the IPU works with static pre-compiled engine that gets loaded onto the chip at the start of the run. While other approaches result in excessive padding or continuous changes of the code, our approach work with the same code for the whole dataset. So in this setting the IPU architecture would

---

Under review as a conference paper at ICLR 2022
especially benefit from 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 quite noisy,
precompiled kernel. Since time measurements many cycles it takes for processing a batch. That way, we can determine the overhead (in cycles) from processing the additional attention masking and for unpacking the loss. Combining overhead and packing factor, we get the speed-up estimate. No experiment repetitions are required since the algorithms and measurements are deterministic.
profile the kernel and how
The main results for the performance metric evaluation are displayed in [able 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 NNI.SH .HP at depth which required 28.4s for processing and ran out of memory for larger depth. 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 inter-changeably. The amount of time needed to process sample (a pack of sequences) is barely changed relative to the un-packed implementation. The packing factor or the improvement in efficiency effectively provide an accurate estimate of the speed-up.
Table 1: Key performance results of proposed packing algorithms (SPFHP and NNLSHP).
packing depth
packing
# packs
efficiency
packing
overhead
realized
algorithm
[M]
(%)
factor
(%)
speed-up
NONE
16.280
49.97
1.000
0.000
1.000
SORT
16.280
99.99
2.000
100
1.000
10
GREEDY
100.397
788.2
R 1..566
R,4.48
21.5
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
Packing depth describes the maximum number of packed sequences. NONE is the baseline BERT implementation, whereas SORT corresponds to sorted batching, and GREEDY concatenates quences as they arrive until they exceed 512 tokens. Setting no limit resulted in a maximum packing depth of 16. The number of packs describes the length of the packed dataset. Efficiency is the percentage of real tokens in the packed dataset. The packing factor describes the resulting po- tential speed-up compared to packing depth With overhead, denote the percentage decrease in throughput due to changes to the model to enable packing (such as the masking scheme intro- duced in Section 3.2.2). The realized speed-up 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 throughput and the overhead from masking and loss adjustment.
4.2 LEARNING CURVES AND HYPERPARAMETER ADJUSTMENT
For depth (classic BERT) and NNLSHP with depth we additionally evaluate on the MLPerfTM version 0.7 BERT pre-training benchmark (Mattson et al. 2020). Briefly, this involves training from standard checkpoint
masked-language model accuracy of 71.2% using 3 million sequences with a maximum length of 512 tokens (refer to MLCommons (2020) 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 are 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.3) and there is no mapping that will generate exact matching of results but only heuristics. In first comparison, use the same hyperparameters when comparing packed and unpacked training except for cutting the accumulation count by half. This way, make that the batch size is constant average.
7

---

Under review as a conference paper at ICLR 2022
In the second comparison, we evaluate our heuristics and how they compensate the difference in batch size. This setup is more desirable because it is beneficial to use the hardware to its full potential and cutting the batch size by half usually reduces throughput. In the third comparison, compare two optimized setups.
The learning curves are displayed in Figure 4 In the first setup, 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 near-identical match. The second setup shows bigger differences since changing the batch size and hyperparameterss changes the training dynamics. We observe slower convergence early on in training due to the increased batch size. This 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. How- ever, it 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 slow down in convergence than when running packed BERT with a batch size of 1500 and a packing factor of 2. n practice, our implementations exceeds the estimated 1.913 maximum speed-up. This estimate is based on the reduction in the computational work needed to process the dataset. However, packing the data also reduces the latency of the transferring the data the device. Figure 4 shows that the realized total speed-up from packing exceeds 2x. On Squad 1.1 after full packed pretraining, Fl score is reduced by 0.003% whereas the EM score is increased by 0.049% (Section D)
183
3.5
3.0
packed, 768*2. 0.81
classic, bs: 1500, beta: 0.81
clessic, bets: 0.01
packed, beta: 0.66, double ln
packed, 0.66
training loss
3.5
3.0
classic, 3000, beta: 0.66
classic, bs 1500, bete: 0.81
packed, ebs: 1500*2. beta: 0.86
packed, double In
2.5
Dultre
2.5
2.0
1.5
1.5
0.5
3.0
1.5
2.0
samples
1e6
samples
1e6
relative time
Figure 4: Comparison of learning curves for packed and unpacked processing, where all experiments converged the target accuracy within the same number of training samples(3 million). [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 speed-up from packing (in excess of desired 2x).
4.3 SCALING ANALYSIS: IMPACT OF THE NUMBER OF ACCELERATORS
A further advantage of packing over competing un un-padding approaches is the inherent load balanc- ing 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 com- puting 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. Be- cause of these additional savings, un-padding can exceed the theoretical upper bound for speed-up from packing (2.013 on Wikipedia). As a result of the dynamic nature of the approach, the process- ing time with un- un-padding 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 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 baad-imbalance between the devices (and inside the batch) leads to considerable decrease in the speed-up from un-padiing as the number of accelerators is increased (see Figure 5
In contrast, packing (our approach) is inherently Load-balanced The processing time each celerator 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 process
8

---

Under review as a conference paper at ICLR 2022
(all per-device batches are equally fast). To demonstrate the severity of the wrad-imbalance issue, consider the scaling of an un un-padding approach with a per-device batch size of 32 running on eight devices (NVIDIA) 2020). From there, we readily extrapolate the performance to both larger and smaller cluster sizes by fitting a Gumbel distribution to the observed processing times (Section B) On single device with batch size 32 un-padding outperforms packing and exceeds the theoretical upper-bound for packing, As the number of devices increases to two or more, the proposed pack- ing approach outperforms the dynamic un-padding approach. On cluster with 32 accelerators the speed-up from un un-padding drops to 50% and with 2048 devices the speed-up is only 30%. In con- trast, the speed-up due to packing is independent of the number of accelerators and stays at 1.913. Switching to smaller batch size would reduce the load-imbalance issue to some extent, but would also result under-utilization of the available memory and compute.
2,013
1.913
1.800
1.700
1.500
1.400
1.300
theoretical upper- hound
1.200
packdng lour approach) pddding
1.100
1.000
padding
32 number of accelerators
256
1024
2048
Figure 5: Comparison of the theoretical speed-up achievable as the number of accelerators in- creased.
CONCLUSION
We showed that packing can be easily implemented without the need for any custom kernels while still providing a 2x speed-up without a loss of accuracy. 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 scaling to large numbers of accelerators. Furthermore, the computational overhead introduced by the positional embedding, the attention mask, and potentially the packed per- sequence loss are small compared to the achieved acceleration. This overhead remains below 5% on the IPU for all tested packing depths. The efficient packing algorithms presented in this paper enable us to efficiently pack millions sequences in a matter seconds. Compared to both pre- prepprocessing time for the Wikipedia dataset and the training runtime, this overhead is negligible. Furthermore, we showed that performing packing as a pre- proceesessing step does not significantly impact the training convergence. Our proposed hyperparameter adjustment scheme additionally helps practitioners easily modify existing validated optimizer settings for use with packed BERT. Further exploration hyperparameter selection is left future work.
When performing packing as pre-processing step, the proposed NNLSHP and SPFHP methods achieve near optimal compression efficiency. In this offline setting, we are 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 histogram of the entire dataset cannot be built. Another interesting direction is the packing of images of different sizes help accel- erate computer-vision applications. This is especially relevant given the recent advances in the approaches the computer vision domain, for example the visual trans- former (Wu et al. 2020). Masking out the self-attention within transformers is easier to implement than avoiding cross-contann contamination convolutions applied to packed images. Future work should explore improving the performance of other models (RoBERTa, GPT-3, T5) by avoiding contamina- tion between contiiniiu segments from different documents. Even BERT itself might benefit from avoiding contamination between the concatenated segments.
use of transformer-base

---

Under review as a conference paper at ICLR 2022
REPRODUCIBILITY STATEMENT
All code for the packing algorithms is available in the appendix (Section O and is directly linked to our GitHub page to simplify the download and usage. We even provide code for different variants and the histograms of sequence length for different datasets that got tokenized for BERT training of fine-tuning.
To generate the learning curves, public submission MLPerfTM could be used and preparing further code releases other frameworks. To encourage the use of the adjustments of models for packed sequences, additionally provide detailed explanations and code snippets in TensorFlow.
Detailed mathematical formulas (Section B and ED, theorem proof (Section A}, and complexity calculations (Section F) are provided in the appendix to support our claims in this paper in full detail.
REFERENCES
Léon Bottou, Frank E. Curtis, and Jorge Nocedal. Optimization Methods for Large-Scale Machine Learning. SIAM Review, 60(2):223-311, jan 2018. ISSN 0036- 1445. doi: 10. 10.1137/16M1000177.
Rasmus Bro and Sijmen De Jong. A fast non-negatiitty least squares algorithm. Journal of Chemometrics, ((55):333401, sep 1997. ISSN 0886-9383. doi: 10. 10.1002((SIC)) 1099-
Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhari- wal, Arvind Neelakantan, Pranav Shyam. Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, Christopher Hesse, Mark Chen, Eric Sigler, Mateusz Litwin, Scott Gray, Benjamin Chess, Jack Clark, Christopher Berner, Sam McCandlish, Alec Radford, Ilya Sutskever, and Dario Amodei. Language Models are Few-Shot Learners. In Advances in Neural Information Processing Systems pre-proceedings (NeurIPS 2020), may 2020. URL abs/://b//20 http://///////....1....00..
http:// http::://axxxv..or/abb/////////
ByteDance Inc. Effective Transformer. httpgs///gghhub...cob/eeeeeeeee transformer 2021.
Jacob Devlin, Ming Wei Chang. Kenton Lee, and Kristina Toutanova. BERT: Pre-training of deep bidirectional transformers for language understanding. NAACL HLT 2019 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies Proceedings of the Conference, 1:4171-418 oct 2019a. URL.ttp::/aaxxi
org/ org/abs/ /1100/1110000 04805
Jacob Devlin, Ming Wei Chang, Kenton Lee, and Kristina Toutanova. BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding. https:://githb. com/
resealeeeeeeeecchbeeeeeeee 2019b.
Jacob Devlin, Ming Wei Chang, Kenton Lee, and Kristina Toutanova. Pre-training data creation script for BERT. htttp:://githut com goog eewoogll-resseee rereeereeeaaeee wtt.r//eeecrr//ttt///oo////atate 2019c.
create_ seraatee_pretraannnndeeeaa.eee
William Fedus, Barret Zoph, and Noam Shazeer. Switch Transformers: Scaling to Trillion Parameter Models with Simple and Efficient Sparsity. arXiv, jan 2021. URL
2101. 03961
Zhe Jia, Blake Tillman, Marco Maggioni, and Daniele Paolo Scarpazza. Dissecting the Graphcore IPU architecture via microbenchmarking. ArXiv, abs/1912.03413, 2019.
David S Johnson. Near-optimal bin packing algorithms. PhD thesis, Massachusetts Institute of Technology, 1973.
10

---

Under review as a conference paper at ICLR 2022
David S. Johnson and Michael R. Garey. A 7160 theorem for bin packing. Journal of Complexity,
(1):66--16,, oct 1985. ISSN 0885064X. doi: 10. 10010000800000000000000000000000
URL https:
Bernhard Korte and Jens Vygen. Combinatorial Optimization, volume 21 of Algorithms and Com- binatorics. Springer Berlin Heidelberg, Berlin. Heidelberg. 2012. ISBN 978-3-642-244877 2. doi: http://www......ee..........eaaa
(-4-9988-------444- 978-3-642-2448--
URL springerrr com com/10.1007
Zhenzhong Lan, Mingda Chen, Sebastian Goodman, Kevin Gimpel, Piyush Sharma, and Radu Sori- cut. ALBERT: A lite BERT for self-supervised learning of language representations. CoRR, hbss/909..11922 2019. URL http: wtwpaiiwii.iioiioiooooooo org/ abs 1909. 11942
Yinhan Liu, Myle Out, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. RoBERTa: A Robustly Optimized BERT Pre- training Approach. arXiv, jul 2019. URL http:://txxiiii wttp:///////b/....a/.../
Mattson, J. Reddi, C. Cheng, C. Coleman, G. Diamos, D. Kanter, P. Micikevicius, Patterson, G. Schmuelling, H. Tang, G. Wei, and C. Wu. MLPerf: An Industry Standard Benchmark Suite for Machine Learning Performance. IEEE Micro, 40(2):8-16, 2020. doi: 10.1109/MM.202 2974843.
Qi Meng, Wei Chen, Yue Wang, Zhi Ming Ma, and Tie Yan Liu. Convergence analysis of dis- tributed stochastic gradient descent with shuffling. Neurocomputing, 337:46-57, apr 2019. ISSN 18728286. doi: (0016//.eeccmm221000..01.
MLCommons. v0.7 Results. https: comppoosss..omoosssooo http////ooooooooooeee//aaaaaaaaa 2020. Result not verified by MLPerf. Thrroughpu//speccup is not the primary metric of MLPerf. MLPerf name and logo are trademarks. See
org for more information.
NVIDIA. Reference numbers for BERT un un-padding results.
https://githubb com/
m1 www.ooonstttaaiinngggggooooomoee hwwphnnggrssussseeeeeeee wttp://wwww..///.ttt/oe//////e/ http://aatttt///iii///eeuesssa
dgxa100 1oxxa100_nge222 2ee0__nn2__._0 wtt_pyttrccbbeer//////eee.eeeeee wtwperrtrresutt_tee txt 2020. Throughput/speedupp is not
the primary metric of MLPerf. MLPerf name and logo are trademarks. See www ml www.mf.foooooom org
for more information.
NVIDIA.
Faster
Transformer.
https://github cOm/NVIDIA/ 2021.
Myle Ott, Sergey Edunov, Alexci Baevski, Angela Fan, Sam Gross, Nathan Ng, David Grangier, and Michael Auli. fairseq: A fast, extensible toolkit for sequence modeling. In Proceedings of NAACL-HLT 2019: Demonstrations, 2019.
Vassil Panayotov, Guoguo Chen, Daniel Povey, and Sanjeev Khudanpur. Librispeech: an asr corpus based on public domain audio books. In Acoustics, Speech and Signal Processing (ICASSP), 2015 IEEE International Conference on, pp. 5206-5210. IEEE, 2015.
Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J. Liu. Exploring the Limits of Transfer Learning with Unified Text- to-Text Transformer. Journal of Machine Learning Research, 21, oct 2019. URL http://
arxiv. absgg//bs/1990 111.////9..118811
Pranav Rajpurkar, Jian Zhang, Konstantin Lopyrev, and Percy Liang. SQuAD: 100,000+ questions for machine comprehension of text. In Proceedings of the 2016 Conference Empirical Methods in Natural Language Processing, pp. 2383-2392, Austin, Texas, November 2016. Association for Computational Linguistics. doi: 10.18653/vI/I6-11 1264. URL https::///// wwwww//www..../ aclweb.
hoc//anthclooyyDD1-6-
Jonathan Shen, Patrick Nguyen, Yonghui Wu, Zhifeng Chen, et al. Lingvo: modular and scalable framework for pouuueccc-to-equenee modeling, 2019.
Julia Ture, Ming-We Wei Chang, Kenton Lee, and Kristina Toutanova. Well-read students learn better:
On the importance of pre-training compact models. arXiv preprint arXiv: 989668228..., 2019.
11

---

Under review as a conference paper at ICLR 2022
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, un- definedukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS' 17, pp. 6000-6010, Red Hook, NY, USA, 2017. Curran Associates Inc. ISBN 178151086096..
Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel Bowman. GLUE: A multi-task benchmark and analysis platform for natural language understanding. In Proceed- ings of the 2018 EMNLP Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP, pp. 353-355, Brussels, Belgium, November 2018. Association for Computational Lin- guistics. doi: 10. 10.18653/11/118-5446
URL htt.:t:t/////. /wwwww/www..//.... ac web. oeb.oorg/atthhloogg/
WI8- 5446
Alex Warstadt, Amanpreet Singh, and Samuel R Bowman. Neural network acceptability judgments. arXiv preprint arXiv: 1805. 0005./247.. /247/, 2018.
Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowiez, Joe Davison, Sam Shleifer, Patrick von Platen, Clara Ma, Yacine Jernite, Julien Plu, Canwen Xu, Teven Le Scao, Sylvain Gug- ger, Mariama Drame, Quentin Lhoest, and Alexander M. Rush. Transformers: State-of-the-art natural language processing. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations, pp. 38 45, Online, October 2020. As- sociation for Computational Linguistics. URL wttph:tp/////ttt //w.p::::wwww... acwweb. wwtp:/ww......aaoooo........../.
1020.emnlie demos. 6
Bichen Wu, Chenfeng Xu, Xiaoliang Dai, Alvin Wan, Peizhao Zhang. Zhicheng Yan, Masayoshi Tomizuka, Joseph Gonzalez, Kurt Keutzer, and Peter Vajda. Visual transformers: Token-based image representation and processing for computer vision, 2020.
Tensorflow XLA. XLA: Optimizing Compiler for Machine Learning.
https:
tensorflow org/xla 2021.
Yang You, Jing Li, Sashank Reddi, Jonathan Hseu, Sanjiv Kumar, Srinadh Bhojanapalli, Xiaodan Song, James Demmel. Kurt Keutzer, and Cho-Jui Hsich. Large Batch Optimization for Deep Learning: Training BERT in 76 minutes. arXiv, apr 2019. URL
erg/abs.
1904. 00962
Minyi Yue and Lei Zhang. A simple proof of the inequality MFFD(L) < 71/600PT(L) + 1, L for the MFFD bin-packing algorithm. Acta Mathematicae Applicatae Sinica, 118):318-330, jul 1995. ISSN 01689673, doi: 10.1007/BF02011199
12

---

Under review as a conference paper at ICLR 2022
Appendix
TABLE OF CONTENTS
Introbetioon
Wikipedaa BERT pr-traiming dalaase
3
Methodk
Packing algonitimn
puckedl model changes
5
Hyperpuramtir adjusiment
4 Experiments
Bin algonihm
byperarameier uljustmeni
Scaling inalysi: Imjucct number necelerators
Conclnsion
A Theorem on LAMB hyperparameerr corvection heuristic
BI Un-gadiiing scaling estimati
C Ablation study
D SQUAD LT
Technical background packing
packing problem
Approtimtt Bin-jucking prehlem
Dehontions
E4 Non negalive least squares histogram packing
Discussio resiiaa weight chotce
Complexll andlysis the packing
Complexity Analysi mon-nogative lant--quunes Instugram pucking
Complesity Analyais Siarest--puck-isst hettgram-pokiing
G Performance Comparison to GREEDY Packing in 15
| Packing SQUAD H
25
Packing GLUE
26
Packing Audio Data (1 LibriSppech)
K Packing Paper Absiracts (PubMMed)
Further
lomgsst-puck-line histograam-pan grackng
padding weighting
Packing source code
13

---

Under review as a conference paper at ICLR 2022
BROADER IMPACT
We showed that when pre-training BERT on Wikipedia, the computational overhead taken to pro- cess 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 to a broader audience of NLP practitioners. As such, we are hopeful the research will have a positive impact on the NLP community, and do not see any disadvantage of using this approach.
The benefit of our algorithm is based two assumptions: A skewed length distribution in the training dataset and a hardware setup that trains efficiently on a fixed batch size. If efficient train- ing is possible, with variable batch size approaches like FasterTransformer and the fairseq sorted batch approach will result in the same or even larger benefits (due to smaller self-attention matri- ces). If the dataset is generated differently like in GPT models (Brown al. 2020) and RoBERTa (FULL-SENTENCES) (Liu et al. 2019), all sequences will be at full length and sequences cannot be concatenated and there indeed no benefit in packing sequences. However, strategies that reach full sequence length usually combine segments from different unrelated document sources which can result in reduced performance. Even in the normal BERT model, there might be this contam- ination between segments from different documents. Our paper introduced an approach to avoid the contamination between sequences. However, the same approach could also be applied to avoid contamination between segments and it remains future work to explore its benefits beyond BERT pretraining.
Future work would need investigate the applicability of packing text produced by different cul- tures 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 Wikipedia but also other datasets such as SQuAD and GLUE. Furthermore, the sentence length distribution of the original English language text shows similar characteristics. Our research leads to believe that compressible distributions arise naturally in language tasks and beyond, for instance in DNA sequence lengths (Hansen et al.) 2017), protein lengths (Guillén et al., 2213), and speech (Section J.. Many such sequence modelling workloads are based on variations of the BERT//ransformer architecture and would therefore easily benefit from our acceleration.
Failures in NLP can have 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 po- tential source of етror comes from the implementation. Both the attention mask and the per-sequence loss need to be modified to support packing. These changes are significantly smaller than those re- quired by custom kernels, however they may still be time consuming to implement and debug. To help mitigate the risk of any implementation errors, we share our reference implementations of the required changes in the appendix.
A THEOREM ON LAMB HYPERPARAMETER CORRECTION HEURISTIC
With packing, the effective batch size changes and hence hyperparameters of the LAMB opti- mizer (You al., 2019) need to be adjusted. For packed dataset with a packing factor p, update the decay parameters as: 31 == 3r, 32 == S8. For instance if [3 0.81 for the un-packed dataset, then for packed dataset with an average of 2 sequences per sample one should use a value of 0.812 s 0.66 instead. Assuming number, we can prove that this heuristic is the exact solution to make sure that momentum and ve- locity in LAMB that p 2 1 by definition.
only minor changes in gradients and p being natural
unaffected by packing. This can be proven by mathematical induction. Note
Theorem 1. For any p E N and assuming that respective gradients on batch of b random samples are (approximately) the same, choosing
B = 3
:= 3
(2)
as Iyperparameeeess in the LAMB optimizer ensures that the momentum and velocity after p separate update steps are the same as with one packed update step with p x b samples.
14

---

Under review as a conference paper at ICLR 2022
Proof.
Base Case:
For 1 the left and right side of the equation are the same which matches exactly the unpacked case. Hence, the theorem holds for 1.
Inductive hypothesis: Suppose the theorem holds for all values of p up some 1.
Inductive proposition: The theorem holds for +
Proof of the inductive step: Let be the loss function, wy the weight vector after updates, and zi..... 2 the respective underlying data to calculate the gradient 9c- For single update step in LAMB with batch size samples, we compute the gradient
al Ow
(x w²).
(3)
==1
Since R 92 2
R 91+1, We have with the inductive hypothesis and the definitions in
LAMB:
my mo + (1 - 3f
(4)
0 3 uo + (1 85)92
(5)
Now calculate (with 91 gk+1)
mk+1 31m + (1 - 31)9h+1
(6)
31 (ff mo (1 )f)))) (1 -1)91
3 mo + +(1 - 1-= 3/+ )g
The calculation for uk the same. As reference for packed update with p + 1 with and B2 would get
P
al
p
al dw
pb
tw
(o)
(o) wn)
91
g1
(9)
j=1
since we are calculating gradients over b samples which are assumed to be approximately the same. Consequently, the updates for momentum and velocity would be
गgद 3i + (1-B1)
(10)
UA
3200 + -1 -1-B2)
(11)
Hence, = and B3 a required to map to the formula with the consecutive updates (for the same amount of data).
Conclusion: The theorem holds for any p E N.
Since proved that the formulas 31 := BP. ,2 Bg. hold for all p N, p 2 1, it is safe to assume that is an appropriate heuristic for all E R. 1.
15

---

Under review as a conference paper at ICLR 2022
B UN-PADDING SCALING ESTIMATE
Firstly, we retrieve the per-batch processing time for an un-padding implementation running pre- training on the Wikipedia dataset from (NVIDIA 2020). These processing times were obtained using 8 GPUs each with a per-device batch size of 32, We also retrieve the throughput numbers for the same system running with padding from (VVIDIA 202T) and use that as the baseline compare the un en-padded throughput against.
The throughput on the GPU system is effectively limited by the slowest of the eight batches being processed in parallel. The Gumbel distribution is particularly suited to modelling the maximum or minimum value of a fixed size collection of i.i.d. samples (in this case batches). We observe that on 8 GPUs the throughput (i.e. speed-up) distribution indeed closely resembles a Gumbel distribution with a1
1.6 and 3g- 0.13 as shown in Figure 6
8 GPUs with (bs=32 each)
1 GPU with bs=32
1.2
3.0
fitted Gumbel
Estimate
data
1.0
probability density
2.5
0.8
2.0
0.6
1.5
0.4
1.0
0.2
0.5
0.0
0.0
0.0
0.5
1.0
1.5
2.0
2.5
3.0
0
3
4
speed-up from un-padding
speed-up from un-padding
Figure 6: Left: Speed-up from un-padding on GPUs closely resembles Gumbel distribution. Right: statistical estimate of speed-up distribution on GPU system running un-padding
We can extrapolate the performance on the 8 GPU system to larger clusters by recognizing that the processing time for each cluster is effectively determined by the slowest batch being processed. Specifically, we could randomly sample (without replacement) two processing times for the GPU system, and record the max of the two the processing time for a system of 16 GPUs. However, this simple approach is too sensitive to outliers in the data and would result in an under-estimate of the performance of un-padding by avoiding directly sampling the processing times. Instead, we fit a Gumbel distribution to the processing times of single batch of size 32 running on one GPU, To perform the fit, we observe that the edf on one GPU (P1) is related to the edf on 8 GPUs (Ps) through (Kotz & Nadarajah 2000 sectionn 1.3):
large systems. We mitigate the effect of outliers in the data
(1-)s(s)) (1 P())
(12)
In other words, if the speed-up up on the cluster is larger than s, this implies that the speed-up on every GPUs the cluster was at least 8. Assuming P1 Gumbel and given the GPU Gumbel parameters ag and 8s. we need to fit two parameters, on and Bi. Consequently for the median (s = 0g-- - Bg (n(((2))). Ps(s) = 0.5), we have:
0.5 = (1 - (i Bg (n((n2)))))
(13)
And since P& Gumbel, we also have an equation for the mode (s agg Ps(s) e11):
(1- = (1 - (as))
(14)
We solve these two non-linear equations simultaneously using the standard SciPy optimization pack- age.
16

---

Under review as a conference paper at ICLR 2022
Listing 1: Infer Gumble distribution parameters.
Smpozt nunpy From scipy
stata, optimize
a 1.6038
bata_s 0.1286
def (())
=lpha__, bela_l
stats.cunbele. (1ocmalpha_., acale-beta_.) Equattions for median and mode
median alpha_3 - bata_ Leg Inp. 1og dist (med-ant
equation! 10
11 made algha_ equation2 (d-ap.exp (-1)) disc.st (node) rxpuepa
12
13
lequationt
Fon2vA2)
14
15 rea aptinisa.nininiee [alpha__, beca_s], methods "dlldd Mead"!
16 alpha 1, beta rea.x
The resulting estimated speed-up Gumbel distribution for a single device has 1.94, 8 = 0.108 and is shown in Figure [right]. [right([[righ).. To simulate the performance of 32 per device, we take the minimum over n samples from this distribution. Repeating this process to generate many samples allows us to estimate the expected speed-up for any given cluster size. Unfortunately, we cannot make any statistical inference about the processing times of individual sequences since the data is only provided at the granularity of 32 sequences per batch, and is not clear how much of the computation is done in parallel and how much in serial.
cluster of size n with a batch size
C ABLATION STUDY
So far, have shown that with the introduced adjustments, BERT. the following, we wanted to analyze in how far the masking adjustment required. In Figure 7
match the accuracy of unpacked
that without our adjustments, training loss and accuracy worsen drastically and a longer training time does not lead to recovery. When not adjusting the positional embedding, the loss and accuracy almost match. However, the accuracy stalls at 71.8% and does not reach the target accuracy of 72. 1%. So overall, both adjustments are crucial.
training accuracy (percent)
no mask adjustment
4 10
packed BERT baseline
65
no emb. adjustment
3 10"
training
no mask adjustment packed BERT baseline
10"
55
no pos. emb. adjustment
50
0
500
1000
1500
500
1000
1500
Iteration
Iteration count
Figure 7: Comparison of learning curves with and without mask or positional embedding adjustment in our packed BERT approach. The grey accuracy baseline to reach is 72.1%. %.
D SQUAD 1.1
Packing slightly violates the i.i.d. assumption of data. Thus, it is of interest, if the algorithm matches downstream performance. This is especially relevant with a full training setup without a starting checkpoint. We trained Phase 1&2 of BERT base with and without packing. To avoid giving an ad- vantage to packing by further hyperparameter tuning, we instead reduced the gradient accumulation count for the packed BERT training for Phase and Phase 2 match the total number of sequences that get processed. With this approach, we could use the same hyperparameters and number of training steps. This gives slight disadvantage to the packed run. For Phase 2, we used sequence length 348 since longer range attention is not relevant for SQuAD 1.1. For the fine-tuning training on SQuAD I.1, we did not use packing. After 10 repetitions, the results showed that on average, the Fl score is reduced by 0.003% whereas the EM score is improving by 0.049%.
17

---

Under review as a conference paper at ICLR 2022
E TECHNICAL BACKGROUND ON PACKING
E. CANONICAL PACKING PROBLEM
The bin-packing problem deals with the assignment of items into bins of fixed capacity such that the number of utilized bins is minimized. In the canonical formulation of the packing problem vector s(i) of length is used to represent the items being packed, where s(i) denotes the length of the i-th sequence/item. The allocation of items into bins is tracked through the assignment matrix B, where B.j E {0, }} states whether the i-th sequence should placed into the j-th bin. In the worst case scenario, every item is assigned to its own bin, thus B E R Notably, grows linearly in the number of sequences/items being packed and B grows with the square. To mask out unused bins Y {0, 1), denotes whether the j-th bin is being used. The optimization objective is to minimize the sum of yj while making sure to assign each 8; to exactly one bin and not exceeding the maximum bin capacity 8m for each bin. This problem formulation is well known bin-packing (Korte & Vygen 2012).
n
min
Σ
yj
Minimize the number of bins.
j=1
s.t.
Σ bij =1
Vi
Assign each length/sequence to only one bin.
j=1
a Σ
s(i)bes S 8m
Vj
Cumulative length cannot exceed capacity.
(15)
Bin-packing is a strongly No-complete (Korte & Vygen 2012) problem. Producing an exact and optimal solution is possible with a variety of existing algorithms, for example with the branch-and- cut-and-price algorithm (Belov & Scheithauer (006). However, given that we want to apply it for very large n (16M for the Wikipedia dataset) approximate approach is required.
E.2 APPROXIMATE BIN-PACKING PROBLEM
Approximate packing approaches are divided into online and offline algorithms [Johnson] 1973) Online algorithms process incoming sequences one-by-one in a streaming fashion, whereas offline algorithms have holistic view of all samples to be packed but typically still operate on a per sample basis. This results best case time and memory complexities of at least O(n log(n)) and solutions that can sometimes be far from optimal, especially for the online algorithms which do not have access to a holistic view of the datasets. The simplest online approach (next-fit) would be to keep a single open bin at any given time. An incoming sequence is added to this open bin if it fits, otherwise the bin is closed (can never be appended to again) and a new one is opened to accommodate the new sequence (Johnson 1973). In the case of the Wikipedia pre-training dataset almost 25% of the sequences are of length 512. which makes this approach very inefficient since bins would frequently be elosed because the incoming sequence did not fit. More specifically, this approach is not able to efficiently combine one long sequence with one shorter sequence, when the number of long sequences is large. The algorithms that come closest to the approaches proposed in this paper are the online harmonic-k algorithm (Lee & Lee 1985). which creates harmonic sized bins for the assignment decision, and the offline Modified First Fit Decreasing method (Johnson & Garey 1985 Yue & Zhang 1995), which sorts the data, groups it into size categories and defines a strategy adjusted to these sizes.
In our approaches, dependent on n by operating on the histogram of sequence lengths with bin size 1. Hence, we replace s(i) by its histogram b and the bin assignment y, B by a mixture of strategies x. where the set of all available packing strategies is modeled as the matrix A (see also Section E.4.2).
make three major simplifications. We make the problem of bin packing less
Then, we do not solve the full packing problem but focus the well known 3-partition problem). Last but not least, we solve the limited depth packing problem only approximately either with non-negativity-consraiin linear least squares (Bro & De Jong.
fixed packing depth (in other words
18

---

Under review as a conference paper at ICLR 2022
1997) (NNLS) followed by rounding nearest integer solution or by applying Worst-Fit (Johnson & Garey 1985 Yue & Zhang 1995) to the histogram, sorted from largest to smallest (in contrast to using unsorted dataset). An exact solution would not be appropriate, since the 3 3-partition problem is strongly NP-complete (Garey & Johnson 1990) as well.
E.3 DEFINITIONS
In this section, we standardize the terms used throughout our methods. Firstly, the terms pack and bin may be used interchangeably. Secondly, the presented packing schemes impose limit how many sequences can be packed into any given bin. This limit is referred to as the maximum packing depth. For simplicity, we require the different sequence lengths in a pack always add up exactly to the bin capacity Sm (we can always generate a padding sequence of just the right length to fill-up the bin). A packing strategy is sorted list of sequence lengths, for example [5, 7, 500], such that the total sequence length is no more than and the number of sequences in the pack does not exceed the maximum packing depth. The output a packing scheme is typically as set of packing strategies and the corresponding repeat count for each strategy stating how many times each strategy should be repeated in order to cover the entire dataset. The strategy repeat count is also referred to as the mixture of strategies. The objective of the packing algorithm is to jointly design set of packing strategies and their repeat counts, such that the amount of padding is (approximately) minimized. The presence of padding in the packs either be implicit or explicit. For instance for 8. = 512 the strategy [2, 508] has an implicit padding of 2 (needed to fill the pack up to the 8m). Alternatively, the strategy repeat count may over-subscribe a particular sequence length leading explicit packing. For instance constructing a pack of [4, 508] may require a new padding sequence of length be constructed, if there are not enough sequences of that length in the dataset. The packing algorithms, we present, use both representations.
E.4 NON-NEGATIVE LEAST SQUARES HISTOGRAM-PACKIN
The first algorithm proposed in this paper is suitable for settings where it is desirable to achieve a high packing efficiency with a limited packing depth. The algorithm deterministic and has three major components described in Sections E.4 and E.4.3
E.4.1 ENUMERATING PACKING STRATEGIES OF FIXED PACKING DEPTH
Listing all unique ways of packing up to maximum packing depth can be achieved through dynamic programming. We only consider packing at most up to 3 sequences per pack. This is the smallest packing depth that can eliminate the need for most padding the Wikipedia dataset. Increasing the depth to 4, increases the size of the packing problem drastically and yields no throughput benefit ' With only two sequences, packing would be not efficient since the distribution sequence length is not symmetric. We use dynamic programming to enumerate all feasible ways/strategies that up to M sequences of length
512 can be packed into a bin of length 512. For example, packing strategy may be [512] or [6, 506] or [95, 184, 233]. To avoid listing the same strategy multiple times, enforce the sequence lengths within a pack to occur in sorted order, for example, [95, 184, 233] is equivalent to [184, 95, 233] and should only be listed once. This reduces the search space as well approximately and thus significantly accelerates
as the space of potential solutions by a factor the optimization process. If you had the same strategy repeated 6 times instead of having just one instance of that strategy with weight X, you will have six instances with weight x z/6 (for example, or any other distribution). This would conflict with integer rounding of the solutions and with convergence of optimization algorithms.
E.4.2 CONSTRUCTING THE PACKING MATRIX
The number of rows in the packing matrix is equal to the number of different sequence length categories. For instance, if we using granularity of I token to distinguish between different sequence lengths, then there are "maximum sequence length" rows. Each column of the matrix corresponds to valid packing strategy (given the depth of packing). An example packing matrix for fitting up to 3 sequences into sequence length 8 is given in Table Each column of the matrix
For data distributions that are more skewed than Wikipedia this might look different.
19

---

Under review as a conference paper at ICLR 2022
represents packing strategy. For instance, the first column represents the strategy [1, 1, 6] of packing two length-1 sequences and one length-6 sequence together to form a pack of length 8. The number of strategies (and columns in the matrix) is discussed in Section F For a packing depth strategies. For depth 4, around
of 3 and maximum sequence length, we obtain around 22 +68 +12 +2) more get added.
12
288
Table Example packing matrix for sequence length Columns represent different kinds of packs. Rows represent the number of sequences in these packs with a certain length. The last column represents a pack with only a single sequence of length six.
2
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
2
0
0
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
E.4.3 SOLUTION OF THE NNLS APPROXIMATE PACKING PROBLEM
A solution of the packing problem is the mixture of packing strategies that minimizes the amount of padding in the packed dataset. We solve directly for the mixture (positive real numbers) and recover the padding as the negative portion of the residual (see Section E.4.4).
min ZER
||A x 612 611²
(16)
x 2 0
The solution vector x will represent the mixture of the columns of A, in other words the mixture of valid packing strategies such that x is as close as possible (in the least squares sense) the histogram of sequence lengths 6. We obtain a solution with non-negative least squares implemen- tation (Lawson & Hanson 1995; Virtanen et al. 2020) Interestingly the case of sequence length 512 only 634 out of the 22102 available packing strategies of depth up to 3 are used (3%).
E.4.4 PADDING AS THE RESIDUALS OF THE PACKING PROBLEM
We compute the residuals of the least squares solution (after rounding the mixture to integer) as:
b A round(x:
(17)
The negative portion of the residuals represents sequences that we are "short". That is, there is a deficit of those sequences and represents sequences which have failed to be packed. Typically, there a deficit of short sequences and surplus of long sequences demonstrated by the following plot.
oubr-subse to them. The positive portion of the residuals
In total, there are n = 16'279'552 sequences in the Wikipedia pre-training dataset. After the non-negative least squares packing (and rounding to integer solution) there are 56'799 un- packed sequences left un-packed (about 0.352%). The residual on sequence lengths 1 to 8 are [-4620, -4553, -4612, 46644 33723, -3336, 3628, 3970].. These negative residuals imply that we need to add this many sequences of their corresponding sequence length to realize the mixture of packing strategies. In total the first iteration introduces 7.94106 tokens of padding. In contrast large sequence lengths have positive residual (a surplus of unused sequences). For se- quence lengths 504 to 512 the values are [3628, 3936, 3724, 4613, 4612, 4553, 4619, 0). Note that sequence length 512 has residual of 0 since they do not need packing. Intermediate sequence lengths typically have non-zero (but much smaller) residuals.
The detailed code for the algorithm is provided in Listing 2
E.4.5 RESIDUAL WEIGHTING
A natural extension of the non-negative least squares problem introduced in Section weight the residuals different sequence length differently.
E.4.3 is to
20

---

Under review as a conference paper at ICLR 2022
Un-weighted nnis packing residual
4000
number of sequences
-4000
under-used sequences sequences
100
200
300
400
500
Figure 8: Visualization of the residual of the NNLS packing problem
min #ERm
(wwA) x (wob)
(18)
20
We should not significantly penalize deficit in short sequence lengths (smaller than 8 tokens) as adding up to 8 tokens of padding is not much overhead. Similarly, a surplus in long sequences is not worrisome because the amount of padding needed to achieve sequence length of 512 is small. Reducing the weight of the residual on the first tokens to 0.09 leads to the following residual plot shown the right in Figure In this the residual is almost entirely shifted to the shorter sequences and the positive residual on the longer sequences has virtual disappeared.
Weighted packing residual
-5000
110000
-15000
-20000
-25000
under-used sequences
over-used
sequence length
Figure 9: Visualization of the weighted residual of the NNLS packing problem
21

---

Under review as a conference paper at ICLR 2022
E.5 DISCUSSION OF RESIDUAL WEIGHT CHOICE
This section discusses the choice and effect of the weighting parameters in the NNLSP packing algorithm. To simplify the problem of selecting reasonable defaults for the residual weights, use just two parameters to completely describe the weights: an "offset" parameter and a "weight" parameter. Originally, all sequence length residuals are given the same weight of 1. This results in a packing with leftover long sequences, because there are not enough short sequences to pack them with. To reduce the residual on long sequences, we could either increase the residual weight on long sequences or reduce the weight on short sequences. We chose to reduce the weight on short sequences. Specifically, sequence lengths up to the "offset" length have reduced "weight". The other residual weights stay at 1.
To start, we chose an offset of 8 tokens, which is the smallest power of for which there are examples in the Wikipedia dataset. We decrease the weight sequences shorter than the "offsset" from to 0.9 to 0.09 to see which order of magnitude the most appropriate. On visual inspection (looking the residual plots in Figure 9 we found that 0.9 still left too many long sequences unpacked. So, we reduced the weight a further order of magnitude to 0.09. This seemed sufficient to encourage nearly all long sequences to pack. While visual inspection helps in understanding how many long/short sequences are leftover, we are also interested in the impact the weights have on the overall efficiency of the packing.
Without any weighting, we get 99.77635999 efficiency, whereas the weighted approach results in 99. 746274% efficiency. Hence, we conclude that the impact of the weights on the packing effi- ciency is very limited. Additionally, using an "offset" length of 4, resulted in similar numbers, for the full range of weights from 0 to 1. Using a weight of for an "offset" length of 8 resulted in insignificantly higher efficiency of 99.7519%, whereas using an "offset" length of 16 reduces per- formance to 99.3 99.38964%. A weight of 0 implies that the residual on those lengths can be safely ignored, i.e., the packing algorithm can thus add as many short sequences as it chooses without any penalty. It is very interesting that this does not significantly impact the packing efficiency, and can have slightly positive impact. However, increasing the "offset" length further significantly decreases the performance with weight O. Keeping the weight at 0.09 and increasing the length reduces performance slightly, for example with 99.53% at length 256 and 99.728% length 16.
For our Squad analysis, weighting improved the efficiency slightly from 96.94% to 97.38%. Fine tuning further with direction grid search, delivered a local optimum of 98.767% efficiency with length 64 and weight 0.002.
Overall the influence of different residual weights the packing efficiency (and the acceleration factor) is less than 1%. This might differ from application to application, but it shows that we are able use the residual weights achieve secondary targets (like not having leftover long sequences) without significantly compromising the packing efficiency.
22

---

Under review as a conference paper at ICLR 2022
F COMPLEXITY ANALYSIS OF THE PROPOSED PACKING APPROACHES
Since approximate packing algorithms have a complexity of at least (nglog()) and we would like to be able to tackle datasets with 2K million samples, we will discuss the complexity of our packing algorithms this section. The complexity depends on the maximum sequence length 8ms the number of samples n, and the packing depth d.
To create the histogram, we have to iterate over the data once (O())). Our histograms will be binned by size 1, meaning one bin for each sequence length. Hence, dictionary can be generated (O(sm) and used for the sorting (O(1)). The respective histogram vector has dimension 8m.
F.1 COMPLEXITY ANALYSIS OF NON-NEGATIVE LEAST-SQUARES HISTOGRAM-PACKING
For packing depth of one, there is only the strategy [sm]] For a packing depth of two, we add
the strategies [1, 8m 11, ...: [8m - L ]] which results an additional 8. potential strategies.
Following the dynamic programming approach, the number of possible additional strategies of depth three can calculated with
pm
Pm-3
Pm
potential strategies
Σ
8m
J
- (j - 1)
2
[=]
j=1
3
8mm 33 /
8m
(19)
2
2
2
12
Note that for 5m -122 the approximation is exact. This means that strategy matrix A has the dimensions 8m x
1 | +1). Overall, this leaves us with a space complexity of 8% since is larger than w, 2, and So it contains 11:316'224 numbers which is still much smaller than n. Note that the original data matrix B had n² entries, which all needed to be optimized together with the n bin assignments y. now now have only [2
[2
12
6m free variables in the strategy vector r. Also note that A can be precomputed when sm. is known and independent of the number of samples. Given a problem matrix with dimension i x j. Luo et al. (Luo & Duraiswami] 2011) indicate that the asymptotic complexity of most solution approaches O(t)"). whereas they propose an Oiij) solution. Since we use the standard SciPy implementation (Lawson & Hanson 1995), our estimated total time complexity for NNLSHP O )..).
+ +
12
For 8m 2048, the estimate would be 350'540 potential strategies which is still far less than the number samples. For packing depth 4, we calculate (Wolfram Research Inc.):
fm
Fm -
T=
i=j
2m
k 4 -j 8m
jmn
(20)
+ - 4k)(s (3 3 4k)
12
s2s + 9s +4)
288
1
s(s + (2s + 1)
288
23

---

Under review as a conference paper at ICLR 2022
So with Sm 512, there would be around 940K strategies. In implementation, this number of strategies would be too high to create the problem matrix. One alternatives to simplify would to not use the exact length of sequences but only consider even numbers for the sequence length and round up. That way arbitrary sequence length could also be handled and the limiting factor would be the complexity of the attention layer in BERT which does not scale well with the sequence length.
F.2 COMPLEXITY ANALYSIS OF SHORTEST-PACK PART-I SEEDOGGRA-PAACCIIN
The complexity calculation of SPFHP is straightforward. We go over the whole data once for the histogram sorting. Next, we iterate over each of the 8m bins in the histogram. Lastly, we iterate over all strategies that were encountered so far. It can be proven that, each iteration, the number of strategies can be maximally increased by one. In each step, we potentially add a sequence to existing strategies but new strategy is opened up only in the final step, when we either create new strategy or we split one of the existing strategies into two. Hence, the number of strategies is bounded by 6m. and the overall time complexity is bounded by O sy,) ). The space complexity is (ss))) m) since we need to store up to 8m strategies with maximum 8m. counts for different sequence length.
G PERFORMANCE COMPARISON TO GREEDY PACKING IN T5
'5 (Rffell al. 2019) is normally trained the C4 dataset. However, give idea of the difference in packing efficiency and acceleration compared to our newly introduced algorithm, we can analyse the performance of greedy aggregation of samples on our given Wikipedia dataset.
We take the histogram and cast it back to a list of different sequence lengths since this is all that matters for analysing packing behaviour. Next, we randomly shuffle the dataset and iterate with the greedy aggregation algorithm multiple times to account for randomness. We iterate sequence by sequence and combine them provided the maximum sequence length 512 not yet reached. If is exceeded, the packed sequence is considered finished and a new sequence is started.
The greedy packing algorithm itself takes a bit more than seconds, since we are operating on single sequences and not histogram counts. The efficiency of this approach is 78.24% (standard deviation of 0.005) compared to our 99.75% for NNLSHP. The respective acceleration would be around 1.566x compared to our 2x. With respective separator tokens, the performance decreases around 0.13% for one separator token and 0.27% when two separator tokens are required between two sequences. Following the brief documentation at https: wtt.:/tthw.oootoeeeooeeeeeeeoo wttp://stteeeetooooonoeoooo hhtpas//taaarrbbbb/2222222222fan
fd0d/
tensor2tensor/eant http://awweaaaataaeeeeerrrrrrrrr lor tokens would be expected in the T5 processing.
two
separa-
In addition the packing preprocessing, our paper proposes, rather than using separator tokens, to instead modify the masking of the attention matrix during training. The RoBERTa paper shows that avoiding contamination sequences from different documents can consistently improve down- stream Fl scores by 0.35%.
24

---

Under review as a conference paper at ICLR 2022
H PACKING SQUAD 1.1
We tokenized SQuAD (Rajpurkar et al. 2016) for BERT (Devlin et al. 2019a) with maximum sequence length 384 and visualized the histogram over the sequence length (Figure TOp. The distri- bution looks similar to the Wikipedia dataset but is slightly less skewed. However, the maximum sequence length only had an occurrence of 1.2% compared to 23.5%. Hence, the theoretical un- padding speedup is 2.232. In Table 3 we can see that SPFHP does not concatenate more than samples and obtains 97.54% efficiency in contrast to a maximally used depth of 16 with 99.60% efficiency on Wikipedia, because of the less skewed distribution. Note that we have less than 90'000 samples. Hence, NNL.SPP less efficient because the rounding in the residuals has much larger impact compared to more than 16 million sequences in the Wikipedia dataset.
0.012
0.010
probability density
0.008
0.006
0.004
0.002
0.000
50
100
150
200
250
300
350
400
sequence length
Figure 10:
SQuAD 1.1 BERT pre-training dataset sequence length histogram for maximum se-
quence length of 384.
Table 3: Performance results of proposed packing algorithms for SQuAD 1.1 BERT pre-training.
packing depth
packing algorithm
strategies # packs
tokens
# padding
efficiency
packing
used
tokens
(%)
factor
none
348
88641
34038144
18788665
44,801
1,000
2
SPFHP
348
45335
17408640
2159161
87.597
1.955
3
NNLSHP
398
40808
15670272
420793
97.310
2.172
3/max
SPEHP
344
40711
15633024
383545
97.547
2.177
25

---

Under review as a conference paper at ICLR 2022
I PACKING GLUE
To explore a variety datasets and emphasize that skewed distributions are common, we explored all datasets in the GLUE benchmark (Warstadt et al. 2018 Wang al. 2018) that came with training data. We loaded the datasets using the HuggingFace dataset loading API (Wolf et al. 2020). For preprocessing. we followed the implementation the HuggingFace transformers repository (Wolf et al. 2020 and extracted the respective data processing snippets to obtain tokenized data with maximum sequence length of 128. The histogram of the sequence length for each of the included datasets is displayed in Figure 11 and the packing results are given in Table Each dataset benefits from packing. The lower the mean, the higher the packing factors are that can reached but with higher packing depth.
Sequence length distributions of GLUE Datasets
cola
stsb
wnli
probability density
0.10
0.08
0.06
0.04
0.02
0.00
20
60
100
120
sequence length
Figure 11: GLUE dataset sequence length histograms for maximum sequence length of 128.
Table Performance results of proposed packing algorithms for the GLUE dataset. Only the base-
line and the SPFHP packing results without limiting the packing depth are displayed.
data
packing
# strategies
# packs
tokens padding efficiency
packing factor
depth
used
tokens
(%)
cola
34
8551
1094528
997669
8.849
1.000
cola
13/max
29
913
116864
20005
82.882
9.366
sst2
1
64
67349
8620672
7723633
10.406
1.000
sst2
15/max
64
7691
984448
87409
91.121
8.757
mrpc
77
3668
469504
274214
41.595
1,000
mrpc
4/max
74
1606
205568
10278
95,000
2.284
123
363846
46572288
35448844
23.884
1.000
qqp
5/max
123
97204
12442112
1318668
89,402
3.743
stsb
85
5749
735872
575993
21.726
1.000
stsb
6/max
83
1367
174976
15097
91.372
4.206
mnli
124
392702
50265856
34636487
31.093
1.000
mnli
8/max
124
123980
15869440
240071
98.487
3.167
112
2490
318720
152980
52.002
1,000
rte
4/max
108
1330
170240
4500
97.357
1.872
wnli
72
635
81280
57741
28.960
1,000
wnli
6/max
63
192
24576
1037
95.780
3.307
26

---

Under review as a conference paper at ICLR 2022
J PACKING AUDIO DATA (LIBRISPEECH)
In this section, we show that packing can benefit other domains than NLP like ASR. We use the LibiSpeech dataset (Panayotov al. 2015) and preprocess it as described reference implemen- tation 5) The resulting histograms for the subsampled audio sample lengths and respective text labels are provided Figure
0.008
probability density
0.006
0.004
0.002
0.000
50
100
150
200
250
300
sequence length
0.025
0.020
probability density
0.015
0.010
0.005
0.000
20
100
120
sequence length
Figure 12: LibriSpeech sequence length histograms of preprocessed audio data [top] as well as target text data [bottom].
be seen that the audio sequence length is dominated by long sequences with 38% of required padding to meet the max sequence length of 330. Thus the theoretical optimal speed-up of 1.6x cannot be reached. However, 80% efficiency are possible with any of the proposed packing algo- rithms to achieve 1.3x speed-up. This can be already achieved by combining up to sequences. To achieve almost perfect packing efficiency, a sequence length around 457 and concatenating up sequences required. Due to the quadratic increased computational load that usually comes with longer sequence length, increasing the sequence length is not practical.
If processing and packing the text data independently of the audio, 99.99% efficiency can be achieved with a speed-up of 2.24x.
htttps://githbb com/m1 htwp://////aaaain/////////s////a recognition/pyl
27

---

Under review as a conference paper at ICLR 2022
K PACKING PAPER ABSTRACTS (PUBMED)
This section analyses the length of abstracts to give an intuition about how different documents can be in length. Figure 13 depicts the length of abstracts in characters extracted from PubMed [ If these abstracts were directly used as sequences, a character length of 1000 could result in 1.9r speed-up from packing. The potential speed-ups for length 2000, 3000, 4000 would be 2x, 3x, and 4z, respectively. Note that, document clean-up up procedures would usually eliminate documents that too short or too long for data sanitizing purposes.
16000
14000
12000
count of abstracts
10000
8000
6000
4000
2000
500
1000
1500
2000
2500
3000
3500
4000
number of characters
Figure 13: Abstract length distribution in PubMed.
Note that for the processing in BlucBERT (Peng et al. 2019), paper titles and abstracts get separated into sequences, tokenized, and then combined with the BERT sequence combination approach for maximum sequence length of 128 tokens. Thus, it results in different distribution.
28

---

Under review as a conference paper at ICLR 2022
L
FURTHER LEARNING CURVES
This section provides further learning curves related to Section 4.2
3.5
classic, bs: 1500
0.70
packed, bs: 768
training accuracy
0.65
training loss
3.0
0.60
2.5
0.55
2.0
classic, bs:
0.50
packed, bs: 768
1.5
2
2
samples
1e6
samples
1e6
Figure 14: Comparison of learning curves for packed and unpacked processing with reduced batch size for the packed approach.
classic, beta: 0.81
packed, beta: 0.66
training accuracy
training loss
packed, beta: 0.66, double Ir
0.6
packed, beta: 0.81, double Ir
3
classic, beta: 0.81
0.5
packed, beta: 0.66
2
packed, beta: 0.66, double Ir
0.4
packed, beta: 0.81, double Ir
0
samples
1e6
samples
1e6
Comparison of learning curves for packed and unpacked processing with heuristics applied.
Figure 15:
3.5
classic, bs: 1500, beta: 0.81
0.70
training accuracy
packed, bs: 1500, beta: 0.66
0.65
training loss
3.0
0.60
2.5
0.55
2.0
classic, bs: 1500, beta: 0.81
0.50
packed, bs: 1500, beta: 0.66
1.5
0.0
0.5
1.0
1.5
2.0
0.0
0.5
1.0
1.5
2.0
relative time
relative time
Figure 16: Comparison of learning curves for packed and unpacked processing in the optimized setup.
29

---

Under review as a conference paper at ICLR 2022
M FINE-TUNED LONGEST-PACK-FIRE HISTOGRAM-PACKING
In the main paper, we focused on SPFHP due its simplicity. this section, we analyse the effect of applying the "Best-Fitt algorithm (Johnson 1973). Here, the longest pack that still fits the sequence is chosen instead of the shortest one. In contrast to SPFHP, we additionally consider splitting the histogram count, if it can fit multiple times. A simple example is sequence length 256, where we divide the respective histogram count by 2 to create the optimal pack with strategy [256, 256] instead of the strategy [256]. This latter strategy would be complemented by other sequences but would probably not result in an optimal packing. The implementation of this approach is much more complex than the SPFHP implementation. The code is provided in Listing and the results in
Table 5
pack. depth
strat. used
# packs
# tokens
# padding tokens
efficiency
pack. factor
(%)
508
16279552
8335130624
4170334451
49.967
1.000
2
634
10099081
5170729472
1005933299
80.546
1.612
3
648
9090154
4654158848
489362675
89.485
1.791
4
671
8657119
4432444928
267648755
93.962
1.880
8
670
8207569
4202275328
37479155
99.108
1.983
16
670
8140006
4167683072
2886899
99.931
2.000
29/max
670
8138483
4166903296
2107123
99.949
2.000
Table 5: Performance results of longest-pack-firs cettoraa-ppccking for Wikipedia BERT pre- training with maximum sequence length 512.
We can see that longest- cesitt-pcc-fiint first Histogram-packirn (LPFHP) uses a much higher packing depth when no limit is set (29 instead of 16). Splitting the histogram counts results in slightly higher numbers of used strategies compared to SPFHP where the number of used strategies is limited by the maximum sequence length. The best efficiency of LPFHP is 99.9 99.949% with packing factor of which is slightly higher than the 99.759. (1.996 packing factor) for NNLSHP and 99.6% for SPEHP (1.993 packing factor). All algorithms
very close the upper limit.
Note that for NNLSHP, we only fill up the unpacked samples with padding. Applying best-fit on the remains, similar results can be expected. Although the benefits of the improved algorithm negligible, we share the concept and code below in case packing is applied to other data with different distribution that would benefit more from it, or for applications where only perfectly packed sequences without padding are of interest.
30

---

Under review as a conference paper at ICLR 2022
N
EXTENDED NNLS WITH PADDING TOKEN WEIGHTING
In Section E.4.4, we defined the residual as
= b A round(x)
(21)
and discovered that a positive residual corresponds to sequences that we did not pack at all and should be avoided. Negative residuals correspond padding and should be minimized. Due to this discrepancy, we decided to set small weights for very short sequences (that don't occur in the data). However, was not possible to directly optimize the amount of padding. A negative residual component for length i, results in [ral padding tokens, however a positive residual actually results into (512- rt) padding tokens. This cannot be addressed by our weighting approach in
min FER
(IwA) -x
(22)
S.L. x 2
Working within the NNLS approach, we can strictly enforce non-positive residual (before round- ing to integer). To that end, we define a new auxiliary variable = -(b Az) which is the negative of the residual, r. This will allow to reformulate the objective r S to the non-negative con- straint: F 2 0.
min mER
(lwAA) (wbb]] + W A. w w- FI1
2 0 F F20
(23)
This will enforce F = Ax - b 2 0 due to the large weight, w == 10 and no upper limits on 7. Now, we can set w; := to optimize for the padding tokens. Due to the use of the squared error, we would however optimize the squared sum of padding tokens instead of the preferred sum of padding tokens. To accomplish the latter, we would have to replace the L2-norm problem by an L1-norm problem which would be too complex solve. Note that due to rounding, the unwanted positive residuals r (F < 0) might still occur. This could be avoided by rounding up x instead of normal rounding of To put the new formulation into solver, we replace
AA A
0m
by
x by
by
and A by w
(24)
F
- DDm)
where Om is an m x m matrix with m being the maximum sequence length, 512, and Dm is unit matrix of the same dimensions as Oz Since, we are already close optimum especially on the Wikipedia dataset, the results are only little bit better. The processing time however increases from 30 to 415 seconds without considering the increased time for constructing the processing matrix. Since the slightly improved algorithm might be nevertheless relevant for other applications, we share it in Listing
31

---

Under review as a conference paper at ICLR 2022
O PACKING SOURCE CODE
Listing 2: Non-negative least squares histogram- packing
Lngort tine
numpy ap
acipy Lnbozt cptinize,
fron functoull import Ira_eache
def rer_packino_nattiee (atraateettttttyeyey.o.o.t nax__equenoo_eencchit sun_at-selegied
= ap.aezos (oooaiiaa aequuaeeeenne Sequencc__engtlly Length, oun_stzateggea),, dtypemnp.iit332)
for i, stratocy in enuneraze (stratedy_eet): seg straiegys A[seq_
10
12
securn
13
14
9iru_cache (maxs) 2on)one)
15
get_.packi packing ng ng....... st rategi length, ninimm, ceiniimmiirreeee irerement, terget_lenggh,, dept gap Lasgei,
ger
16
leaci_
17
strategies =
18
Complete
packing with exaosly
depth
20
if gas >= Sindinur_ncrrennnt
21
strategies sepeeee ([gep])
Complete sarple in "depuli" slaps, recuzaively
eleez
24
For new in range (ninimm, intiiiimmmiinneeeneeee increment, gep 1. 1):
25
new_gep Largel_ stagt_
new gep
aepeeaagies.ppeerd (nne]] wlaet
28
29
tons paccing strategien Jength
lerget_lergth,
option options:
it len (option!
12
st esttegiies..ppaaee [ [[tex] option)
33
def pack using ani thi nax requence length, max sequences, per pack]]
36
List all unique ways of packing to the desired neximum sequence length
37
print (StPacking packing strattggttttee
strategy
nox_sequencs. Jength, www.eeeenneeeper..... (len(s: set)l unique packing stteegiees.")
Gct the packing natrix corresponding to this list of packing strategics get pww.ting.neetiiiceeeee iatrii set, nax weguercce_eeneee Weights that penalize the inaid sbort Jength) penslization_cnm
40
41
less.
43
xü on.ones max sequence lengthl)
44
xdl openalll inatlen_cutoff) 0.08
45
Seive the packing problan
(e*egeennee pack: histogram,
47
start tinc.time()
48
strategy_rege http://opoos_oottteeeoeee countt, roarh optinize.nn cap.e
dinsind, -1) A, hiszogrami
49
(=*gal non-negative
took itine.cimed start:3.2e) secords,")
Round the fieating point solutica to copettt_count-..oo .astype (np.in619) strategy_reee wwwpy__rpeettooooo count riurint (strategy_reppl Compute the residuals, shape: max sequence lengthl sesidesl hictogran
integer
52
53
srrategy_ropest_oom
Bandle Lett-over sequences unpacked seglen np.arange!!! [1, max sequence Jergth (residod))) > for in unjacked__cgi22n
positive part sesides.
56
57
stdataoy__ndox stratecy_set int.xxsttt
39
sesatagy_reppe ceopr___opoo__ottttttee (stratogy__nnee index] +- residmel
60
Be-compute the residual with the updated strategy wttpppyy_pppt__on_e_
should
sesideal hictogran A stratogy_ropcst___
And peoding based on detsciz (negative residcal portion at residual)
64
padding np sp.where (sesidual < -residusi, 0; statiscics
65
Calculate
Lequense_lengcht ng.arange C., nax_sequnco_iengt)
67
oid_nebber_e ct__ssgiesses histsgran, sunl)
68
rev hww_nnuberr_tt.coo strpppps____opppes int sereseey__epest_com sim())
speadus_ peeadue_upper__on
1.0/11 (bisccoran- sequenco_iengths bax_sequanss_aaatth)
70
run www.pppdddnggooeee packed sequence_iengtien pedding) .un(()
71
afficiancy
72
(d" etricisncy [Eraction
(stTicioney:3
2t thecretical limit: [apaedap_ low.d......d...4
14
2'Achieved spsed-up ovar un-packed dataset: of____aooooo___aaoooo
75
seturn stsatogy_sot, statoeyy_ooccs_coont
32

---

Under review as a conference paper at ICLR 2022
Listing chortest-packe first aaooggra-packking
Cron collectiona defaulidiet Inport nunpy as "P
def add_pack (pack, count, final, limit, offsel): neepslter packs reached meximon lergth (pack)
seguennces.
final loffset]. apppedd (counk, pack))
elaes
Imploffael eppend
packi)
10
11
def pack ag thiatogram, nax nex sequence lergth, nax perpennces.ptt.pecee
12
neeghocted wat pack firat histogran paoking algoriLim, tor histogran pp..tipphisscggeee
Enitial the nain strategy daca dios tonary,
15
The key indieates how many colens are lelt. for full length.
16
The value 18 litt tuples, conslsting (sorted) list seguence trpp atrategios_per Jength detsultdict (list)
and respective
pack
get
18
19
rttegeee per. length sorfuutd:cct
20
Endex i Indiicate here, how much for sange (max__equeneeeeeooooeoooooooeoee :
ia left, doe reversed histogran
22
n. seguenses to bin reversed histogrem(1)
23
length_ta_bin mex_aequente langth
24
ottset =1 nesggeenes
largest possible
12 siongth_to_bies bin aftset) in pot_rtrattric__pr__oooo
27
extract shortess pack that will get mositied
28
sesguencess
length
iength_to_bin ottect]].pop1)
30
new aex_pack " pacs Llengeh_to_bit count minin miininssepee sequences pact, sequercess bin)
11
32
a_coppences_to__pe r_socjonccs_to__onn
pack gets
34
deequmncas_to_pee - "_scquerces_.o_.bt
35
http://peee.oggghttoonoeteeeeeoe tonniiggtttt_nnnn... appent)
36
pacci)
nucoquaacs__to_liia
38
cise:
39
sequueeces to n_sequences_ to pact
40
po_orrasoqic__por_leeee strategles_pct_lnngt.
42
nax max_secunnes__pr__.
offset]
43
clean to spees nain key scarch
44
aopp_stateggls__pe__oooo let_pee____it__eeeeeeeeee tog attset]:
umg.otatttaaaa_pr__aattt.oo (Leagth_to_bln oftset)
46
clsc:
47
otiset --
48
Dees
effset
50
ado ado_pack
(llnphcc bini, s_sequences_to to.
51
mxx_seqensos_pcr__aae stratecles_pe__lnnttt
52
"Laeguomess_to_Bu
54
nares all scratcgles
55
for tmp_stratocges__p lontgggoitos_pp__onntht:
flacton stratocies dictionary
58
strategy_sot
59
strateqy_repoat_oout []]
stratcoiio_por__cooee
count, pack w.sbeegiww.ae.eeeght....
62
pack.raversad)
63
strateqy_eet.sspedd
stsalleyy_repet__coo
secuED stzstecy_ses, ap.azray wow.aaeyetttttoooooooaoooooo
33

---

Under review as a conference paper at ICLR 2022
Listing 4: Evaluation function of shortest- shortest-pack first histogram histogram-ppacingg
Pa depth analyais of abortest-pact paact-rirttt sestocran-packinng Fron collections ingort defaulsciat
Eepuci Lebulate
Lmpozt tina
segort "p
evaloate_sptapp (alacoqran, nax_soquence_ 1ongth/:
resevaluste shortest pack Fiest histogran packing algori stata_data [l'pack. Septlit, *y strat. used", "6 packa", "A Lakena", padding
10
"afficiency 18)*, "pack. factorr, "tine"]]
for max mex_sequeneee perk start Line.time))
3, &, 16, *max"]:
12
13
usiing sptip histogran, sws_sequenoe Length,, pos_ssegeerooopprrroo dusation tine.time() atart
strategy strategy repest count
14
16
17
Curmanoe Realual lan packing approach nustrategies
18
Lenietrategy retll
packs int foum net reteey regeett counnt)
20
sequembes = sun Jepunt I len(peck] for county pack in
21
ripletrasegy
strategy set) packs)
22
srax_segience_ tnpky_ (aunf[
24
counts (max sequence (engch-oin((ack)) for count, pack in rattsty regest__omunt strategy__et) set)]))
25
26
wng-y_iokens Lotalliokens 100
27
if max sequences per pack "max":
28
lLllnghh nan man (Ilen for pack in strategy_set]] legerd
29
(1))".tomattn in_nnngt!
nax sequenncss_ park, nasteat packs, tokel_ empty_ton tokene, coken_etticions sequences packs, decation]s print (tabul ste.tabulaceisten
32
33
PridergeFFirstron Float fnt=*, 3r"")
Listing 5: Loss calculation
The number of sequences in each barch aequences_ bntba Lf. aequances_in batee tf.cast (secuences, La bn_bethh,, if. (loat32)
(naaked leiggthht
Create the 0/1 nask that wilh be used to un packed sequences lasked_ aiigghh Lf. rearhageee (nasked In anggggght [3, 1, 1]]
reshape range (,, sequence select lan tf.cast heat ve
sequence selection
sequerces per
Apply the mask Lo un pack the loss per sequence
all per token reshaaee (nl token, [3, -111 sequence_se Mosmalize the guz sequence loss by the nutber of alarcokena
10 pel_per_seeeenne
ell_per_tokee
sequence (ax aLandard)
12 attergred tfureduce sun Iseguence, selaction, -1, keepdi nseTrue]
13 bdgggeed attempted tf.cast lestanpted
tf., flow:322
prevent NaNs when dividing by abtwngeed
14 pequeeee per__pe__eeuueoee
Leapted
15 Average per-batch lose (so contribn rintrtttt but tons from different batches are comparable)
16 loslos Lf ane zum (nl] sequence) /seguer in
34

---

Under review as a conference paper at ICLR 2022
Listing 6: Wikipedia and SQuAD 1.1 histograms
nunpy op Mikipedte hi oggreg -p..rrayil
C, 0, D. 0, 1821, 1226, 1989, 13:5, 1794, 1953, 5682, 3446, 4166, 5062,
e554, 16475, 19173, 17588, 17557, 19060, 21555, 23524, 26954, 30661, 33470, 36514, 40134, 43256,
46004,
60624, 65263, 64597. 65421, 68983,
72467. 72954, 23955, 74311, 74835, 74489, 2499C, 75377. 74854, 75096, 74784, 74698, 74337, 74638,
74570, T3557, 73597, 78153, 72358, 7158D, 71032, 70085, 69732, 69445, 67818, 67177, 58641, 65739,
64688, 63841, 63218, 62799, 61458, 60548, 60148, 59858, 58809, 58023, 56920,
55999, 55245, 55051,
63979,
50489, 49307, 49201,
47948,
47724,
46930, 46544,
10
46011. 45259, 66192, 44332, 9.38 18, 43986, 62988, 42365, 42391, 42219, 41668,
41072, 40616, 50581,
11
39999, 40169, 39340, 58906, 35438, 38142, 31755, 57818, 37535, 37217, 36757,
36589, 36151, 35955,
12
35531, 35496, 35089, 35053, 34567, 34789, 34039, 33952, 33753, 33656, 33227,
32554, 3268E, 32880,
13
31657,
31196, 30550, 30316, 32494,
29445, 28921, 29271, 20078, 28934, 28764, 28445, 28319, 28141, 28282, 27279, 27522, 22333, 27470.
15
27289, 27102, 27015, 27066, 25525, 26384, 2613E, 26385, 25392, 26082, 26062, 25660, 25662, 25547,
16
25425, 250-2, 25079, 25346, 24659, 24102, 24862, 24479, 24288, 24121, 24268, 24097, 23798, 258
18
21893, 22096, 21916, 21736, 21555, 21446, 21436, 21486, 21528, 21597, 21301, 2219%, 21281, 22066,
19
20935, 21023, 20888, 20515, 20574, 20511, 20419, 20512, 20114, 20023, 20087, 1995,, 19946, 19866,
20
1956, 19210, 19556, 19477, 19481, 19387, 19225, 19069, 19360, 18685, 19034, 18763, 18800, 19012,
18893, 18 19645, 18577, 1831%, 18459, 1837, 18152, 17822, 18102, 17735, 17989, 17905, 11713,
22
17690, 17303, 17669, 17410, 17583, 17531, 17313, 16892, 16967, 16870, 16926, 17233, 16845, 16861,
23
16576, 16655, 16455, 16687, 15747, 16524, 16475, 16349, 16273, 16255, 16228, 15219, 16021, 16115,
24
15867,
1575., 15856, 15685, 15469,
15664,
15335, 15463,
25
15305,
15078, 14810,
14780, 14654,
26
16585, 24706, 14860, 14373, 15289, 14396, 14615, 10168, 14239, 13987, 14167, 14107, 14096, 14232,
27
13985, 14110, 14094, 14127, 13895, 13869, 1559%, 13572, 13727, 13569, 13782, 13617, 13289, 15333,
28
33425, 13457, 13256, 13404, 13318, 13425, 15919, 13179, 13193, 13257, 13160, 12813, 13149, 15010,
12867, 12958, 12818, 12801, 12769, 12510, 12575, 12573, 12524, 12735, 12523, 12677, 12298, 12469,
30
12341 12945, 12421, 12326, 12110, 12081, 12395, 12156, 12032, 12199, 12150, 12980, 12922, 11825,
11
11 11969, 11851, 11997, 11924, 11759, 11685, 11709, 11783, 11783, 11659, 11649, 11619, 11526, 11575,
32
11236,
11002,
11124, 11000, 11129, 10923, 19965, 11071, 11029, 11026, 10972, 11012,
1093,, 10909, 10750,
34
10569, 10756, 10780, 10575, 10503, 10511, 10538, 10383, 10638, 13471, 10667, 10601, 10430, 10490,
35
10310, 10140, 10469, 10346, 1025%, 10286, 10232, 1035 10182, 101 10095, 10192, 9869, 19073,
36
10148,
10003,
9830, 9854,
9799, 9789, 9880, 9767, 9797, S892, 9393, 9535, 3658, 2554, 9593, 9530, 9523, 3488,
38
9519, 9419, 9418, 9508, 9638, S521, 5277, 9209, 9253, 9022, 9281, 9351, 9259, 8253,
39
9225, 9098, 9268, 9221, 9224, 9106, 9239, 38150441, stype-np. (p.ten...nn66)
40
wikipodia__ne wow_euuueccccccccc_c__. Longth
42
43 squas 1_ Rp
44
C,
8,
3,
0,
0,
0,
3,
0,
0,
0,
9,
C,
3,
5,
10,
22, 24,
35, 35,
42,
37,
85,
86,
87,
86,
37,
50.
99, 85,
46
102,
114,
113,
93, 116, 118, 116, 116, 127,
127,
113,
155,
237.
145,
137,
151,
153,
199.
163, 137.
47
134, 150,
145,
132,
166, 162, 175, 160, 149, 151.
138
156,
148, 176 163,
182
188,
182,
17 199,
48
203,
264,
553.
648, 673,
112,
722,
692,
EST, 747,
754,
712.
781,
825,
836,
737.
776,
755,
799, 793,
50
163, 153,
129,
149.
112,
196, 160,
141
125,
129.
155.
132, 730, 139, 141,
705.
108,
123,
655, 688.
51
688, 677, 662,
628,
635.
618, 185, 327,
562,
619,
562,
S78, 538,
558, 582,
541,
575,
525,
556, 498,
52
529,
291, 388, 358,
365,
358,
255, 257,
267.
308,
325,
204,
332, 289, 252.
304,
242,
283,
54
238, 257, 271,
268,
277,
254 253, 229,
217,
250,
214,
247, 237, 212, 205, 193.
20C,
298, 193, 193,
55
201, 197, 173,
176,
195,
156, 20L, 179, 159,
183,
169,
178,
163,
153,
171, 149,
138, 181, 165, 171,
117, 135,
99, 86, 100,
85, 85.
95,
122,
105,
114,
113, 200.
80,
86,
79,
87,
82, 73, 73,
58
66.
16,
12,
15,
67, 60,
71. 77,
12,
55,
61,
12,
59,
65,
72,
19,
43.
62,
48.
50,
54
45,
42, 53,
59
56.
45,
43,
32,
30,
36,
42,
37,
45,
28,
41,
31,
14,
35,
36,
47,
47,
48,
65,
32,
23,
35,
38,
20, 23,
60
16,
21,
16,
12,
14, 10541
d.ygemop.int55
62
63
384
35

---

Under review as a conference paper at ICLR 2022
Listing 7: Histogram creation for GLUE training datasets
Ezon Exans Cozneza Impozt AutoTokanizez
regort
Lepuct nunpy op
conseantt
Dax_ssquennee length
task_to_Xeva
"col=": ("sentenee", None),
Maol1":
P"pceniss", "hypothesss"
"erpoo:
"qoli*; ("queed ion",
feentarow"
12
"qup": ("queationly
"quescion21
13
"rce*: ["sentencel*
*eenteroe211
14
2aat2*;
15
"acab": ["seatenowi" "aencenoe2"),
16
"anli"; ("sentencell) "sencence2*),
17
18
glue_keys M"oclat,
"mapal, "gup', "atab', 'mill", ritefy (wilf]
unused datasets due to missiing ing crein ning dat
20
unys = (f sttbbllddd famil 1 miisaateehedd "quli", Tax"]
load 21
Jatasel 1:
24 for key in glue. keys:
25
Lecasse__loeds (key) detaset loadd dat wat (fgloe", key, spli iteetriin))
26
27 tokenize data
28
tokenizer teleeTTkeiizeerrroe pret lned bwet base unoossed)
29
tokenized_
key
sent sentencel.oo key, sent ence? key teek__tt_
32
33
def saMogkenize texis"re
Funct est:
34
35
args
36
(examples senttence keyl,) senter oe? key is None
37
coxappoos examples [soatcnes__key]!
result (ekenizer(rangg, ped6 padéingeFales max lengtheran sequence, length, troncat ToneTrue]
40
return recult
41
[key]
(key) (preprocess, fonction,, batcheeeTrue!
43
44 extract length intornstion (tor histogren plots:
45 bistogran_lenath
key in tokoniaed_data::
47
histogren lengnnleegtttet
48 for cumber, key in cnuncrote (ttiittottttcntiid_ddass koy. 1 rax_reosrd tokenized
49
["input_idee input_idss]]:
histogran Lengssheeeehhheeeeeeeeeee append
52
create histogran for packing
53
stae_histogram
data_key aistograr_
55
give wtt.hhittgronntttt..a.. key) rp.arrayl10)
max_eequanco_langt stypernp.intion
56
for entry in iasterranningtthhaaaaaa..o
57
alue_histogrmmmssttt... [entry-i]
36

---

Under review as a conference paper at ICLR 2022
Listing Longest-pad pack- first histogram- paacking-
Cron collectiona defaulidiet
Ingort nunpy as "P ingort Lime
add pack lowck, county top, final, limit, offaet, www.eeeeeeeeeeeneg Sength+112) neepllee out packs that seached maxinut lengch or number of conponents. sanity checks
suncpacki offsel), Minerreet offaet." assert totteet 01, *Too small otteet."
10
11
assert (nff < nax seguence.... gaguenoe_llenttinn lengthi, *To large offeec." if len (pack) limit offeee. append (count, packi]
12
13
elaez
15
Lap Lmplooreel] seppend (eopunt, (count, pack()
16
17
18
det pack_using lpthp thistogram, max wtw.eeeuuce__eereeee ler.gtt, nox_soquenees_por.pe diste.bu:e=true)
19
Longgeet pollonget--pck--ee paa--pakk---tt -irk- histogren-packing:
20
start tine in)()
:p.tiiiphiesegroml
22
Initielise nain strategy esta diccionary,
23
The key indi cates how many sokens are leit for full length.
24
The value is list taples, consieting pack (sorted)
and respective
seguence lengta
get
26
trp, wtt.ssssteies_p.c.cccooo longth dcfoultdict (list)
27
strategies__eet lenghe if sequences
(etau.tdicctllett
28
fmax":
max aas_eequoncos_pt..o pcc_ppck rax_sequence_
30
Index 1 cndisates here, now mach space 15 left, due to reversed histogrem
11
for in range (max sequence length):
32
aLsequencos_te_btt towarood
length_to_brs max.eeeueenee.......eeeeee..e.e. length
36
offset 0 smallest passible effset for perfect fit while r_seeqences_to._ poc 0:
35
36
(length
ottset) in imp.strategiee per__eenghh: extract worst pack
get moditied
38
__segucnces_to__pa pack ttp_ssrattopir__ppr__.oo
39
length_ bin ofteet)-popl) calculate
40
repest mini1
length_to_pinn max_sequenzes wtw_soonoo__pr___eeeee....... (er_ppac----oecppas)))
42
correct dopandant on count
43
while aespppncc__too_a///eepppe --
44
repeat
aot distributa:
46
repsat 11
47
aex_pack pacs patgsh_tt__bijjeageoee
48
"_scquences_ta_pcc count:
old pack getd reduced
51
_asqusncas_to_pacz -a count
52
(cusequnces__t__pe)) pack))
54
R t_ - count repeat
55
elset
[Leequencea_to
add_pack (nsk_packkk count,
58
top sesr:cogie__pp__eertee
strategles_pett perctpeptt_ettt..
59
maLeecuenoo_par__aa max_seqenco_iengt))
offaet [zopeat 11 tonich_to_bia,
60
clean up to apend up nain key searcl.
62
if not tap_at peeraglss_e_eseerreeeeeee tengtt (lenggttttoobbii offset]:
63
wtt.:ttttoooo__p___ooo_oo best fil changed
tloa offset)
66
clec:
67
ofIset 1=
68
Dees
offawt b- nex seguenne length lengt'tttckin
20
sinilar sepecition Lion bus no desendence on pack. repoat nin panuueee_e cengquueee_eenttt/ooeeee wwwggt///ggnntttteeeeeeeeeeeesee tot whill nLoegueenes btnpi//oee.....bi///eee... repeat
71
mak_ssquance__orrpaaey
72
73
24
if not distributa:
25
repeal
adi_pack (flength_so trepeat, (_sequences
77
thp. et straceg per. per. lengt', strategies per length,
78
max wwggenoess per pack, nexusegeenne length bin mux_eecuenco__ee Jength) reguences, bin//regeat repeat
79
37

---

Under review as a conference paper at ICLR 2022
narga scrasooies
Ior key in wtwpallgii_ppe_eeeeee
petteciee_oor_eenthhhe extendd http://www....a.t....otttoaaeeee
flatton
dictionary
steategy_
strategy_sepeat_ []
for key in acsotog.ss_por_icnnth
pack.saversa
10
11
12
Sunnarizs officiency solution
14
suration Line.tine stacs
15
sequense_iengthe ng-arange (2, nax_soquonc__eentt +
16
/eralegy_.rppeel.u nastratogee (eet
18
old number_ of sanp les histoggnan.smml
19
mwy_mabbes_e tf_nnele =trabagy_ ((ounntiii (pack) for
la
sipistrategy. reppratteyrpppet.oooo repeet__coint at streegg setil)
22
Luken nax mex_segonoo Langonos__eengill leng oen_nmbees_of xarppees_____apeeeeeeeee xamplex
25
topay_tokana sur ([counts men_aaeeenc__eengg. un for count, pack
sipistrategy. reppattttttttpprr agrategy setil:
efficiency
sopty_Lokens Lotal_tokena
26
speedup upper bound = 1.0/1l (histogrant(
27
sequence lengths mwx_seguence_.. Beriiie___eggtteee (nngth))..omm) old_number of xamples)
28
print PatPacking efficiency Ifraction of real tokers] aetriciieey:3..44110
30
Seggeed up thecretizal Sinit: Ispeedap uppr.pp hoand:3.4 3f :tAcliived speed
31
packed datasslz [uld_mmbwss_dd _t__sss_f__aaaaeeeeeeeaaa__
semples) sequences sampasss homple///oe_nueeeee munber wtwmnessseeeeeeeeeeeeee pf lamp :3. (5)
secones.
34
returh strategy strategy.ropest.com count
38

---

Under review as a conference paper at ICLR 2022
Listing 9: Extended non-negative least squares settorram-pckinngg
Ingort nunpy as "P
Eron scipy ingust opt in, stats
Cron Funeiools impost lsu_oache
def gel..wwckingnne rix reteeeree wew.eeeueeeeeeeeeeeeeeg.eg Lengthh)
sun_aczalegies len (straleeyyyeee
à op.seroe (tnex (mnes sequence length, seraegg, itypeenp.int sirelegy
10
for seq seq_ in strategys
11
Alseg len b,
12
swLuen
13
roccchc (maxed ceelone)
15
def gel..pokking wt slzalggie (al ar__att mininum,inceeeennt Leught deptl):
16
gap terget length
length
17
strttegee
18
Complete tae packing with exactly number it depth =- 1:
19
20
if gep >- miniien__inereee incrmment:
strategies. (ppeecdd. (gppl)
22
Complete the serple in "degch" steps, reaersively elwez
23
24
rangemniniman. inc.riimnnnncrrmmett.. gap nep_gep target -target_lerghh start_lenge length 13 new_ges 6: strategies.apperttinnnet
25
26
27
28
elset
options
now, nCW, targst_ copth 12
30
for option in opticns:
11
if len (option) > 0:
32
(erataglas.apeend(aa option)
strategies
34
35
det back_usingccanitty thistogran, www_seeccce__sseee
36
List all unique ways paccing desired meximum sequence length
strategy_set
1, nax_sequacc_iangee
mox_peponnee_por__eaa.
38
print Fa*kinking will involve (een
unique packing strategies.")
39
Get the packing estrix corresponding to this list of packing strategies gct_packina_natssk sstsatsoy_sstt, nax_soquerce_ionaa Meights that penalize
40
residual by the nunber resuiting paoding tokens.
42
x0 no no.acray for x in zange (mw___qqurr.o_eeeaa))))
43
construct the packing natrix
44
A bar np.reres (etra/l222a___eeeeeeoaa wtw.osooooccoeeeettt.. (stratttttyy_eee) mox_ceeuencc__enattt veichted naczix
46
bart smax__squunnc_oeer
siallstratog_seetl di. (w8, -1) Higher weight to avoid pocitive residuel
47
48
bar sowx_soquseee__eeoo
op.expani_dina
10+.genp. ones (nox_ocpueeess__seeeeeo
-1)
50
begative singonal unity natrix for napping to restoual
51
A [nex_ pana__soounos_eeettttt Jengthi, len (Stratooyy_ett)
op.exaand_dima
52
10+v6enp ones (nax_pcpanee__ccntttt bar norea [emaa_aeeunoo__ennt Apply veigating to bistagran vestor
-1) htwp_/ooccee_ccssttyyeee..c
54
55
babarl babarimaa wtwp___ouuccc_eeeoeeee
x0 histogran
56
[enx_ssquanoe_eene Selve the pecking problam.
10.:6xmp.cnez
histogran
58
print sequenees to pack: ", histogran. sum
59
stazt tine iine()
60
strateqy_residie residuuu,
opcimize.
b_bas)
repale _omut pocnt stralegy residall (:laaal::llllaalli (al.:
62
print (Stsaivira non-nesative least squares took [tins.tine (1 start:3.22) aecorda,")
63
Round the fleating point soluticn to acarest intoger teaaeey_.epeel__ooe
64
op.rial cetsalegy..ppele.ooot yal (np.
Compute residuals, shase: (mo__oooenoo_ooochh resideal histogren A sarategy_ropest.com
66
67
Bandle the LefL-oves sequences i.s. posilive pazt of sesidua: Lapacked
68
ap.arange max_sqquano__eerrk. [residusl for umparked_aaqllen
20
atzategy = socted([2, nax_seguenoe length 11) $ the depth 1 strategy index stratery_ser. indox
71
72
Ba-conpute the residual raty
strategy_repeet_com [st
73
the updated strateey_.opeat_comd
24
This should now be stristly <.0
25
swidual histogran A cepaaa coont
76
residual postion zesidual) padding = np-shere (residus). < 6, -residusl, 0:
Add gadding based deficis
77
78
Caloulate sus basic ataiisiis sequence_ old number of sanglee histogrann.smml
79
ng-arange (t, max_sequence__ema +
nev_mathe of sangles
82
speadup_ hopppppoppp__ppoep bound 1.0/ (hiscoorans
83
hengths swg.engeen lengthi)) (ammm)))..mmm... () htt/////dddnnnneeeeeeeeeeeeeeeee ofwber_of__seggleee par Lokeenaapeeeeeeeeeaeeeeee
84
deequene_llegglae
padding)
officiancy
nan_padding_ ttt_s_oooeeeeeeedeeee wtwpwwwwbbbr_o__ooo
86
print Pack ing afficiency [frae: fan of real tokersl: [effini 3.4433344
87
2tepeed thsereliaal inal limits lspaedayp soaee:_ 4a)
s*acheeeed speed-up un-packed dataset: number camples/new number camples:5.55im
owcurn sereeggy_ set, repeetyy__ppee_oooem
39

---

Under review as a conference paper at ICLR 2022
APPENDIX REFERENCES
G. Belov and G. Scheithauer. A franchanddcut-andee algorithm for one-dimensional stock cutting and two-dimensional two-stage cutting. European Journal of Operational Research, 171 (1):85-106, may 2006. ISSN 03772217.
doi: 10. 10.1016//.ejoo22044.0000 00.066.. URL https:/7
linkinghub. e www.bberleeeeere.....ee wttp://ww....//accc.e//////////0
Michael R. Garey and David S. Johnson. Computers and Intractability; Guide to the Theory of WP-Completeness. W. H. Freeman & Co., USA, 1990. ISBN 0716710455.
Gabriel Guillén, Claudia Diaz-Camino, Carlos Loyola-Torres Rosaura Aparicio-Fabre, Alejandrina Hernández-L.ppez Mauricio Díaz-Sánchez, and Federico Sanchez. Detailed analysis of putative genes encoding small proteins in legume genomes. Frontiers in Plant Science, 4:208, 2013. ISSN 1664-462X doi: 10.3 20088///02s222130000000
CRLhttps:///wet www.:www.......oooo.ot.........w www.ttirsssstioo org/
article/10. 3389 wwwp:/ppp....e//.p/ 2013 00208
Henrik B. Hansen, Peter Damgaard, Ashot Margaryan, Jesper Stenderup, Niels Lynnerup, Eske Willerslev, and Morten E. Allentoft. Comparing ancient dna preservation in petrous bone and tooth cementum. PLOS ONE, 12(1):1-18, 01 2017. doi: 10.137 1137///oaall.pomo00000444 URL
https: org wt..ggg00..00 010001131/// jttl//oounnlllla pone. 0170940,
S. Kotz and S. Nadarajah. Extreme Value Distributions. World Scientific Publishing Company, 2000. ISBN 9781783261734
Charles L. Lawson and Richard J. Hanson. Solving Least Squares Problems. Society for Industrial and Applied Mathematics, jan 1995, ISBN 978 978-0-89871-356-5. doi:
URL http: //eubs. s am. www./doooo.oooooooooooooooooo..o hbt.k////ooo////// http://bb....iaercroooo/o//oooo/ http://o//oooo/....117777..11111
C. C. Lee and D. T. Lee. A Simple On-Line Bin-Packing Algorithm. Journal of the ACM (JACM),
32(3) 572, jul 1985. ISSN 1557735X. doi: 10.1145/3828.3833 URL/attps://dl.cc
org/ htcp/oo//10 10. 1145/ 3833
Y. Luo and Ramani Duraiswami. Efficient parallel non-negative least squares on multi-core archi- tectures. SIAM Journal on Scientific Computing, 33:2848 - 2863, 2011.
NVIDIA. Performance catalogue for BERT on Pytorch. https: hiiiiiii//gg..iiia...... com/ ratallo/rresoures//iiiieee
2021. nwwiia.
Yifan Peng, Shankai Yan, and Zhiyong Lu. Transfer Learning in Biomedical Natural Language Processing: An Evaluation of BERT and ELMo on Ten Benchmarking Datasets. In Proceedings of the 2019 Workshop on Biomedical Natural Language Processing (BioNLP 2019), pp. 58-65, 2019.
Pauli Virtanen, Ralf Gommers, Travis E. Oliphant, Matt Haberland, Tyler Reddy, David Courna- peau, Evgeni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, Stéfan J. van der Walt, Matthew Brett, Joshua Wilson, K. Jarrod Millman, Nikolay Mayorov, Andrew R. Nel- son, Eric Jones, Robert Kern, Eric Larson, C Carey, ilhan Polat, Yu Feng, Eric W. Moore, Jake VanderPlas, Denis Laxalde, Josef Perktold, Robert Cimrman, Ian Henriksen, E. A. Quintero, Charles R. Harris, Anne M. Archibald, Antônio H. Ribeiro, Fabian Pedregosa, Paul van Mul- bregt, and SciPy 1.0 Contributors. SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nature Methods, 17:261-272. 2020. doi: 01100////4112-09---111
Thomas Wolf, Quentin Lhoest, Patrick von Platen, Yacine Jemnite, Mariama Drame, Julien Plu, Julien Chaumond, Clement Delangue, Clara Ma, Abhishek Thakur, Suraj Patil, Joe Davison, Teven Le Seao, Victor Sanh, Canwen Xu, Nicolas Patry, Angie McMillan-Major, Simon Bran- deis, Sylvain Gugger, François Lagunas, Lysandre Debut, Morgan Funtowicz, Anthony Moi, Sasha Rush, Philipp Schmidd. Pierric Cistac, Victor Muštar, Jeff Boudier, and Anna Tordjmann. Datasets. GitHub. Note: https://githu..com//ugg hwwp://wwww.gngggg//cctttttaeaae
1, 2020.
Wolfram Research Inc. Mathematica, Version 12.2. URL https: www. wol fram com/ wolfram- alphalppaaaae -otooanktttoook-ooo. wwwotebook-edttiiie edition Champaign, IL, 2020.
40


Reviews:
[{"review_id": "mWUg8bqRlbg", "reviewer": "Reviewer_EN5A", "summary": "", "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": "Strongness:\n(1) The method is easy to understand and easy to incorporate into the existing training pipeline. \n(2) The performance gain looks great. \n(3) Have the ablation study to show the effectiveness of the model arch changes.\n(4) Easy to understand \n\nWeakness:\n(1) Although pre-training is an important part of BERT, did you test the different pre-trained models on downstream tasks?\n(2) I did not find the GitHub link in Appendix. The text code is hard to do the reproduction.\n\nQuestions:\n(1) In section 3.3, the authors mentioned the learning rate is not adjusted since the gradient is accumulated by averaging. However, as far as I know, LAMB also uses the averaging of the gradient but it still needs to scale the learning rate. Can you explain more?\n(2) Do you have a comparison of the two proposed packing algorithms?", "summary_of_the_paper": "The paper proposes a simple way to pack sentences together for efficient training. In order to recover the accuracy/performance, several model arch and optimizer hyper-parameter changes are introduced.", "summary_of_the_review": "Please see above.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "gw282yDHkCk", "reviewer": "Reviewer_4Mr1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength:\n\nThe idea is simple and easy to understand.\n\n\nWeakness\n\n1. The authors revealed their identity (affiliation) in the code snippets of appendix. It might violate the double-blind rule of ICLR.\n\n2. The novelty of this paper is limited. Packing is not a new idea and it has been widely used in the official tensor2tensor library and achieved good results: https://github.com/tensorflow/tensor2tensor/blob/3f12173b19c1bad2a7c37eb390f3ad46baee0c19/tensor2tensor/data_generators/ops/pack_sequences_ops.cc. So this can be a useful trick but the contribution might be not significant enough to publish at ICLR.\n\n3. The scenario discussed in this paper is too restricted. For example, 1) it only discuss the wikipedia dataset (that’s how the number 50% comes), but there are a lot more datasets; 2) it only works for BERT training, but there are quite a few other important tasks, such as language modeling (GPT-3). All the numbers reported in this paper are based on this setting, making its generalization capability questionable. \n\n4. The experiment section only shows the training loss of pretraining, but never talks about the downstream fine-tuning. Then how do you conclude that the performance is little affected? After all, the accuracies of downstream applications is the final metric.\n\n5. The paper is a bit hard to read for the following reasons: 1) The contents are not self-contained in the main text — quite a few important contents are deferred to appendix that one cannot easily follow the ideas in the main text; 2) The paragraphs are usually lengthy and verbose —  they can be as long as 30 lines! 3) There are quite a few typos, e.g. “For achieve this”, “¡CLS¿” etc.", "summary_of_the_paper": "This paper proposes efficient packing methods for training sequences of BERT, such that the 50% of the padding tokens in the Wikipedia dataset is avoided to speed up the training. These methods include shortest-pack-first histogram-packing (SPFHP) and non-negative least-squares histogram-packing (NNLSHP) algorithms, which are shown to be straightforward to implement and have little impact on the performance. Empirical studies show that a near 2x speedup over the vanilla BERT training is achieved by the proposed methods. ", "summary_of_the_review": "The paper violates the double-blind rule (in the appendix). It lacks novelty, only works on a restricted setting and is a bit hard to read.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "g2ypKMF7JP", "reviewer": "Reviewer_nPLY", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Most part of the paper is clearly presented. The proposed packing strategy should be novel, easy to implement and also effective. However, I have the following concerns and comments. \n\n1. The paper claimed the packing algorithm doesn't loss accuracy compared with the original algorithm by showing the training loss and training accuracy. However, since the sequences are not i.i.d. in the packing algorithm, I am wondering if the generalization performance on downstream tasks (such as GLUE) will be affected. \n2. As mentioned in the paper, BERT is pre-trained in two phases, where the first phase uses sequence length 128 for 900K steps and the\nsecond phase uses sequence length 512 for 100K steps. Therefore, if compared with this approach, the speedup from the proposed method is probably only 1.2x instead of 2x. \n3. Why do we need a limit for pack depth? \n4. Other than the original training approach, the paper only compares with the un-packing methods in multi-accelerator case. It lacks comparison with baselines such as grouping samples by size before batching as mentioned in Page 2. \n\nMinor:\n1. `s_m` in Sec. 3 is not clearly defined. \n2. The abstract mentioned 0.02 seconds overhead time for SPFHP and 28.4 seconds for NNLSHP. In the main text, I only see 0.03 seconds for SPFHP and no mentioning about NNLSHP. ", "summary_of_the_paper": "The paper proposed to pack sequences instead of padding to reach the max sequence length for each sample for BERT pretraining. To achieve similar optimization results with the original training process, the proposed method modified positional embedding, additional attention masks and other optimization hyper-parameters. On the Wikipedia dataset, the proposed method can achieve 2x speedup while achieving similar training loss. \n", "summary_of_the_review": "Overall, the paper proposed a simple and effective method for speeding up BERT training especially on the datasets with a large variance of sequence length. However, due to lack of comparison with other similar baseline methods, I think the current version is slightly below the acceptance threshold. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "fIn25A3R2r", "reviewer": "Reviewer_g5tJ", "summary": "", "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": "Generally, simple packing ideas are frequently used such as sorting sequences by their lengths and then try to “cluster” near length sequences into one mini-batch. This paper further goes deeper into two interesting packing algorithms and experimented on IPU hardware with Wikipedia style datasets and BERT-large models.\n\nDetailed questions and comments:\n1.\tPossibly trying larger models such as GPT3 and later will be an important directly to testify your ideas: bert-large is not that big enough and saving 50% training time will be more meaningful for super-large models such as GPT3.\n2.\tWikipedia is not generally used for domain specific bert such as healthcare and finance domains, in which pubmed and financial news are frequently used. So, the findings of specific datasets are quite limited and hard to say it is a general finding.\n3.\tNot find any baseline packing algorithms here. Any simple heuristics used in the baselines? Such as sorting by length and then perform the training with as fewer packing symbols as possible in minibatch.\n4.\tFrom reading the paper, I think the two algorithms are not limited to BERT (its MLM and NSP pretraining tasks) and really willing to see other types of pretraining tasks, such as T5, GPT style’s results. These will make an evaluation of these two algorithms’ novelty and generalization ability to be with richer evidences. \n5.\tAlso wonder if the packing algorithms can be applied to ASR tasks such as packing audios as well. It looks that not only applicable to textual sequences.\n6.\tIPU is less available to most readers yet, so possibly also mentions details in GPU/TPU are preferred as well.\n", "summary_of_the_paper": "This paper proposes two packing algorithms for bert pretraining, shortest-pack-first histogram-packing (SPFHP) and non-negative least-squares histogram-packing (NNLSHP). 2* speed was achieved under datasets such as Wikipedia for bert-large training.These packing algorithms packed Wikipedia’s 16M sequences in 0.02s (SPFHP). Packing depths of from 1 to 16 were testified. This paper also has 20 pages near appendix telling about packing algorithms, packedBERT of model changes and hypermeter adjusting, and detailed experiments such as bin-packing algorithm comparison, scaling analysis and technical background on packing with some core codes attached as well.", "summary_of_the_review": "\nStrong:\n1.\tTwo packing algorithms for bert-large and related pretraining models;\n2.\t2* speeding up without losing accuracy for bert-large pretraining under datasets such as Wikipedia;\n3.\tRich analysis of technical backgrounds, experiments, and code details.\nWeak:\n1.\tLimited to Wikipedia and bert-large is a small scope considering that there are rich pretraining tasks, rich domain and rich datasets of different languages;", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "CDOuo6QSsJ", "reviewer": "Reviewer_xs2k", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The motivation makes great sense and the overall structure of the paper is very clear (though I did not read anything in the appendix, i.e., from page 13-37).\n\nUsually dynamic sequence length is not supported in GPU or TPU training libraries. The most common way is to pad a fixed sequence length (e.g., 512) and provide a mask in the input so the padded data can be masked out during computation. The advantage of this approach is that this is straightforward to implement.  However, it loses efficiency by padding all the data into the max sequence length.\n\nThe proposed work is to reduce padding via packing multiple sequences into one fixed length. I am not familiar with publications on this front, but I am aware of an existing implementation of similar methodology in `tensor2tensor` library, there is a `pack_dataset` method (https://github.com/tensorflow/tensor2tensor/blob/master/tensor2tensor/data_generators/generator_utils.py#L671), which is designed following a very similar idea. This implementation in tensor2tensor is not profiling the dataset on sequence length histogram because it is receiving the data in a streaming fashion. So I agree that this paper is definitely doing something related but differently by considering the entire problem as bin-packing so as to look for approximate optimal global solution.\n\nGeneral Significance: The main significance is the two packing algorithms being proposed and experimented in BERT pre-training. Multiple sequences can be packed into one fixed length. However, I see the impact is limited because:\n1) this strategy is data dependent. Though there could be many datasets that have this property, there are also other datasets that could follow a different sequence length distribution in which case the proposed methodology won't achieve similar amount of speedup.\n2) because the packing algorithm enforces a specific order (by selecting which sequence to add to which pack), this affects the i.i.d assumption. Also this assumption is actually important in many data preprocessing pipelines we use for BERT encoder. If we have to use one model (packed) for training pre-trained BERT model, then using another model (non-packed dataset and modeling code) for training downstream models this is really not ideal in development. \n3) this workaround (to reduce padding) creates complexity in the user code, both in the input pipelines and the modeling changes. And more importantly, as the author already pointed out, this workaround also increases the effective batch size which might need a complete re-tuning of hyper-parameters of the model.\n\nNovelty: A baseline implementation of multi-sequence-packing already exists in a public library (tensor2tensor). The author might want to clarify what are the extensions on top of tensor2tensor. As I pointed above, tensor2tensor is consuming data in a streaming fashion, and  this paper is considering the entire problem as bin-packing so as to look for approximate optimal global solution. Could you quantify the difference between using tensor2tensor library vs your proposed two bin-packing algorithms regarding speedup vs quality?\n\nTechnical quality: The overall technical quality is limited because of the limitation mentioned in \"significance\" and \"novelty\".\n\nClarity: The paper is well-structured, with clear relationship between each section. The ideas are clearly conveyed with a good writeup.\n\nMinor issue(s):\n* Formatting problem in section 2 before and after CLS and SEP token. (¡CLS¿, ¡SEP¿ , which I guess they should be <.>) Hopefully this is not a problem from my browser viewing pdf file.", "summary_of_the_paper": "This paper profiles the training data of BERT and finds out opportunities to reduce padding thus saving computation. By packing multiple sequences into one fixed length sequence (two packing algorithms were used), the author shows that a BERT training speed-up of 2x can be achieved without loss of quality. The author also studies how to correspondingly change the modeling configuration and optimizer configurations to compensate the effective batch size increase due to the packing.", "summary_of_the_review": "marginally below the acceptance threshold", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes to re-organize the training data in such a way that padding can be avoided. The novelty is somewhat limited and the results are what one would expect - a nice speed-up of 2x but nothing really game-changing. While the reviewer scores straddle the decision boundary, nobody is very strongly supportive of acceptance and the positive reviews actually have lower confidence.
Decision: Reject