Efficient Sequence Packing without Cross-contamination: Accelerating Large Language Models without Impacting Performance
Authors: Mario Michael Krell
Matej Kosec
Sergio P. Perez
Andrew W Fitzgibbon
Venue: Submitted to ICLR 2023 (2023)
Keywords: deep learning
BERT
IPU
GPU
hardware-acceleration
padding
Wikipedia
NLP
bin-packing

Abstract: Effective training of today's large language models (LLMs) depends on large batches and long sequences for throughput and accuracy. To handle variable-length sequences on hardware accelerators, it is common practice to introduce padding tokens, so that all sequences in a batch have the same length. We show in this paper that the variation in sequence lengths in common NLP datasets is such that up to 50% of all tokens can be padding. In less common, but not extreme, cases (e.g. GLUE-COLA with sequence length 128), the ratio is up to 89%. Existing methods to address the resulting inefficiency are complicated by the need to avoid "cross-contamination" in self-attention, by a reduction in accuracy when sequence ordering information is lost, or by customized kernel implementations only valid for specific accelerators.

This paper introduces a new formalization of sequence packing in the context of the well-studied bin packing problem, and presents new algorithms based on this formulation which, for example, confer a 2x speedup for phase 2 pretraining in BERT while preserving downstream performance. We show how existing models can be adapted to ensure mathematical equivalence between the original and packed models, meaning that packed models can be trained with existing pre-training and fine-tuning practices.

Under review as a conference paper at ICLR 2023
EFFICIENT SEQUENCE PACKING WITHOUT CROSS- CONTAMINATION: ACCELERATING LARGE LANGUAGE MODELS WITHOUT IMPACTING PERFORMANCE
Anonymous authors Paper under double-blind review
ABSTRACT
Effective training of today's s large language models (LLMs) depends large batches and long sequences for throughput and accuracy. To handle variable-length sequences on hardware accelerators, is common practice to introduce padding tokens, so that all sequences in a batch have the same length. We show in this paper that the variation in sequence lengths in common NLP datasets is such that up 50% of all tokens can be padding. In less common, but not extreme, cases (e.g. GLUE-cola with sequence length 128), the ratio is up to 89%. Existing methods to address the resulting inefficiency are complicated by the need to avoid "cross- contamination' in attfnnattnn,on, by a reduction in accuracy when sequence ordering information is lost, or by customized kernel implementations only valid for specific accelerators. This paper introduces a new formalization of sequence packing in the context of the well-studied bin packing problem, and presents new algorithms based on this formulation which, for example, confer a 2x speedup for phase 2 pre-training in BERT. We show how existing models can be adapted to ensure mathematical equivalence between the original and packed models, meaning that packed models can be trained with existing pre-traue pre-tranning and fine-tuning practices.
INTRODUCTION
Many language datasets, including the de-facto pre-training dataset for BERT Winkie-dii,piiaa, have skewed distribution of sequence lengths (see Figure D However, typical machine learning accelerators, and their corresponding libraries, exhibit poor performance when processing variable- length workloads. A simple mitigation is to set maximum sequence length, and to pad shorter sequences with padding tokens. This naive batching is widely used and provided the vanilla BERT implementation well the Hugging Face framework (32). Its effect is enhanced by the offline dataset generation process which, in BERT, attempts to "pack" together sentences so as to fill the sequence length as completely as possible (8. We improve this process
whole-dataset level.
We show that, even after this pre-processing, padding tokens represent 50% of all tokens of the Wikipedia pre-training dataset sequence length 512. Thus, by avoiding processing the padding tokens one can get 2x speed-up for phase 2. Overall, the lengths range between 5 tokens up to 512. Samples of length 512 represent only 23.5% of the dataset,
Beyond the simple batching, other solutions have been addressed in the literature, and in open-source software implementations. When processing sequences, most libraries and algorithms mention packing as reference to concatenating sentences from the same document (BERT) or from different documents (BERT, T5 (24), GPT-3 (4), and RoBERTa (16) as they arrive (GREEDY) from the source dataset to generate the training dataset. None of the respective papers addresses the packing efficiency, i.e., remaining fraction of padding. To "separate" sequences from different documents, a separator token is introduced. However, this is not sufficient and can have significant impact on performance. This is discussed only in the RoBERTa paper which shows that downstream Fl scores get consistently reduced on average by 0.35%. Altemative common approaches overcome the large amount padding in many datasets are "un-padding" as in Effective Transformer (5) and sorted batching (SORT) as in Faster Transformer (21). lingvo (88 fairseq (22). and RoBERTa. However, for

---

Under review as a conference paper at ICLR 2023
running efficiently arbitrary accelerators, these approaches require substantial hardware-specific low-level code optimizations only available on GPUs. Further details are in Sections C
and 4.4
Beyond language models, packing has been also present in other areas of machine learning, however with little to no exploration the literature and mostly hidden some libraries without any further discussion. For example, PyG (Py (PyTorch Geometric) combines combiinss multiple small graphs in batch to account for the large variation size and to optimize the hardware usage when training a Graph Neural Network (GNN). Another example the RNN implementation in PyTorch which introduces "PackedSequence" object and states that "All RNN modules accept packed sequences as inputs" but does not address how sequences are packed efficiently and how the processing of packed sequences is implemented in an efficient manner while avoiding interaction between sequences. Even though we focus on BERT (6) and other transformers in this paper, the general principles can be transferred to many more machine learning algorithms with differently sized data samples.
In this paper, we formally frame the packing problem in transformer based models, and provide some solutions, showing that sequences can be packed efficiently, separator tokens are not required, and cross-contamination can be avoided with little overhead.
In summary, the contributions of the paper are as follows. In Section we produce histograms of variety of datasets showing the high percentage of padding tokens. In Section we present two new deterministic and efficient packing algorithms based established solvers which efficiently pack datasets with millions of sequences in a matter of seconds (or less). In Section 3.2 and Section 3.3 we describe ccross-contaminatii mitigate- and show how the BERT model can be adjusted to show the same convergence behavior on packed and unpacked sequences. We empirically show that the proposed packing algorithms produce a nearly-optimal packing scheme for Wikipedia pre-training dataset (Section 4.1) > and more the Appendix. 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. Further experiments underline the necessity and efficiency of our changes.
tte cause of the accuracy reduction which separator tokens do not
2 SEQUENCE LENGTH DISTRIBUTIONS
max sotuake Sp0ccia 2001
0.00
Eicoreiial sp303 1,210
Depreiiaa ussodus:
xe2
0.00
1815
0.003
0392
0.000
319
800
oegummos kays
VAGUINE ireehh
esquenee lingth
#equetce lengh
03033
0001
350 1/6
Figure 1: Sequence length distributions for different datasets. The three graphics at the top left show Wikipedia BERT pre-training dataset sequence length histograms (token count excluding padding) for different maximum sequence lengths based on the Wikipedia article dump from October 1st 2020. The theoretical speed-up relates not using any padding tokens and not having any overhead from processing the different lengths. Top right: GLUE datasets. Bottom from left to right: SQuAD 1.1, LibriSpeech text labels, LibriSpeech audio token sequence, and QM9 molecules of graph in sequence.
BERT is pre-trained using masked-language modelling and next-sentence prediction a large corpus of Wikipedia articles. Each sequence is composed of one <CLS> token followed by the first "segment" of sentences, followed by <SEP> token, and then finally the second "segment" of sentences. Because these "segments" are created sentence-level increments there is no token-level control of sequence length. Furthermore 10% (default value, (7)) of sequences are intentionally
2

---

Under review as a conference paper at ICLR 2023
short. This leads to significant levels of padding, especially for longer maximum sequence lengths (see Figure [ and Section ([). At sequence length 128 (commonly used in phase 1 of pre-training) the theoretical speed-up is around 1.2, at sequence length 384 this increases to 1.7, and finally at sequence length 512 (commonly used for phase 2 of pre-training) it is 2.0. Despite the widespread use of the Wikipedia dataset for pre-training BERT such histograms have, to the best of our knowledge, not been published previously. This has perhaps lead to the underestimation of the speed-up opportunity available. To put things into perspective, the sequence length 512 dataset contains 8.33 billion tokens, of which 4.17 billion are padding tokens.
Note that the skewed sequence length distributions are neither limited to Wikipedia, as shown with GLUE (30 BT) from Section L and SQuAD 1.1 (25) from Section|[]] (2.2z speed up). to BERT training, as shown with LibiSpeech text distributions (23) from Section M D. nor to text itself, given the LibriSpeech audio data distributions, and the QM9 molecular data (7 26) (1.6z speed-up. Section QT). ). All distributions can be found in Figure Since LibriSpeech audio data is skewed to longer sequences, only 1.3z speed-up could be achieved despite the theoretical maximum of 1.6x. For all other cases, the algorithms presented in Section 3.1 lead to close to optimal packing.
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, S. (Sections 3.1 and F Secondly, we introduce a series of model changes in Section that preserve the equivalence 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 (.2.2), and an adjustment of the the positional embeddings (Section 1 to handle packs of sequences. Other components of the model, such as the feed-forward layer (29), operate on a per-token basis and do not require modification for pre- mre-training. In Section 3.2.3] 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) that lead analogous convergence behavior between the packed and un-packed BERT implementations. Additional videos and animations are provided as supplemental material.
3.1 PACKING ALGORITIMMS
The widely studied and well established bin packing problem deals with the assignment of items into bins of a fixed capacity such that the number of utilized bins is minimized. It has been known for decades if not centuries. Since an exact solution strongly NP-complete (4), numerous approximate solutions have been proposed complexity of at least (n log n). we propose two new heuristic offline algorithms that are tailored to the NLP setting applied to the whole dataset. For a detailed introduction to packing see Section F
(12) 15] 13 35). Since most existing approximations have high
3.1.1 SHORTTSST-PACK-FIEE IISTOGRAM-PACCEE (SPFHP)
Shortest-pack- histogram-packing (SPFHP) works 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. we apply the worst-fit algorithm (5) such that the histogram bin being processed goes to the "pack" f that has the most space remaining ("shortest-pack firstt). If the histogram bin does not fit completely, new pack is created. We also limit the packing depth, in other words the maximum number of sequences that are allowed in 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 3 The time and space complexity of the algorithm are O(n + 2 and )x)), (Section G.2
We avoid the ambiguous terms "hin" and "sample/scquence""eee "nd use "pack" instead to refer to the multiple sequences concatenated during packing.
3

---

Under review as a conference paper at ICLR 2023
3.1.2 NON-NEGATIVE LEAST SQUARES SETTOGRAM-PACKINNG (NNLSHP)
The proposed NNLSHP algorithm is based on re-stating the packing problem as (weighted) non- negative least squares problem (NNLS) (3) of the form WAr wh where 2 0. The vector b is the histogram containing the counts of all the sequence lengths in the dataset. Next, we define the A matrix (the "packing matrix") by first generating list of all possible sequence length combinations ("strategies") that add up exactly to the maximum sequence length. We focus specifically on strategies that consist of at most 3 sequences per pack (independent of b) and encode each strategy of the sparse matrix A. For example, a strategy consisting of the sequence length 128, 128, and 256 in represented column vector that has the value the 12Sth row, the value 1 at the 256th row, and zero at all other rows. The variable describes the non-negative repetition count for each strategy. So a 24 in the ith row of x means that the strategy represented by the ith column of A should repeat 24 times. Moreover, in the un-weighted setting, As = b states that we would like to "mix" the pre-defined strategies (columns of A) such that the number of samples matches the histogram b, and where each strategy is used x 2 O times. We use the residual weight w to control the penalization of the Ar- residual on different sequence lengths (different rows of b). Heuristically, we set the weight of 0.09 for all sequences of length 8 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 F.4.3 and H55 I). The overall efficiency of the packing is not greatly influenced by the weighing (less than 1 % extra speed-up).
column
After solving Axx wh for x 2 0 using an off-the-shelf solver, we obtain 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 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 Onn + sn)) and O (s Further details are provided in Section F.4
3.2 PACKEDBERT: MODEL CHANGES
This section describes how any vanilla BERT implementation should be modified for packed sequence 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, well being required by benchmarks such MLPerfIM (17). The presented approaches and principles apply to a variety of other models.
3.2.
ADJUST POSITIONAL EMBEDDINGS
The BERT model uses three types of embeddings: token, segment, and positional embeddings. The latter is canonically implemented as bias add operation, rather than full embedding look-up. This is possible because the positional indices increase linearly for every sequence. However, when using the packed data format the position index needs to be reset with each new packed sequence. For instance, when packing two sequences one of length and one of length 3, the positional embedding indexes that need be picked up are j0, 1, 2]. To achieve this, the bias add needs to be replaced by an embedding look-up to 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 required adjustment has only minor impact on absolute accuracy/loss (see Section 4.2 and 4.2.
3.2.2 ADJUST ATTENTION MASKING
Input
mask = (p.array((11, 1, 1, 2, 211) 0, nask
Upgao pack digh
LSWAACO
vero_pne_nask LL.eeuual (iwak, mask.T) for use aоttnax:
softnax_nack zf.whoral swea_orw_maak, 0, 2000)
Figure 2: Attention mask code [left], respective zero-one mask [middle], and vectorized unpacking of the sequence loss[right]. White rectangles correspond to padding.
4

---

Under review as a conference paper at ICLR 2023
To maintain an implementation that is consistent with the un-packed version, tokens from different sequences within a pack should not be 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 attention per-sequence (5). Instead, we propose directly masking the attention matrix with a block-diagonal mask before the attention softmax. This is straightforward frameworks (see Figure 2). Naturally, there is a cost to both the mask construction and applying it the attention matrix. However, is required to keep the accuracy (see Table [ Section 4.1 See also the code of the deprecated tensor2tensor library and our own provided code.
implement in modern
Section 4.2
3.2.3 ADJUST PER-SEQUENCE LOSS AND ACCURACY
Canonical implementations of BERT compute the cross-entropy loss for the masked language model on a 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 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-sequence averaging behavior of the canonical un-packed BERT implementation, we 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. However, rather than looping through the sequences index, we compute on all indexes in parallel (see Figure This minimizes the latency overhead of un-packing the loss calculation. As an example, we show how per-sequence loss can be implemented for the pre-training task. We use the "masked Im weight" 7 input tensor to represent which sequence a given masked token belongs to (0, 1, 2 and so on). This is consistent with the canonical BERT implementation where this input takes a value of either I (belonging to the sequence) or 0 (belonging to padding). The full methodology is detailed in Listing and can be applied to other classification or pre-training tasks.
3.3 ADJUST HYPERPARAMETERS
In terms of convergence behavior, the primary consequence of packing is an increase in the effective batch size (with respect to number of sequences and real tokens) with some added variation over different iterations. If we look on the sentence level, the number of sentences in one batch increases by the packing factor. Similarly, the number of tokens in one batch increases. Hence, hyperparameters that are sensitive to these numbers need to be adjusted.
direct solution is to reduce the computational batch size by the packing factor (average number of sequences per pack) and keep all other hy pyprparrametess the same. For example, if the packing factor cutting the gradient accumulation count by half is sufficient. The advantage of this strategy is that no fine-tuning of hyperparameters is required and performance curves are comparable. However, this approach might be not desirable as might imply under-utilizing the memory/compute, especially the micro batch size needs to be reduced.
Hence to preserve batch size and optimize hardware utilization, we additionally propose an approxi- mate heuristic for updating the decay parameters of the LAMB optimizer (34) For packed dataset with a packing factor p. we update the decay parameters as: 31 := 8r. B2 := S For p = 2, this corresponds to the exact parameters for calculating momentum and velocity, when updating with the same gradient twice (Section D). A common approach is to scale the learning rate with the batch size. However, 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.
5

---

Under review as a conference paper at ICLR 2023
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-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 a general understanding on how the packing depth influences the processing time. For NNLSHP, we focus on packing depth because it packs the data sufficiently well. For the speed-up analysis, we focus on the intelligence processing unit (IPU) (L1) (IPU-M2000, 16 accelerator chips), BERT phase 2 pretraining setup as in Section 4.2 A GPU dynamically loads the code into the accelerator; in contrast, the IPU works with a 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 especially benefit from our approach since it avoids code changes. Nevertheless, it can be applied to any implementation
GPU or TPU. For determining the speed-up, precompiled kernel. Since time measurements are quite noisy, we can profile the kernel and how many cycles takes for processing a batch. That way, 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.
take advantage of the
Table I: Key performance results of proposed packing algorithms (SPFHP and NNLSHP) on IPU.
pack. depth
packing
EFF
p
OH
realized
algorithm
(%)
(%)
speed-up
NONE
50.0
1.00
0.000
1.000
SORT
99.9
2.00
>> 100
<1.000
R 10
GREEDY
778
11.6
44.48
11.
SPFHP
80.5
1.61
4.283
1.544
SPFHP
89.4
1.79
4.287
1.716
NNLSHP
99.7
2.00
4.287
1.913
4
SPFHP 93.9
1.88
4.294
1,803
SPFHP 98.9
1.98
4.481
1.895
max
SPFHP 99.6
1.99
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 se- quences as they arrive until they would exceed 512 tokens. Setting no limit resulted in a maximum packing depth of 16. EFFiciency is the percentage of real tokens in the packed dataset. The packing factor describes the resulting potential speed-up compared to packing depth 1. With overhead (OH), we denote the percentage decrease in throughput due to changes to the model to enable packing (such as the masking scheme introduced in Scction 3.2.2). The realized speed-up is the combination of the speed-up due to packing (the packing factor) and the decrease in throughput due to the overhead on the IPU. It is used to measure the relative speed-up in throughput and the overhead from masking and loss adjustment. SORT can be only efficient on GPUs (see Section 4.4)
The main results for the performance metric evaluation are displayed in Table I The processing time for SPFHP on an Intel(R) Xeon(R) Gold 6138 CPU with 2.00GHz, 80 nodes, and 472G RAM was around 0.03s and independent from the packing depth. Classical First-Fit-Decreasing requires 87-s lot of memory, and scales almost linear with the number of samples. We see that the overhead slightly increases with packing depth but that the benefits of packing outweigh the cost. The best speed-up up is obtained with NNLSHP at depth 3 which required 28.4s on the CPU for processing and ran out of memory for larger depth. With 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 process sample (a pack of sequences) is barely changed

---

Under review as a conference paper at ICLR 2023
relative the un-packed implementation. The packing factor, or the improvement in efficiency, effectively provide an accurate estimate of the speed-up. GREEDY packing as used in T5 shows to be quite inefficient and sorted batching (SORT) is highly efficient in avoiding padding but the resulting different computational graphs cause a major overhead on the IPU that exceeds the benefits of avoiding the padding. Since we made our algorithm and code public available, results have been reproduced with a different framework on the Habana Gaudi accelerator (10) and confirmed that our approach is hardware and software independent giving it huge advantage over existing approaches.
4.2 MLPPERTM PHASE 2 PRETRAINING SETUP: LEARNING CURVES AND HYPERPARAMETER ADJUSTMENT
For depth I (classic BERT) and NNLSHP with depth 3. we additionally evaluate on the MLPerfTT ver- sion 0.7 BERT pre-training benchmark (17). Briefly, this involves training from a standard checkpoint masked-language model accuracy of 71.2% using 3 million sequences with a maximum length of 512 tokens (refer to (19) 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 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 (R 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 a first comparison, use the same hyperparameters when comparing packed and unpacked training except for cutting the accumulation count by half. This way, we make sure that the batch size is constant on average and we have the same amount of training steps. 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, we compare two optimized setups. In these two cases, packing takes half the amount of training steps.
The learning curves are displayed in Figure 3 In the first setup. we see the curves almost matching perfectly when normalizing by the numbers of samples processed. Differences can be explained by the variation of the number of sequences in the packing batch, and general noise in the training process. Especially after the initial phase, the curves show near-identical match. The second setup shows bigger differences since changing the batch size and hyperparameters changes the training dynamics. We observe slower convergence early on in training due to the increased batch size. This is expected. The adjustment of the learning rate actually decreases performance probably because we correct for the increased number of sequences already in the modified loss. With the adjustment of the decay parameter of LAMB, we see matching performance at the later training stages. However, it is not feasible completely recover the early convergence behavior of the smaller batch size by adjusting the hyperparameters. For instance doubling the batch size of unpacked BERT to 3000 and adjusting the LAMB decay parameters leads to more of a slow down in convergence than when running packed BERT with a batch size of 1500 and a packing factor of 2. n practice, our implementations exceeds the estimated 1.913 maximum speed-up. This estimate 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 to the device. Figure 3 shows that the realized total speed-up from packing exceeds 2x.
4.2.1 ABLATION STUDY
So far, we have shown that with the introduced adjustments, we can match the accuracy of unpacked BERT. In the following, we analyze in how far the masking adjustment is required. In Figure 4 we can see 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 12.1%. So overall, both adjustments crucial to avoid reduction in performance.
7

---

Under review as a conference paper at ICLR 2023
3.5
dassi,
packed, ebs: 769*2, beta: 0.81
classic beta: 0.81
packed, beta: 0.66
3.5
classic, bi: 3000, beta: 0.66
classic,
3.0
0.66, double
packed, dec 1500"2, beta: 0.66
parkedd betar 0.81, double
2.5
2.5
2.0
1.5
1.5
1.0 relative
3.5
2.0
samples
samplees
Figure 3: Comparison of learning curves for packed and unpacked processing, where all experiments converged to the target aceuracy 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). Further learning curves are provided Section 0
training accuracy (percent)
70
10
no mask adjustment
packed BERT baseline pos. emb. adjustment
less
x 10
no mask adjustment
2x
packed BERT no pos. emb. adjustment
50
1500
Rteraion
Iteration
Figure 4: 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%.
When running packed BERT without the NSP loss but keeping everything else the same in full training setup, we observed that downstream performance on SQuAD reduced the FI measure by 1.31% % and EM by 1.15%. Hence, do not consider removing NSP done in approaches like RoBERTa and T5 as discussed in Section
4.3 FULL PRETRAINING AND SQUAD FINETUNING
Packing slightly violates the i..dd assumption of data. Thus, we have to check that downstream performance is not impacted by packing. This is especially relevant in a full training setup without a starting checkpoint. To this aim, we show that the packed and unpacked SQuAD 1.1 scores are comparable after full-pretraining of BERT base and large plus fine-tuning. During pre-training, in order to avoid giving an advantage to packing by further hyperparameter tuning, we reduce the gradient accumulation count for the packed BERT training for phase and phase 2 to match, on average, the total number of sequences that get processed before each weight update. With this approach, can use the same hyperparameters and number of training steps but process each batch faster by avoiding the processing of padding. This gives a slight disadvantage to the packed run in terms of machine utilization, as explained in Section 3.3 and is different to the speedup analysis in Section 4.2 For Phase 2, we use sequence length 384 since longer range attention is not relevant for SQuAD 1.1. The respective speed-ups from packing for BERT base and large are shown in Table 2 the realized speed-up, measured as the quotient of the throughputs between the packed and unpacked runs, is slightly lower to the theoretical throughput (i.e. the packing factor) due to the packing overhead. Further learning curves with the loss function and accuracy are provided in Section P. For the fine-tuning training on SQuAD 1.1, we do not use packing. The scores, computed as the median of 10 different seeds, displayed in Table 3 They comparable to the reference ones in (6): for BERT base (resp. large) the Fl score is reduced by 0.2% (resp. 0.3%) and the EM score increases by 0.3% (resp. 0.02%).
8

---

Under review as a conference paper at ICLR 2023
Table 2: Measured speed-ups in BERT
Table 3: SQuAD 1.1 scores after BERT pretrain-
pretraining with packing.
ing with packing.
Model Sequence
Packing factor
Realized speed-up
Model Configuration
F1
Exact
size
length
size
match
base 128
1.17
1.15
(6)
88.5
80.8
base
384
1.70
1.68
Packed
88.32
81.03
128
1.17
1.15
(6)
90.9
84.1
large
large
384
1.70
1.69
Packed
90.65
84.12
4.4 SCALING ANALYSIS: IMPACT OF ACCELERATORS COUNT
A further ad advantage of packing competing un un-padding approaches is the inherent load balancing provided by packing. So called un un-padding approaches rely on dynamically launching custom kernels that ignore padding. A stated advantage of such implementations is the ability avoid computing the complete (512 x 512) attention matrix. This provides additional computational savings compared packing, where the attention matrix is computed in its entirety and then masked. Because of these additional savings, un-padding can exceed the theoretical upper bound for speed-up from packing (2.013 on Wikipedia). As result of the dynamic nature the approach, the processing time with un- un-padding is different for each sequence in the batch, and the amount of time required to process a batch of sequences will be determined by the processing time of the longest sequence in the batch (with the sequences being processed in parallel). Furthermore, in the multiple accelerator setting the processing time on each device will vary depending on the sequences in the batch that receives. Devices which finish early have to wait for the slowest device finish before exchanging gradients. This load-imbalance between the devices (and inside the batch) leads to a considerable decrease in the speed-up from un-padding the number of accelerators is increased (see Figure 5 and Section (I). In contrast, packing (our approach) is inherently load- boad-balanced The processing time each accelerator is independent of the content inside the batch received by the device. Any number of accelerators can therefore operate in unison without having to wait for the slowest batch to process (all per-device batches equally fast).
9
1.600
1.400
theoretical upper bound
1.300
packing approach)
1.200
un-padding (Pffective Transfomeer
1.000
padding (common baseline)
1.000
1
4
16
32
64
128 256 512 1024 2048
number of accelerators
Figure 5: Comparison of the theoretical speed-up the number of accelerators is increased.
5 CONCLUSION
Whereas packing is a well known concept, this paper sheds a new light onto it in multiple aspects. First, visualize the sequence length distributions of multiple datasets not just from language domains but also audio and molecular domains to emphasize that packing is beneficial for varied datasets, leading to more than 2x acceleration by removing 50% or more padding. Second, we provide two new highly efficient packing approaches based on established solvers that leave almost no padding and that can tackle arbitrarily large datasets matter of seconds, in contrast to existing approaches that are slow and suboptimal. Third, we demonstrate that without adjusting the sequence processing algorithm (c.g., BERT) to the packed sequences, predictive performance is reduced. Thus, propose several model adjustments that are all necessary to keep predictive performance. Last but not least, we prove that, thanks to such adjustments, predictive performance is preserved as no packing was used but speed significantly increases, especially since the adjustments come with an overhead of less than 5%. We prove in our experiments that downstream performance is not impacted by packing and that the anticipated 2x acceleration can be achieved.

---

Under review as a conference paper at ICLR 2023
REFERENCES
[1] ANONYMOUS. Supplemental Material for "Efficient Sequence Packing without Cross-contamination:: Accelerating Large Language Models without Impacting Performance', 2022.
[2] BOTTOU, L., CURTIS, F. E., AND NOCEDAL, J. Optimization Methods for Large-Scale Machine Learning. SIAM Review 60, 2 (jan 2018), 223-311.
[3] BRO, R.,. AND DE JONG, S. fast non-negaatiittycoonttin least squares algorithm. Journal of Chemometries 11, (sep 1997). 393 401.
[4] BROWN, T. B., MANN, B., RYDER, N., SUBBIAH, M., KAPLAN, J., DHARIWAL, P., NEELAKANTAN,
A., SHYAM, P., SASTRY, G., ASKELL, A., AGARWAL, S.. HERBERT- A., KRUEGER, G.,
HENIGHAN, T., CHILD, R., RAMESH, A., ZIEGLER, D. M., WU, J., WINTER, C., HESSE, C., CHEN,
M., SIGLER, E., LITWIN, M., GRAY, S., CHESS, B., CLARK, J., BERNER, C.,, MCCANDLISH, S.,
RADFORD, A., SUTSKEVER, I., AND AMODEI, D. Language Models are Few-Shot Learners. Advancess in Neural Information Processing Systems 33 pre-proceedings (NeurlPS 2020) (may 2020).
[5] BYTEDANCE INC. Effective Transformer. htcps://getthbb..mm//yyataaaa
ive ive
transformer 2021.
DEVLIN, J., CHANG, M. W., LEE, K., AND TOUTANOVA. K. 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 I (oct 2019), 4171-4186.
[7] DEVLIN, J., CHANG, M. W., LEE, K., AND TOUTANOVA, K. BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding. http:////tiaab..ccooooogggg-gee http://////opppeeeeeeeeeeraee//a 2019.
[8] DEVLIN, J., CHANG, M. W. LEE, K., AND TOUTANOVA, K. ation script for BERT. https::/git.n create pretraining data pysta43 2019.
Pre-training data cre-
hamm/googlee resereeeeeerrrccbb/bbbbblbobl wttpbttt//bbbbbmttrr.bb..
[9] FEDUS, W., ZOPH, B., AND SHAZEER. N. Switch Transformers: Scaling Trillion Parameter Models with Simple and Efficient Sparsity. arXiv (jan 2021).
[10] INTEL, 2021.
[11] JIA, Z., TILLMAN, B., MAGGIONI, M., AND SCARPAZZA, D. P. Dissecting the Graphcore IPU architecture via microbenchmarking. ArXiv abs/1912.03413 (2019).
[12] JOHNSON, D. S. Near-optimal bin packing algoritluns. PhD thesis, Massachusetts Institute of Technology, 1973.
[13] JOHNSON, D. S., AND GAREY, M. A 7160 theorem bin packing. Journal of Complexity 1, (oct 1985), 65-106.
[14] KORTE, B., AND VYGEN, J. Combinatorial Optimization, vol. 21 of Algorithms and Combinatorics. Springer Berlin Heidelherg, Berlin, Heidelberg, 2012.
[15] LEE, C. C., AND LEE, D. T. Simple On-Line Bin-Packing Algorithm. Journal of the ACM (JACM) 32. (jul 1985), 562-572.
[16] LIU, Y., OтT, M., GOYAL, N., DU, J., JOSHI, M., CHEN, D., LEVY, O., LEWIS, M., ZETTLEMOYER,
L., AND STOYANOV, V. RoBERTa: A Robustly Optimized BERT Pretraining Approach. arXiv (jul 2019).
[17] MATTSON, P.. REDDI, V. J.. CHENG, C.. COLEMAN, C.. DIAMOS, G., KANTER, D., MICIKEVICIUS,
P., PATTERSON, D., SCHMUELLING, G., TANG, H., WEI, G., AND WU, C. ML.Prrf An Industry Standard Benchmark Suite for Machine Learning Performance. IEEE Micro 40, 2 (2020), 8-16.
[18] MENG. Q., CHEN, W., WANG, Y., MA. Z. M., AND LIU, Convergence analysis of distributed stochastic gradient descent with shuffling, Neurocomputing 337 (apr 2019), 46-57.
[19] MLCOMMONS. v0.7 Results. httts::/micconnee org http://etttaainnnnggeeeeeee www.iiggggooaao-oo noomal 2020. Result not verified by MI.Perf. Throughput/specdupp not the primary metric of PI.P MI Perf name and logo trademarks. See www. www.mlpprr... org for information.
10

---

Under review as a conference paper at ICLR 2023
[20] NVIDIA. Reference numbers for BERT un-padding results. https://githut www.luu...oom.ccoooo commons/
graining_resoltt__eee http//////mmmttreeeee/ee/ master /NWIII//NIIIIIIIE wttp::///e.etttttggg////aaaa /ttp:///ww..........ooooooo../..
06
rttorch/bert/resullee
txt, 2020. Throughput/ppecdup is not the primary metric of MLPerf.
MLPerf name and logo are trademarks. www.://wowwww..oooro..oo... for more information.
[21]
NVIDIA. Faster Transformer.
tree httm////eeerrtterraaassssssa httpss//eittnb..co////////////ee http://aaannnnnnaamammm.mmmmmm ngexamples
https::/giithb.
2021.
[22] OTT, M., EDUNOV, S., BAEVSKI, A., FAN, A., GROSS, S., NG. N., GRANGIER, D., AND AULI, M. fairseq: A fast, extensible toolkit for sequence modeling, In Proceedings of NAACL-HLT 2019: Demonstrations (2019).
[23] PANAYOTOV, V., CHEN, G., POVEY, D., AND KHUDANPUR, S. Librispeech: an aSt corpus based on public domain audio books. In Acoustics, Speech and Signal Processing (ICASSP), 2015 IEEE International Conference on (2015), IEEE, pp. 5206-5210.
[24] RAFFEL, C.,, SHAZEER, N., ROBERTS, A., LEE, K., NARANG, S., MATENA, M., ZHOU, Y., LI, W., LIU, J. Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer. Journal of Machine Learning Research 2/ (oct 2019).
[25] RAJPURKAR, P., ZHANG, J., LOPYREV, K., AND LIANG, SQuAD: 100,000+ questions for machine comprehension of text. In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing (Austin, Texas, Nov. 2016), Association for Computational I. Linguistics, pp. 2383-2392.
[26] RAMAKRISHNAN, R., DRAL, P. O., RUPP, M., AND VON LILIENFELD, O. A. Quantum chemistry structures and properties of 134 kilo molecules. Scientific Data I (2014).
[27] RUDDIGKEIT, I.., VAN DAURSEN, R., BL.M,, I.. C.,, AND REYMOND, J.-L., Enumeration of 166 billion organic small molecules in the chemical universe datahase gdh-17. Journal of Chemical Information and Modeling 52, 11 (2012), 2864-2875 PMID: 23088335.
[28] SHEN, J., NGUYEN, P., WU, Y., CHEN, Z., ET AL. Lingvo: a modular and scalable framework for sequencceto--sequence modeling, 2019.
[29] VASWANI, A., SHAZEER, N., PARMAR, N., USZKOREIT, J., JONES, L., GOMEZ, A. N., KAISER, U., AND POLOSUKHIN, I. Attention is all you need. In Proceedings of the 31st International Conference on Neural Information Processing Systems (Red Hook, NY, USA, 2017), NIPS' 17, Curran Associates Inc., p. 6000-6010.
[30] WANG, A., SINGH, A., MICHAEL, J., HILL,, F., LEVY, O., AND BOWMAN, GLUE: A multi-task benchmark and analysis platform for natural language understanding. Proceedings of the 2018 EMNLP Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP (Brussels, Belgium, Nov. 2018), Association for Computational Linguistics, pp. 353-355.
[31] WARSTADT, A.. SINGH, A., AND BOWMAN, S. R. Neural network acceptability judgments. arXiv preprint arXiv: 805. 105. 12477 (2018).
[32] WOLF, T., DEBUT, L., SANH, V., CHAUMOND, J., DELANGUE, C., MoL, A., CISTAC, P., RAULT, T., LOUF, R., FUNTOWICZ, M.. DAVISON, J., SHLEIFER, S., VON PLATEN, P., MA, C., JERNITE, Y., PLU, J., XU, C., SCAO, T. L., GUGGER, S., DRAME, M., LHOEST, Q. AND RUSH, A. M. Transformers: State- of-the-art natural language processing. In Proceedings of the 2020 Conference on Empirical Methods Natural Language Processing: System Demonstrations (Online, Oct. 2020), Association for Computational Linguistics, pp. 38-45.
[33] XLA, T. XLA: Optimizing Compiler for Machine 2021.
[34] You, Y., LI, J., REDDI, S., HSEU, J., KUMAR, S., ВНOΣANAPALIA, S., SONG, X., DEMMEL, J., KEUTZER, K., AND HSIEH, C.-J. Large Batch Optimization for Deep Leariing: Training BERT in 76 minutes. arXiv (apr 2019).
[35] YUE, M., AND ZHANG, L. A simple proof of the inequality MFFD(L) < 71/600PT(L) + for the MFFD bin-packing algorithm. Acta Mathematicae Applicatae Sinica 11,3 (jul 1995), 318-330.
11

---

Under review as a conference paper at ICLR 2023
Supplemental Material for "Efficient Sequence Packing without Cross- contamination: Accelerating Large Language Models without Impacting Performance"
TABLE OF CONTENTS
Introduction
2
Sequence length distributions
Methods
3.1
Packing algorithms
packedBERT: model changes
3.3
Adjust hyperparameters
5
Experiments
Bin packing algorithm comparison
MM.Perf phase 2 pretraining setup: learning curves and hyperparameter adjustment
Full pretraining and SQuAD finetuning
8
Scaling analysis: Impact of accelerators count
Conclusion
A Broader impact
14
Reproducibility Statement
14
Related work
15
D Theorem on LAMB hyperparameter correction heuristic
16
Un-padding scaling estimate
17
Technical background on packing
19
Canonical packing problem
19
F2
Approximate bin packing problem
19
Definitions
20
Non-negative least squares
.e..............................
20
Discussion of residual weight choice
23
Complexity analysis of the proposed packing approaches
24
G.1
Complexity Analysis of non-negative least-squares histogram-
24
Complexity Analysis of shoktest-pack-iiss histogram-packing
25
12

---

Under review as a conference paper at ICLR 2023
H
Performance Comparison to GREEDY Packing in T5
25
Impact of NSP loss
25
Wikipedia with Longer Sequence Length
27
Packing SQuAD 1.1
28
1. Packing GLUE
29
M Packing Audio Data (LibriSpeech)
30
Packing Paper Abstracts (PubMMdd)
MLPerf phase 2 learning curves
32
Full pretraining BERT base and large learning curves
33
Note on changing the sequence length for optimal packing
35
Fine-tuned longest-pack -fistt histogram-packing
35
S
Extended NNLS with padding token weighting
36
Implementation Challenges and Tricks
37
Packing Algorithms
37
Positional Encoding
37
Attention
37
Avoiding loss unpacking
37
Testing
37
1.6 Loss Balancing
38
Packing source code
40
13

---

Under review as a conference paper at ICLR 2023
A BROADER IMPACT
We showed that when pre-training BERT on Wikipedia, the computational overhead taken to process padding tokens is roughly 50%. By eliminating this wasted computational time, the approach presented in this paper paves a way to halving the carbon footprint of training BERT-based models.
Furthermore, our approach circumvents the need for custom kernels, making the benefits of packing readily accessible 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 on two assumptions: A skewed length distribution in the training dataset and a hardware setup that trains efficiently on a fixed batch size. If efficient training possible, with variable batch size approaches like rusterTransforer and the fairseq sorted batch approach will result in the same or even larger benefits (due to smaller self-attention matrices). If the dataset is generated differently like GPT models (4) and RoBERTa S (16), all sequences will be at full length and sequences cannot be concatenated and there is indeed no benefit in packing sequences. However, strategies that reach full sequence length usually combine segments from different unrelated document sources which result in reduced performance. Even in the normal BERT model, there might be this contamination between segments from different documents. Our paper introduced an approach avoid the contamination between sequences. However, the same approach could also be applied to avoid contamination between segments and it remains future work explore its benefits beyond BERT pretraining.
Future work would need to investigate the applicability of packing on text produced by different cultures and in different languages. We have already shown that the speed-up resulting from using our methods does not only occur when pre-training BERT on Wikipedia but also on other datasets such as SQuAD and GLUE Furthermore, the sentence length distribution of the original English language text shows similar characteristics. Our research leads us to believe that compressible distributions arise naturally in language tasks and beyond, for instance in DNA sequence lengths (39), protein lengths (38), and speech (Section MD. Many such sequence modelling workloads are based on variations of the /eaa/saanforr architecture and would therefore easily benefit from our acceleration.
Failures in NLP can have a big impact on society; many technologies, such as Alexa, Siri, and Google Home, rely them. Whilst any errors arising from our approach can be avoided, one potential source of error 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 required 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.
B REPRODUCIBILITY STATEMENT
All code for the packing algorithms is available in the appendix (Section Up and is directly linked to our GitHub page 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, our public submission to MLPerfTM could be used and we are preparing further code releases other frameworks. To encourage the use of the adjustments of models for packed sequences, we additionally provide detailed explanations and code snippets in TensorFlow.
Detailed mathematical formulas (Section B
and theorem proof (Section D). and complexity calculations (Section are provided this appendix to support our claims in the paper in full detail.
14

---

Under review as a conference paper at ICLR 2023
C RELATED WORK
The most obvious way to reduce the extent of padding in the dataset is to group samples by size before 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 training in this way, the wasted compute due to padding is approximately 20% (see Figure D. Other examples of this "sorted batching" approach can be found in Faster Transformer (2D, lingvo (28) fairseq (22). and RoBERTa (16), which group samples of similar size together in one batch and fill up with padding only to the maximum length 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 cireumventing the downsides. Firstly, sorting the data can reduce the overall convergence speed when the batch size is large because it violates the i..dd assumption the data distribution 18). Secondly, processing batches with shorter sequence lengths under-utilizes the compute compared to running the same batch size with longer sequence length. For GPUs, common heuristic to mitigate this effect is to adjust the batch size to keep the number of processed tokens near constant (2 16). 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, is 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 (33 9. which provides a R 7 acceleration for BERT in MLPerfTM (17) compared to the non-XLA baseline (33). Changing the sequence length or batch size requires re-optimization of the computational graph and recompilation of the program for the new tensor shapes. For complex models such as BERT, optimization and recompilation take a non nog-negligible amount of time. Even 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 is 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-padding" approaches. In Effective Transformer (5), the input batch is provided as a padded matrix but padding values are dynamically removed and restored during different calculation stages. While un-padding implementations are highly sophisticated and are able to completely cireumvent the processing of padding tokens, they introduce a significant overhead due to the multiple GPU kernel launches (i.e., one kernel per sequence rather than one kernel per batch). Additionally the time to process each batch will fluctuate depending on the sequence lengths in each batch, i.e., batches with only shorter sequences will typically be processed faster. When working with more than one accelerator, this variability in throughput results in all devices in the cluster waiting for the device with the most compute intensive batch to finish processing. As such, un un-padding approaches are not appropriate for deployment on large clusters. The "packing" based approach introduced in this paper offers significant advantages over un-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, packing SQuAD (25) or GLUE datasets 30) for BERT also leads to significant speed-ups (some in excess of 9x) (Sections K and D 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 (8. The use of bi-directional self-attention in BERT implies that the input sequences should contain complete sentences. If a sentence is abruptly cut short, the hidden state on other (preceding) tokens in the sequence will be affected. Language models with causal attention (only attending to previous tokens in the input) do not have this issue to the same degree. For such models, if a sequence is 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 attention. For instance, GPT-3 (4) is trained with maximum sequence
15

---

Under review as a conference paper at ICLR 2023
length of 2048 where single sequence may contain multiple segments of sentences separated by 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 computational efficiency GPT-3 does not mask the attention between different segments a sequence. In contrast, the packing approach presented in this paper introduces mask in the attention layer (see Section 3.2.2) to prevent coosscoontamination between examples in a 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 TS (24) use a similar packing approach as GPT-3, combining full sentences/sequeecess with GREEDY packing (first come first concatenate) and also separation tokens or additional padding. The RoBERTa ablation study shows that mixing of sentences from different documents reduces accuracy, but it is used nonetheless for load balancing reasons which indicates that sorted batching is not sufficient.
There might be hidden code snippets as in the deprecated [ensor2tensor library that seems to im- plement the same attention masking mechanism as we propose. However, these lack a sufficient documentation, testing, evaluation, ablation, and communication the research community to be considered state of the art in NLP research. More general, to the best of our knowledge and the knowledge of many other engineers and researchers that were in contact with, there is other research work that focuses on packing in NI.P
D THEOREM ON LAMB HYPERPARAMETER CORRECTION HEURISTIC
With packing, the effective batch size changes and hence hyperparameters the LAMB optimizer (34 need to be adjusted. For packed dataset with packing factor p. we update the decay parameters as: 31 : Sr. B2 == 3% For instance if 31 = 0.81 for the un-packed dataset, then for a packed dataset with an average of 2 sequences per sample one should use value of 0.81 0.66 instead. Assuming no or only minor changes in gradients and p being natural number, we can prove that this heuristic the exact solution to make sure that momentum and velocity in LAMB are unaffected by packing. This can be proven by mathematical induction. Note that 2 1 by definition.
Theorem D.1. For any p N and assuming that respective gradients on batch of random samples are (approximately) the same, choosing
B = 3r
B2 = 3.
(2)
as hyperparameters 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 X b samples.
Proof.
Base Case:
For p 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 to some k, h 1 1.
Inductive proposition: The theorem holds for p=
Proof of the inductive step: Let be the loss function, w, the weight vector after / updates, and =f!- ,./ the respective underlying data to calculate the gradient gr. For single update step in LAMB with batch size b samples, we compute the gradient
al
9t
Ow (z) (x), w²).
(3)
Since 91 Rd 92 R LAMB:
= gk+1, We have with the inductive hypothesis and the definitions in
my B mo + (1 - 18/)91
(4)
22 33 + (1 35009
(5)
16

---

Under review as a conference paper at ICLR 2023
Now we calculate (with 91 [k+1)
mk+1 = 3im + (1 - 31)gx+1
(6)
= 31 (5 mo + (1 - (1)))))1) + + -11911
(7)
+ +mo
mo +(1 (1- -
(8)
The calculation for Ug the same. As reference for packed update with p = k with 3 and B2, we would get
(1) wn
p p
1
Öl Sw
(x)) w-)
-
91 91
(9)
pb
dw
since calculating gradients over b samples which assumed to be approximately the same. Consequently, the updates for momentum and velocity would be
my = mm + -1-31)
(10)
Tk 3200 + (1 32)
(11)
Hence, 31 = and 32 - is required to map to the formula with the consecutive updates (for the same amount of data).
Conclusion: The theorem holds for any E N.
Since we proved that the formulas 81 : =33. Ag = 88. hold for all p E N. p 2 1, is safe to assume that it is an appropriate heuristic for all p E R, p 2 1.
E UN-PADDING SCALING ESTIMATE
To demonstrate the severity of the load-imbalance issue in Section 4.4 we consider the scaling of an un-padding approach with per-device batch size of 32 running on eight devices (20). From there, we readily extrapolate the performance both larger and smaller cluster sizes by fitting Gumbel distribution to the observed processing times described in this section. On a 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 more, the proposed packing approach outperforms the dynamic un-padding approach. On a cluster with 32 accelerators the speed-up from un mn--adddin drops to 50% and with 2048 devices the speed-up is only 30%. In contrast, the speed-up due to packing independent of the number of accelerators and stays at 1.913. Switching to a smaller batch size would reduce the load-imbalance issue to some extent, but would also result in under-utilization of the available memory and compute.
Firstly, retrieve the per-batch processing time for un-padding implementation running pre- training on the Wikipedia dataset from (20). 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 (43) and use that as the baseline to compare the un-padded throughput against.
The throughput on the 8 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 fixed size collection of i.i.d. samples (in this case batches). We observe that on GPUs the throughput (i.e. speed-up) distribution indeed closely resembles a Gumbel distribution with 0 1.6 and Bg 0.13 shown in Figure 6
We can extrapolate the performance on the 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 8 GPU system, and record the max of the as the processing time for 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 large systems. We mitigate the effect of outliers in the data
17

---

Under review as a conference paper at ICLR 2023
8 GPUs with (bs=32 32 each)
GPU with bs=32
1.2
3.0
fitted Gumbel
Estimate
data
1.0
probability density
2.5
0.8
2.0
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
3
speed-up from un-padding
speed-up from un-padding
Figure 6: Left: Speed-up from un-padding on 8 GPUs closely resembles Gumbel distribution. Right: statistical estimate of speed-up distribution on a GPU system running un un-padding
by avoiding directly sampling the processing times. Instead, we fit Gumbel distribution to the processing times of single batch of size 32 running on one GPU. To perform the fit, we observe that the cdf on one GPU (P1) related to the edf on GPUs (Ps) through (section 1.3):
(1-))(s)) (1 Ps))
(12)
In other words, if the speed-up on the cluster is larger than s, this implies that the speed-up on every GPUs in the cluster was at least 8. Assuming P1 Gumbel and given the GPU Gumbel parameters and 08. we need to fit two parameters, O1 and $1. Consequently for the median (s = ag - 3g (l)),,)), (s(s) = 0.5), we have:
0.5 = (1 (i 3 ln(n()))))
(13)
And since P3 Gumbel, we also have an equation for the mode (s agg Ps(s) c-1);
(1 - = - Pas)))
(14)
We solve these two non-linear equations simultaneously using the standard SeiPy optimization package.
Listing Infer Gumble distribution parameters.
Sngort narpy d
From scipy import stats, opt imize
alphi_ 1.5038
beta 8 0.3288
g(x):
a1pha_1, beta_]
cist stats. 1 r Iloco=alpha 11, aceilebbeta_]
Rquatiion for nedian and mode
median sipas_8
equation! 3.5 distt.sf (median) ant gpu
mode elpha_8
equation2 C-appexp lequstion iguation22421
dist. (mode) exp_
res aptimize.miiimi.ee ig. [nipha_8, beta_81,
alghe beta
The resulting estimated speed-up Gumbel distribution for single device has 1.94, 8 0.108 and is shown in Figure 6 [right]. To simulate the performance of a cluster of size n with a batch size of 32 per device, take the minimum over 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 it is not clear how much of the computation is done in parallel and how much in serial.
18

---

Under review as a conference paper at ICLR 2023
F TECHNICAL BACKGROUND ON PACKING
F.1 CANONICAL PACKING PROBLEM
The bin packing problem deals with the assignment of items into bins of a fixed capacity such that the number of utilized bins is minimized. In the canonical formulation of the packing problem a vector s(i) of length sequencefitem. The allocation of items into bins is tracked through the assignment matrix B, where By E {0, 1} states whether the i-th sequence should be placed into the j-th bin. the worst case scenario, every item is assigned to its own bin, thus B Rox" 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 Mj 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 as bin packing (14).
used to represent the items being packed, where s(i) denotes the length of the i-th
n
min (E(0.1)".BE
Σ
Vj
Minimize the number of bins.
j=1
s.t.
bij =1 1 Vi
Assign each length/sequence to only one bin.
j=1
(i)bbe S 8m1li
Vj
Cumulative length cannot exceed capacity,
(15)
Bin packing is a strongly NP-complete (14 problem. Producing exact and optimal solution is possible with a variety of existing algorithms, for example with the algorithm (36). However, given that we want apply it for very large n (16M for the Wikipedia dataset) an approximate approach is required.
F.2 APPROXIMATE BIN PACKING PROBLEM
Approximate packing approaches are divided into online and offline algorithms (12). Online algo- rithms process incoming sequences one-by-one a streaming fashion, whereas offline algorithms have holistic view of all samples to be packed but typically still operate on per sample basis. This results in 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 (12). 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 closed because the incoming sequence did not fit. More specifically, this approach not able 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 algo- rithm (15), which creates harmonic sized bins for the assignment decision, and the offline Modified First Fit Decreasing method [33 35), which sorts the data, groups it into size categories and defines strategy adjusted to these sizes.
In our approaches, we make three major simplifications. We make the problem of bin packing less dependent n by operating on the histogram of sequence lengths with bin size 1. Hence, replace s(i) by its histogram and the bin assignment y, B by a mixture strategies x, where the set of all available packing strategies is modeled as the matrix A (see also Section F.4.2).
Then, we do not solve the full packing problem but focus on fixed packing depth (in other words the well known 3-partition problem). Last but not least, we solve the limited depth packing problem only approximately either with a nonnnegativity-constteae constrained linear least squares (3) (NNLS) followed by rounding nearest integer solution or by applying Worst-Fit (13 35) the histogram, sorted
19

---

Under review as a conference paper at ICLR 2023
from largest to smallest (in contrast to using unsorted dataset). An exact solution would not be appropriate, since the 3-partition problem is strongly NP-complete (37) as well.
F.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 a limit on 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 pack to always add up exactly to the bin capacity 8m (we can always generate a padding sequence of just the right length to fill-up the bin). A packing strategy total sequence length is no more than 8m and the number of sequences in the pack does not exceed the maximum packing depth. The output of a packing scheme 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 a 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 sm 512 the strategy [2. 508] has an implicit padding of (needed to fill the pack up to the sm). Alternatively, the strategy repeat count may over-subscribe a particular sequence length leading to explicit packing. For instance constructing 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.
sorted list of sequence lengths, for example [5, 7, 500], such that the
F.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 is deterministic and has three
major components described in Sections F4. F.4.2 and F.4.3
F.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 on the Wikipedia dataset. Increasing the depth to 4, increases the size of the packing problem drastically and yields no throughput benefit P With only two sequences, packing would be not as 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 1 - 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 as the space of potential solutions by a factor of 6 approximately and thus significantly accelerates 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 //6 (for example, or any other distribution). This would conflict with integer rounding of the solutions and with convergence of optimization algorithms.
F.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 are using a granularity of 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 represents packing strategy. For instance, the first column represents the strategy [1, 6] of packing two length-1 sequences and one length-6 sequence together to form a pack of length 8. The
Forr data distributions that are more skewed than Wikipedia this might look different.
20

---

Under review as a conference paper at ICLR 2023
number of strategies (and columns in the matrix) is discussed in Section G
For a packing depth
of 3 and maximum sequence length, we obtain around si +6xm +12 strategies. For depth 4, around
12
(5m (2) more get added.
288
Table 4: Example packing matrix for sequence length 8. 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
1
0
0
2
0
0
0
0
0
0
0
0
0
0
2
0
0
1
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
F.4.3 SOLUTION OF THE NNLS APPROXIMATE PACKING PROBLEM
solution of the packing problem is the mixture of packing strategies x 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 F.4.4
min *ER
||4 x bl|2
(16)
s.t. x 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 A o is close possible (in the least squares sense) to the histogram of sequence lengths We obtain solution with non-negative least squares implemen- tation (41 (45) Interestingly in the case of sequence length 512 only 634 out of the 22102 available packing strategies of depth to 3 are used (3%).
F.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:
r b round(x))
(17)
The negative portion of the residuals represents sequences that we are "short". That is, there is deficit of those sequences and we are over-subscribing to them. The positive portion of the residuals represents sequences which have failed to be packed. Typically, there deficit of short sequences and surplus of long sequences demonstrated by the following plot.
In total, there are n 162279'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 I to are [-4620, -4553, 46122 4614, 37233 -3936, 36288 -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.9410 tokens of padding. In contrast large sequence lengths have a positive residual (a surplus of unused sequences). For sequence lengths 504 512 the values are [3628, 3936, 3724, 4613, 4612, 4553, 4619, 0). Note that sequence length 512 has a residual 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
F.4.5 RESIDUAL WEIGHTING
natural extension of the non non-negative least squares problem introduced Section F4.3 is to weight the residuals on different sequence length differently.
21

---

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

---

Under review as a conference paper at ICLR 2023
F.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 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 a reduced "weight". The other residual weights stay at 1.
To start, we chose an offset of tokens, which is the smallest power of for which there are examples in the Wikipedia dataset. We decrease the weight sequences shorter than the "offset" from to 0.9 to 0.09 to see which order of magnitude is the most appropriate. On visual inspection (looking at the residual plots in Figure 8 found that 0.9 still left too many long sequences unpacked. So, 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. 99.746359% efficiency, whereas the weighted approach results in 99. 746274% efficiency. Hence, we conclude that the impact of the weights on the packing efficiency is very limited. Additionally, using an "offset" length of 4, resulted in similar numbers, for the full range of weights from 0 1. Using a weight of 0 for an "offset" length of 8 resulted insignificantly higher efficiency of 99. 95195,, whereas using an "offset" length of 16 reduces performance to 99. 99.38964%. weight of implies that the residual on those lengths can be safely ignored, i.e., the packing algorithm can thus add many short sequences as it chooses without any penalty, It is very interesting that this does not significantly impact the packing efficiency, and can even 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% at length 16.
For our Squad analysis, weighting improved the efficiency slightly from 96.94% to 97.38 97.38%. Fine tuning further with direction grid search, delivered 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 to achieve secondary targets (like not having leftover long sequences) without significantly compromising the packing efficiency.
23

---

Under review as a conference paper at ICLR 2023
G COMPLEXITY ANALYSIS OF THE PROPOSED PACKING APPROACHES
Since approximate packing algorithms have a complexity of least to be able to tackle datasets with 2K million samples, we will discuss the complexity of our packing algorithms in this section. The complexity depends on the maximum sequence length 8ms the number of samples and the packing depth d.
and we would like
To create the histogram, we have to iterate over the data once (O(n)). Our histograms will be binned by size 1, meaning one bin for each sequence length. Hence, dictionary can be generated (0(sm) and used for the sorting (0(1)). The respective histogram vector has dimension 8m.
G.1 COMPLEXITY ANALYSIS OF NON-NEGATIVE LEAST- HISTOGRAM-PACKING
For a packing depth of one, there is only the strategy [sm]] For a packing depth of two, we add the strategies [m, 8m 1], .... (mm - - ]] which results an additional 8m 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
8m
3
8m
8mm 33 / 33+1
8m
(19)
2
2
3
2
12
Note that for 5m 512 the approximation is exact. This means that strategy matrix A has the dimensions 8m x
1ay J+1. Overall, this leaves us with a space complexity of 8% since A is larger than w. I. and So 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. We now have only
12
+ L free variables the strategy vector
12
T. Also note that A can be precomputed when 9m is known and is independent of the number of samples. Given a problem matrix with dimension i x j. Luo et al. (22) indicate that the asymptotic complexity of most solution approaches is Oii)²). ). whereas they propose an O(ij) solution. Since we use the standard SciPy implementation (41). our estimated total time complexity for NNLSHP is
Onn + ).
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 (7)
fm
Fm
-1-k
2m
8m
k 3j
jmn
(20)
+ - 4k)(s 3 4k)
12
(2s + 9s +4)
288
1
s(s + (2s + 1)
288
24

---

Under review as a conference paper at ICLR 2023
So with Sm 512, there would be around 940K strategies. In our 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 to only consider 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.
numbers for the sequence length and
G.2 COMPLEXITY ANALYSIS OF SHORTEST-PACK FIRST HISTOGRAM SAAOOGRR--PACKINGG
The complexity calculation of SPFHP straightforward. We go over the whole data once for the histogram sorting. Next, we iterate over each of the Sm bins in the histogram. Lastly, we iterate over all strategies that were encountered far. can be proven that, at 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 a new strategy or we split one of the existing strategies into two. Hence, the number of strategies is bounded by 8m and the overall time complexity bounded by On + s² The space complexity is (s since we need to store up to s. strategies with maximum 8m counts for different sequence length.
H PERFORMANCE COMPARISON TO GREEDY PACKING IN T5
T5 (24) is normally trained on the C4 dataset. However, give an 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 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 of 512 is 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 10 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 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 tensor2tensor [link] two separator tokens would be expected in the T5 processing.
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 of sequences from different documents can consistently improve downstream Fl scores by 0.35%.
I IMPACT OF NSP LOSS
When running packed BERT base without the NSP loss but keeping everything else the same, we observed that downstream performance on SQuAD reduced the Fl measure by 1.31% and EM by 1.15%.
For the packing in approaches like RoBERTa or T5, it is crucial that there is no NSP loss because that would circumvent putting arbitrary sequences together in contrast to our approach that can handle multiple sequences from different documents without cross- conss-contamintiion. Liu et al. (16) argument that NSP can be omitted because "removing the NSP loss matches or slightly improves downstream task performance". In their experiments, they compare the normal BERT setup with NSP ""SEGMENT-PAIR") to the "POC-SENTENCES" approach, where there is no NSP and data in one sequence comes only from one document. For the "SEGMENT-PAIR" approach, the paper does not address, how much padding tokens are still present. Assuming, is around 40%, their correction in batch sizes for each step would result in a significant increase in training steps for the "DOC-SENTENCES" approach. It is well known that BERT performance increases with longer pretraining time. Our results indicate that NSP loss might be still relevant, depending the dataset
25

---

Under review as a conference paper at ICLR 2023
generation process. With our approach, get the acceleration benefits of T5 and RoBERTa while keeping the predictive performance by avoiding cross-contamination.
26

---

Under review as a conference paper at ICLR 2023
J WIKIPEDIA WITH LONGER SEQUENCE LENGTH
The histogram raw data for Wikipedia with different maximum sequence length is provided in Listing visualized Figure 9 sequences become more and more rare and the resulting benefits from packing drastically increase. Keeping in mind that the BERT dataset generation process decreases the size of maximum of 50% of the sequences, we can infer that having different dataset generator that truncates any short sequence, would result in significant loss of data (> 25% for length 512).
We can see that with increasing maximum sequence length, long
max. sequence length: theoretical max. speed-up: 1.210
max. sequence longth:
max. sequence longth theoretical max. speed-up: 2.001
theoretical max. speed-up: 1.742
0.005
50.8%
23.5%
probabiity dematy
0.004
0.004
0.003
0.003
0.003
0.002
0.002
0.002
0.001
25
50
75
100
125
100
200
500
400
100
200
300
400
500
sequence length
sequence length
sequence length
max sequence length:
max. sequence longth: 2048
theoretical max. speed-up: 2.984
theoretical max. speed-up: 3.920
10.8%
Breoreticcl man. Speed-up
probabiity donalty
0.004
0.003
3.5
0.003
3.0
0.002
2.5
0.001
2.0
1.5
0.000
0.000
200
400
600
8:0
1000
500
1000
1500
2000
128
384512
1024
2049
sequence length
sequence length
sequerce longth
Figure Sequence length distributions for different sequence lengths in Wikipedia BERT pre-training dataset and according theoretical speed-up.
Due the length distribution, it anymore sufficient concatenate only sequences obtain perfect packing for maximum sequence length 1024 or 2048. Instead, around 6 and 12 sequences are required. This cannot be solved by NNLSHP anymore due search space complexity but requires an online heuristics like SPFHP or the slightly better LPFHP, introduced in Section R that is based on Best-Fit and splitting counts in the histogram in contrast the rather simple First-Fit descending. Figure 10r shows the achieved speed-ups with LPFHP depending on the maximum number of allowed sequences.
max.
3.5
128
384
2.5
1024
2.0
1.0
6
1216
32
128
maximum number of sequences
Figure 10: Speed-ups achieved by LPFHP for different maximum sequence length and maximum number of packed sequences.
27

---

Under review as a conference paper at ICLR 2023
K PACKING SQUAD 1.1
We tokenized SQuAD 25 for BERT (6) with maximum sequence length 384 and visualized the histogram over the sequence length (Figure IT]. The distribution looks similar 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 we can see that SPFHP does not concatenate more than 3 samples and obtains 97. 97.54% efficiency in contrast to 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, NNLSHP is less efficient because the rounding in the residuals has much larger impact compared more than 16 million sequences in the Wikipedia dataset.
0.012
probability density
0.010
0.008
0.006
0.004
0.002
0.000
100
200
300
400
sequence length
Figure 11: SQuAD 1.1 BERT pre-training dataset sequence length histogram for maximum sequence length of 384.
Table 5: 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
I
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
SPFHP
344
40711
15633024
383545
97.547
2.177
28

---

Under review as a conference paper at ICLR 2023
L PACKING GLUE
To explore a variety datasets and emphasize that skewed distributions are common, we explored all datasets the GLUE benchmark (31 30) that came with training data. We loaded the datasets using the HuggingFace dataset loading API (6) For preprocessing, we followed the implementation in the HuggingFace transformers repository (32 and extracted the respective data processing snippets to obtain tokenized data with a maximum sequence length of 128. The histogram of the sequence length for each of the included datasets is displayed in Figure 12 and the packing results are given in Table Each dataser benefits from packing. The lower the mean, the higher the packing factors are that can be reached but with a higher packing depth.
cola
stsb
0.125
probability density
sst2
mnli
0.100
mrpc
rte
qqp
wnli
0.075
0.050
0.025
0.000
0
20
40
60
80
100
120
sequence length
Figure 12: GLUE dataset sequence length histograms for maximum sequence length of 128.
Table 6: Performance results of proposed packing algorithms for the GLUE dataset. Only the baseline
and the SPFHP packing results without limiting the packing depth are displayed.
data
packing depth
# strategies
# packs
# tokens
padding efficiency
packing
name
used
tokens
(%)
factor
cola
34
8551
1094528
997669
8.849
1,000
cola
13/max
29
913
116864
20005
82.882
9.366
sst2
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
mppc
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
rte
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
29

---

Under review as a conference paper at ICLR 2023
M PACKING AUDIO DATA (LIBRISPEECH)
In this section, we show that packing can benefit other domains than NLP like ASR. We use the LibiSpeech dataset (23) and preprocess as described reference implementation
@ The resulting histograms for the subsampled audio sample lengths and respective text labels are provided in Figure 13
probability density
0.008
0.006
0.004
0.002
0.000
50
100
150
200
250
300
sequence length
0.025
probability density
0.020
0.015
0.010
0.005
0.000
20
40
60
100
120
sequence length
Figure 13: 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% 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 the proposed packing algorithms to achieve 1 1.3r speed-up. This can be already achieved by combining up 2 sequences. To achieve almost perfect packing efficiency, sequence length around 457 and concatenating up to 8 sequences is required. Due 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 could be achieved with a speed-up of 2.24x.
30

---

Under review as a conference paper at ICLR 2023
N PACKING PAPER ABSTRACTS (PUBMED)
This section analyses the length of abstracts to give an intuition about how different documents can be in length. Figure 14 depicts the length of abstracts characters extracted from PubMed If these abstracts were directly used as sequences, a character length of 1000 could result in 1.9x speed-up from packing. The potential speed-ups for length 2000, 3000, 4000 would be 2x, 3x, and 4r, respectively. Note that, document clean-ur up procedures would usually eliminate documents that are 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 14: Abstract length distribution in PubMed.
Note that for the processing in BlueBERT (44), paper titles and abstracts get separated into sequences. tokenized, and then combined with the BERT sequence combination approach for a maximum sequence length of 128 tokens. Thus, it results in a different distribution.
31

---

Under review as a conference paper at ICLR 2023
O
MLPERFIM PHASE 2 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 15: 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
Figure 16: Comparison of learning curves for packed and unpacked processing with heuristics applied.
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 17: Comparison of learning curves for packed and unpacked processing in the optimized setup.
32

---

Under review as a conference paper at ICLR 2023
P
FULL PRETRAINING OF BERT BASE AND LARGE LEARNING CURVES
This section provides further learning curves related to Section 4.3
0.8
classic
5
training accuracy
packed
0.7
training loss
0.6
3
0.5
0.4
classic
2
packed
0.3
1
0
1
2
3
4
0
1
2
4
samples
1e8
samples
1e8
Figure 18:
Comparison of learning curves for BERT base phase 1 (sequence length 128) with packed and unpacked processing.
0.85
classic
2.0
packed
training accuracy
0.80
training loss
0.75
1.5
0.70
classic packed
1.0
0.65
0.0
0.5
1.0
0.0
0.5
1.0
samples
1e8
samples
1e8
Figure 19: Comparison learning curves for BERT base phase 2 (sequence length 384) with packed and unpacked processing.
33

---

Under review as a conference paper at ICLR 2023
classic
0.8
training accuracy
packed
training loss
4
0.6
3
0.4
2
classic
packed
1
0
1
2
3
4
0
1
2
4
samples
1e8
samples
1e8
Figure 20: Comparison of learning curves for BERT large phase 1 (sequence length 128) with packed and unpacked processing.
0.85
classic
2.0
training accuracy
packed
0.80
training loss
1.5
0.75
1.0
0.70
classic packed
0.65
0.0
0.5
1.0
0.0
0.5
1.0
samples
1e8
samples
1e8
Figure 21:
Comparison of learning curves for BERT large phase 2 (sequence length 384) with packed and unpacked processing.
34

---

Under review as a conference paper at ICLR 2023
Q NOTE ON CHANGING THE SEQUENCE LENGTH FOR OPTIMAL PACKING
An interesting aspect of packing that the maximum sequence length for packing could be larger than the maximum sequence length in the underlying dataset that gets packed.
For the QM9 dataset, this means that by setting the maximum sequence length to 36 instead of 27 an optimal 1.6r speed-up be easily achieved.
Note that the choice of maximum sequence length depends on the underlying machine learning algorithm. Due the squared computational and memory complexity of self-attention in BERT and other transformers, the maximum sequence length is usually kept as small as possible for these models. So an increase for packing alone is not practical. For algorithms with linear complexity as for example Graph Neural Networks, implemented in PyG, larger maximum sequence length can be chosen ensure, optimal packing is always possible.
R FINE-TUNED
PACSSSTT-PA---ISSSSSS HISTOGRAM-PACKING
In the main paper, we focused on SPEHP due its simplicity. this section, we analyse the effect of applying the "Best-Fit" algorithm (12). 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 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 Listing 8 and the results in Table 7
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 7: Performance results of longest-pack-firs histogram-packing for Wikipedia BERT pre-training with maximum sequence length 512.
We can see that longest-pack first Eetogram-packkingg (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 2 which is slightly higher than the 95%75% (1.996 packing factor) for NNLSHP and 99.6% for SPFHP (1.993 packing factor). All algorithms are very close to 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 are 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.
35

---

Under review as a conference paper at ICLR 2023
S
EXTENDED NNLS WITH PADDING TOKEN WEIGHTING
In Section R444 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 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) i padding tokens. This cannot be addressed by our weighting approach in
min FER
(lwA) - (wob]]
(22)
S.L. x 2
Working within the NNLS approach, we can strictly enforce non-positive residual (before rounding to integer). To that end, we define new auxiliary variable = -(b Ax) which is the negative of the residual, r. This will allow us to reformulate the objective r I the non-negative constraint: r 2 0.
min #ER"
(lwAA) (wbb]] + w. A. w w- F11
2 0
(23)
F F20
This will enforce = Ax - b 2 0 due to the large weight, w 10 and no upper limits on F. Now, we can set w; to optimize for the padding tokens. Due 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 L.2norm problem by an L1-norm problem which would be too complex to solve. Note that due to rounding, the unwanted positive residuals (F < might still occur. This could be avoided by rounding up ær instead of normal rounding of To put the new formulation into solver, replace
A 0m (A A -Dm)
by
x by
by
and A by
(24)
w
where Om is an m X m matrix with m being the maximum sequence length, 512, and Dm is a unit matrix the same dimensions as On- Since, we are already close to 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 in Listing 9
36

---

Under review as a conference paper at ICLR 2023
T IMPLEMENTATION CHALLENGES AND TRICKS
Whereas the model changes are described Section 3.2 getting them implemented in the most efficient way can require bit more effort. This section points few tricks that we used in our code.
T.I PACKING ALGORITHMS
Whereas the packing algorithm implementations might look trivial, they can become quite intricate. For example, when splitting and distributing bins like for example combining sequences of length 256 to a sequence of length 512, the number categories can drastically increase and thus the search space. Hence, it is valuable test each adjustment while changing the packing algorithms. If solution is not provided right away, the algorithm switched probably to a way less efficient complexity category.
T.2 POSITIONAL ENCODING
This approach was implemented as described in Section 3.2.1 by providing the index of the item with the data. Note that for any other part in BERT, the exact position does not matter. This allows to actually rearrange the data to our advantage. We can start with the up to 72 mask tokens and have an additional mask, that tell us, which tokens are the mask tokens, a list that provides their true labels, and with the positional encoding, we can determine their position in the sequence.
The NSP tokens get moved from the beginnings of their sequences to the end.
T.3 ATTENTION
For the attention mask, we realised creating them on host can have major cost in data transfer due to its size. Instead, one can create the mask on the accelerator. Therefore, we implemented custom operation using C++ and PopArt: /ttpp:://gitiie master/nlp. httpe///nnppbeetpporrr.eccc
http///aamppppeeeeeeeee wwtppppptpttpt..otttttet. wwweeeettniiinnssceeeeee cpp
cow/graphoore
Note that most cases, the attention mask gets not multiplied but added for efficiency, Hence, the "softmask mask" is used instead of the multiplication mask from Figure 2 in our implementation.
T.4 AVOIDING LOSS UNPACKING
Note that the MLM loss is applied on a token level and does not need any loss unpacking. However, for NSP, theoretically, the NSP tokens would be distributes within sequence. During dataset creation however, we arranged the tokens and moved all NSP tokens to the end. Due to our packing strategy, also know that those tokens are limited to maximum number of 3. This, can apply the NSP head to the potential positions and just provide a mask to filter out the relevant NSP tokens. This way, we need much less memory and compute for the unpacking for the NSP loss.
T.5 TESTING
The ultimate approach to test the correctness of the implementation is to check, if packed and unpacked sequence provide the same values and gradients. Due to large numeric variations, we implemented this test in FP32 for our Pororch Huggingface implementation This way, could prove that with the correct adjustments, unpacked sequences processed with vanilla BERT result in the exact same losses and weight updates as the packed sequences processed with the modified packed BERT version.
37

---

Under review as a conference paper at ICLR 2023
T.6 LOss BALANCING
This section addresses a challenge, called loss imbalance, that is usually faced with small batch sizes with different appearance when running packed compared vanilla BERT. It can also translate to other scenarios where losses get averaged with large amounts and variance of underlying padding in the data or variance in the underlying "scquencs/segmeen//oopoooo relevant since model sizes increase and already now, the microbatch size when running BERT large on the IPU is 3 and on the GPU for large scale training. a batch size of is used on a single GPU to limit the total batch size to 12960 aggregated over 4320 GPUs (
in a batch. This is highly
The main question is, how much /nfluence/weight in gradient update does a single MLM token and single NSP token get and how does this change with batch size, packing, or other factors that woule be expected to be invariants? Let us look into two extreme cases: batch size and a batch being the full dataset. Note that in the BERT model, we first take the mean over all MLM tokens and over all NSP tokens and then add the losses up.
For batch size of I, there are two extreme cases in the vanilla BERT setting. In case I, we have 1 MLM token and 1 NSP token. So each token gets a weight of in the final sum. In case 2, we have 76 MLM tokens and 1 NSP token. So each MLM token gets weight of 1/76 in the overall loss/gradien//eiihtt update and the NSP token, again gets a weight of 1. This means, the MLM tokens of short sequences get weight of 1 and it reduces linearly down 1/76 for maximum sequence. Thus, short sequences get more influence in the weight update and the ratio of weights compared to NSP changes, too, even though it is unclear how the ratio influences the final result.
Let us assume perfect packing efficiency for packed BERT. Hence, we have 76 MLM tokens and a weight of 1/76 for the MLM tokens in every case independent of the batch size. However, with maximum packing depth of 3, the number of NSP tokens can range between 1 and 3 and thus the weights can be 1/2, 1/3. This means that NSP loss for a sequence of length 512 gets times more weight than the NSP loss for a single sequence compared to packing 3 sequences for example of length 170 together. Again, the ratio between NSP and ML. changes, too.
Now lets look at the other extreme case of batch being the full dataset of size L (which behaves similar to the case of large batch size between 12k-1000K which is common). Again, for vanilla BERT, the NSP weight is I/L in any case. Assuming 50% padding, which can be common as previously shown, and again a maximum 76 MLM tokens per sequence, we get total of 0.5 L MLM tokens with the respective reciprocal value for the weight. There is no variation. 76 0.5 is the average number of MLM tokens per sample.
Assuming a packing factor of 2, the respective maximum batch size can only be L/2. This fits to scheme of reducing the batch size to avoid further adjustments of hyperparameters. For packed BERT, the number of MLM tokens is doubled compared to the average case in vanilla BERT and thus the weight is 1/676- 1.0 - (L/2)), assuming a packing efficiency of 100%. The number of NSP tokens is 2 (L/2) and the respective weight is 1/ L. Again there is no variation and the weights between packed and vanilla BERT are identical. This seems more like an ideal case that is less dependent on how samples are put together. Also, it ensures equivalence between packed and vanilla setup.
Getting weights calculated correctly in a distributed setup (data parallel processing as well as pipelining) where each replica has small batch size down to challenging. Each replica would need separate gradients for NSP and MLM loss, then aggregate a weighted sum for those separate gradients, and only afterwards add up the gradients before the optimiser update. This is infeasible because of challenges in framework implementation, large increase of memory requirements, roughly doubling of the computational workload for the backpropagation, and more than doubling the communication overhead for weights.
We propose a simplified approach that generalizes from the weights, we observed for large batches, to the weights in tiny batches. Instead of averaging using the real number of tokens, we propose using the expected number of tokens instead. Technically that means, the mean aggregation gets replaced by sum aggregation multiplied by constant weight. Let b be our batch size, the token efficiency, p the packing factor, and m the maximum number of MLM tokens in a sample. This means, for
_tt_onfffaaaaaaaa_aaaaaaa DGXA 1 00 540x8x 16XX10005500xxx1__222200 www.wwww... sh+
1.2
38

---

Under review as a conference paper at ICLR 2023
vanilla BERT with sequence length 512, we have something like 0.5, p m 76 and for packed BERT, we have 1, 2, 76. Let 1 T(k)), k {1,-.b)
b) be the active MLM losses and F .j E J(k), k E {1,..,b) by be the active NSP losses in a sequence. Then we balance the MLM loss calculation like:
mean(Iy) = Exe(L...)) EVEr(H) pi.k
Eke(i...b) Eier(h) balanced(Ixr) ExE(1...)) EiErcs) 14 b. m-m-e
(25)
and the NSP loss calculation like:
mean(Ix) Eke(),..))) Ejeroy 1itk Exe(1,...)) Ejer(k)
Eke()...,)) Eseray PN b
balanced(Iw)
(26)
Note that when logging the loss, it should be averaged over multiple batches to get representative result that is comparable to values previously obtained. This approach is straightforward to implement any framework, even though some fine-tuning might be required when working with low precision.
In our experiments, loss balancing only reduced the noise in the NSP loss. Other than that, it had no influence on the loss curves.
39

---

Under review as a conference paper at ICLR 2023
U PACKING SOURCE CODE
Listing 2: Non-negative least squares histogram-packing
inportt time
angort nampy ap
eptinize,
inport Tru
det get
www_packingg_eteee mateixietrategy sertrstttryse.t... set,, pnk_sequenoe__engttn ret-gies isnistrtyy ret)
np.2c2o5 hogpepppeeesseeneeeeee
aun_stratsgios), stype-ap.int:3)
for la stretegy in enumerate e (strategy_
for seq_ien in strategy:
siru_cache (maxcize-None)
get strategies leegth,, minimm increment, target length, deptal: gap terget_icagta start_lengsh
strategies []
Completa the packing with axaetly number
gap (scpp
staatoques.aspmed(
Complete the sample in "depth" steps, recersively eloe:
Bav rance
paP 1):
nev_gep targrt_lergth start_leacta now
i5 new_gap =* stratsoiessapperd
options get ret_packing_strateeee (start t new, new, tarcet_longch, depth 12 for option in opticas:
len (option!
apsatsolaa.apseeddaaa option)
socurn strctopies
unique ways of pasking anL_seuuooo_eenthh auk_aaquance__oo__po naximun sequence lengch
stralegy_sei sel packing Lrateggees, 10, 1, nax_aequencs aer_aaquenee__eeeee Lengnel_lenglly lengtly nax mwc.eegenneeeperr..o print (f*kack will involve (lan(stzataoy_ae) Gct the packing
this cnique packing stzatagles.")
corresponding get_ www.i catcal aet,, beg.eegorow Maichts that benaliza the residual on short sequances less.
packing stratogios
panaiiaaiioncuueen -
Solve the packing problen
print ("rgquences to pack: histogsan.sur))) tine.time()
ctrategy_repeel.c poputt moomn opt inise.rmls (ip.expand print (2teabvir son-negatio least aquares took [tins, cine () atart:3.22) seconda," Round the fleating point solutien to aearest intoger replegy_rppeat_pooe
his.ogran]
up. ret Compute residuals, shapes (nqx_ length)
ype (666))))
rexidual histogran - 8 strategy prrategy..rpeeee repest_noort Bandle the Iwft oser Lapacked_ ap.asange max_sequano__ergrr for emparked__segeet
1.M. posiliow part sexidhes"
[residusl
atzalegy Ledddd nax_oeguence, length 11) $ the degth 1 stralegy atratacy_index stratecy_aer indox (stratecy)
compute the cosidual rateryy Index]
updated
This should now be strictly 6.0
rexidua) hixtogran A.
Add pedding based defici. repeatt
residual postion cwsidual) padding = np-shere (residusl. 6, -residusl, 0:
Caleulate some basic statissics
sequenou_ lengthe ng-arange Ct, mak_aegunno
sangles histogrann new_nurbes of___ff_llllla
regeet
speedup upper soreeoooue 1.0/vl (l. (histograms (1 seguence__enntths / nax_eequaace_eenggt)) comp
old number samplee)
wun_pe@diing_okkens..o
pmequnne_lengtte
pedding)
etticiency
num_ wwwding..coeeeeeeo weckensspsckeeeeeee (nww_nenber oumber_ot... sawg.essmax.cccmmoo sequence sequence_length
print (Stpacking inkking afficiency [frae: ion of real tokersl: (efficiency: 3.44))n',,
stSpeed thecretlsal linits Ispeedap pom___ hoand:3. (a4
s*Achleved speed-up un-packed dataset: nuncer wareer_oo__a_pppeeeeee cappppmees//ee nuncer, st_eamplees:..t1m
return stretggy set, strategy. repeat, count count
40

---

Under review as a conference paper at ICLR 2023
Listing 3: Shortest-pack-No first histogram packing
Ezon collectiona Laport defaclidiet regort nunpy op
def adc_ tseck, count, top, final, limit, offaet): neepilter out packs that teached neximun length number of sequenoes, Are (pask) limit offset final (ontsatt append (count, pack))
elaez
[ocfa]] append teount, pack()
pack wwing thistogran, mex sequeeee pee_eeppeno__eegith.. www.seepeeoooo.e...e.. hershoctest ppaceccket-teceeeeeee
reversed pack-tisat flrat patoogaa--packaa alçoritim,
stratagy diccionary.
key indicates how nany cokens
for length.
The ve vallie is a Hat of tuples, conslat iigg of counce and resgect ve packs. A pack
(sorked) l1st of seguenge length valuws that get concatemeted. tmp prppsstateggee..p lee_eeeeteeee
detaultdict at rattggees pepegeesperrr. pe_pper_lengt length defau defaultdice (litt)
Endex 1 Indioates hee,, hos mach space la left, due Lo revecaed histogran for
length)
nLseguencees_tg
stograan())
length max_ length
otfset = 4 largest possible offset whille nuseguences, bin 0:
(Jength offaet) in pee extract shortess pack that sill get mosified 1 LLeguennces Fo_ pack per.asseeegieeepa.eeee..
Length_to_ble
pack pack [length_ts count winte_eeeeeeese..ooooo it a_soguencer__t__ _o__pac > n_soquences__o__0 tiniii
I old pack reduced
rusequence trp. strattglessper. Leg_ieeghhilonggtheee bin aappent in sequences to pack, pacci) auooqunncss_toolli
n_sequeroess_
sequeences to
n. susequences, to past
add (ds_pack pack, count,
per__eengt,, lengta, strategies_pest lerggg
seguences per_pack,, offset]
clean up to spees up man key search
if not trp. wtt.sttggeee.pee.... length bin + lt ttp__rsttooss__o__oott.oooo (leavth_to_bin offset)
c1601
oftset -=1
1 Dees not fit anyиberc, Create new pack.
cctset
sequences
sairaccaies_por_ioooee stratadle__ee__lnnth,.
mxx_sequences, pww_requeneer_prr_pacc 1)
__eequnnce_sa_bih
nerge stratogies
for key smp_sstateggie per_length
cattaccee_por_eerrthhe oxtand ottp
Flatton dictionary
strategy_set
stratsqy_epeett_coum []
for seratogiss_por_ienott
pack.zsversa()
strategy_set.cdd (pack)
wwp...ppdddddddeee. (pack)
strateqy_rpeat_cau aapandd
stsstegy_stt, htw.tttooot_optttt.ooooo
41

---

Under review as a conference paper at ICLR 2023
Listing 4: Evaluation function of shortest- shortest-pack
pack-first first histogram histogram-ppacingg
Ma depth analyais of abortest-pact paact--i-tt sestocraa-packinng Fron col collections ingort defaulsdiat
snpuct Lebulate
inpozt tina
evaluate_sptap (blatoqran, nax_soquence_ 1ongth/:
resevalust shortest pack Fiest histogran packing algorithi thn. stata_data [l'pack. Septlit, *y strat. used", "6 packa", "A Lakena",
padding
"afficiency 18)*, "pack. factorr, "tine"]]
for max weg_sequeneen.pp per start Lime.time)
3, &, 16, *max"]:
usiing sptip histogran, ses_sequenoe Length,, mos_seeguerooopprrrroo dusation tine.time() atart
strategg strategy repest count
Per Curmanoe Realual lan of packing approach strrttggies
Lenietrategy retil
packs int fsum (st net reteey. regeett [ountt]
sequenbes = sun Jepunt I len(pack] for county pack in
totel_rokens ripletrasegy
strategy set) packs)
srax_segience_ Lopee_ taunf[
counts (max sequence (engch-oun(pack)) for count, pack in raptstyy regeett_count, strategy__et) set)]))
Loken Cffiinenyy
wng-y_iokens Lotalliokens 100
if max sequences per pack "max":
mL tength nax nan (Ilen for pack in strategy_seti]
(t))".tomat in_lnngt!
epgerd
nax seguencess_ park, nasteat packs, tokel_ empty tokene, coken_etticions sequences packs, decation]s print (tabul ste.tabulaceisten
Peiderge"Fiestron Float fnte", 3r""))
Listing 5: Loss calculation
The number of sequences in each barch requences aequences aquances_inn_ated LE.
(naaked leiggthht tf.cast (secuences, in_ if. (loat32)
Create the 0/1 nask that wilh be used to un packed sequences
masked awighh Lf. reahhagee (nasked In angggghh [3, 1, 1]]
reshape range (,, sequence heelection lan tf.cast hed ve
sequence selection
sequerces per
reegeence_seleetee f2.flost32;
Apply the mask Lo un pack the loss per sequence
nll per token reshaaee (nl per token, [3, -111 sequence_se weleeeeeeeeeiiii perussueeeee
ell_per_tokee
Mosmalize the guz sequence loss by the nutber of alarcokena
sequence (ax aLandard)
at tergeeed ed tfureduce sun Iseguence, selaction, -1, keepding-Trog nseTrue]
tengteed ed attempted tf.cast jestenpted per__pe__
tf., flow:322
prevent NaNs when dividing by abtengeed
all pess pesquueeeeeee
Leppted
Average per-batch lose [so contribud rlout lons from different batches are comparable)
ln LF, red are zum (nl] per sequence) /seguer ces in
42

---

Under review as a conference paper at ICLR 2023
Listing 6: Wikipedia and SQuAD 1.1 histograms
mnnixipodia and BQUaD 1.1 hestograns,
For sequencи length 128 512,
the Wikipedia arciele dump foom Outober 1st 202C.
for requenze length 1024 and 2040, we use the kikipedio artiale cump tron February 8th 2021. hupl ion factora alightly by differ.
Igorrt nonpy hp sikipedia oigoog mp.arrayll
C, 0, D. 0, 1821, 1226, 1985, 13:5, 1794, 1953, 3082, 3446, 4166, 5062,
9554, 16425, 19193, 17589, 17957, 19060, 21555, 25524, 26954, 30661, 33470, 36514, 40134, 43256,
46004, 49350,
60624, 63263, 64527, 65421, 68983, 68123.
70230, 70486,
12467, 72954, 73955, 14311, 75835, 78489, 1499,, 15377, 74954, 75056, 74284, 74698, 14332, 74638,
14370, 73557, 73597, 73153, 72358, 71580, 71082, 10085, 69733, 69445, 67818, 621.7, 56641, 65939,
64698, 63841, 63218, 62799, 61458, 50848, 60148, 59858, 5880s, 58023, 56920, 55999, 55245, 55051,
539:9, 52689, 52819, 52162, 51752, 51172, 50469, 49901, 69201, 49060, 47948, 47126, 46990, 96564,
46011, 45269, 44192, 44392, 78, 43986, 42988, 42365, 42391, 42219, 41668, 41122,, 40616, 40581,
39399, 40169, 39340, 58906, 35438, 38142, 31757, 57818, 37535, 37217, 36757, 35589, 36151, 35953,
35531, 35496, 35089, 35053, 3456', 34789, 34039, 33952,
33656, 33221, 32956, 32686, 32880,
31657, 31465, 31142, 31136, 50550, 30316, 32494,
29445, 28921, 29271, 29078, 28934, 28764, 28445, 28319, 28141, 28282, 27779, 27522, 22333, 27470,
27209, 27102, 2 20018, 27066, 26525, 26385, 26188, 26385, 26392, 20082, 26062, 25669, 25682, 25561,
25425, 25012, 25079, 25346, 24659, 24702, 24869, 24479, 24288, 24127, 24268, 24097, 23798, 25878,
23893, 23917, 23398, 23382, 23290, 22993, 23018, 20242, 22987, 22894, 22470, 22612, 22452, 21996,
21843, 22394, 21916, 21726, 21953, 21446, 21436, 21484, 21528, 21591, 21301, 21197, 21281, 22066.
20935, 21 0233, 20888, 20575, 20574, 20511 1, 26419, 20312, 20174, 20023, 20087, 1995,, 19946, 19846,
19562,
19556,
19487, 15387, 19225, 19069, 19350,
19934, 18763, 19900, 19012,
18893, 18 19645, 18577, 1831% 18458, 18374, 18152, 17822, 18102, 17735, 17989, 1.795, 11713
17590, 17303, 17669, 17410, 17583, 17531, 17318, 16892, 16967, 16870, 16926, 17233, 16845, 16861,
16376, 16665, 16455, 16687, 16745, 16526, 16473, 16349, 16273, 16255, 16228, 19219, 16021, 16112,
15867, 15751, 16081, 15703, 1575 15856, 15685, 15469, 15431, 15425, 15464, 15517, 15335, 15463,
15237, 15292, 15305, 15351, 13078, 14810, 15119, 14780, 14654, 14869, 14722, 14899, 14672, 14439,
16505, 14706, 14850, 14373, 15285, 14396, 14615, 16168, 14299, 13981, 14167, 14107, 19096, 14232,
13985, 14110, 14094, 14127, 13895, 13869, 1559%, 13572, 13717, 13669, 13782, 13611, 13284, 15335,
13425, 23057,
13318, 12425, 1331>, 13179,
13010,
12861, 12950, 12818, 12901, 12769, 12510, 12575, 12573, 12524, 12135, 12523, 12677, 12298, 12469,
12341, 12445, 12471, 12326, 12110, 12067, 12395, 12156, 12032, 12199, 12150, 11989, 12022, 13825,
11969, 11931, 1195T, 11924, 12739, 11685, 11702, 11783, 11783, 11559, 11647, 11610, 11526, 11573,
11538,
11236,
11376, 1:21%, 11002, 11245,
11124, 11000, 11129, 10323, 10565, 11071, 11029, 11036, 10972, 11012, 10300, 10935, 10904, 10750,
10569, 10756, 10780, 10975. 10503, 10511, 10598, 10383, 10638, 13471, 10667, 10502, 10430, 10400,
10510, 10140, 10469, 10316, 1025', 10286, 1023,, 10351, 10182, 10102, 02, 10095, 10192, 9065, 19073,
10148, 3956, 10132,
3782, 9799, 9799, 9789, 9649, 9767, 9797, S892, $393, 9535, 3638, 9534, 9593, 9539, 9523, 3188,
9920,
9838, 9854,
9540, 9410, 9418, 9508, 9638, 9521, 927 9209, 9253, 9322, 9281, 9351, 9259, 9253,
9225, 9098, 9268, 9227, 9224, S106, 5239, 3815044], ap. 1nt64)
uilppedi__nax_sequnno Jenggh 512
vikipedia_ 128_histcgrron (p.array(1
c, 5, 3101, 1980,
2921, 3125, 4830, 5364, 8047,
13409, 21166, 25207, 25106, 27445, 30336, 2503C, 39592, (5885, 52030, 57859, 64201, 71851, 78013,
86925, 91813, 99489, 104534, 112176, 117841, 120085, 125 153240, 138810, 143228, 145717, 151324,
154822, 158681, 162508, 165313, 188386, 170678, 172157, 174582, 174911, 177952, 173775, 179075, 178718,
179454, 179142, 179395, 178505, 179759,
174549, 173217, 174185,
170076, 168799,
165638, 166251, 163258, 161835, 160796, 158675, 157306, 156076. 154365, 153016. 151754, 150507, 148866,
145567, 144652, 143753, 141893, 140452, 139603, 138186, 136564, 135663. 134562, 132625, 132270, 129838,
130250, 125494, 127125, 126259, 125152, 120847, 120316, 123023. 122125, 121(34, 120822, 119356, 11941c,
117987, 118139, 116432, 116579, 114937, 114728, 114064, 114:11,
113091, 112457, 1:1797, 111032, 111055,
103929, 110613, 109624, 103634, 109102, 109301, 107099, 106661. 21454463), dtype-ap.int58)
1Mkipedi__12__ja___eee Length 128
np.array(1
6, 0, 0. 0, 1996, 1380, 2227, 1385, 1908, 2065, 3221, 3673, 4581, 5391,
5975, 16832, 19431, 18385, 19107, 20129, 23118, 24956, 29088, 32989, 35695, 38943, 43618, 46724,
5055s, 53774, 57470, 81019, 82236, 83350, 84128, 84939, 84585, 85705, 85151, 85245, 85923, 85869, 85748, 85704, 85459,
69859, 71609, 72274, 73630, 75620,
79774,
86822, 54067, 83960, 84322, 82652, 82371, B1509, 80958, 80255, 79266, 77896, 75827, 7E356, 73733,
14378, 13639, 72827, 71460, 70859, 69590, 69039, 67987, 66779, 65626,
65312,
63539, 63290, 62662,
61334, 61194,
57841, 57492, 56965, 55816, 55709,
53126,
52378, 51656, 51337, 50926, 50590, 50019, 0986C, 48821, 48788, 49365, 47776,
67225, 46417, 66428,
45922, 45626, 45021, 44818, 44293, 44338, 45474, 43547, 42987, 42685, 42425, 42255, 41725, 41583,
38212, 37845, 37808, 37639, 41194, 40717, 40565, 40238, 33761, 35557, 39235, 39009, 38935, 38841,
37852, 37513,
35265, 36026, 36135, 35781,
34939, 35241, 34523,
34106, 34106, 33687, 34008, 33631, 33630, 33335, 32960, 32756, 32666, 32421, 32135, 32230, 32395,
31561, 51958, 31580, 51250, 31074, 31199, SC74C, 30577, 30244, 30305, 30238, 30171, 25987, 29793,
29765, 29162, 29584, 29470, 20137, 29254, 29018, 28646, 28788, 28470, 28295, 28465, 28114, 26241,
27501,
27415, 2737E, 27357, 27194,
26929,
26278, 26246, 25962, 25901, 25915, 2554D, 25514, 25T01, 25934, 25284, 25452, 24888, 25031, 24975,
24900, 24756, 24554, 24505, 24558, 24828, 24275, 23974, 24305, 24229, 23824, 24005, 23606, 25746,
23496, 23262, 23477, 23510, 23083, 23185, 25239, 22947, 22939, 22879, 22846, 22564, 22942, 22512,
22245, 22468, 22453,
22075, 22081, 21918, 21789, 21121, 21641,
21370, 21654, 21360, 21237, 21327, 20946, 26841, 20701, 21044, 23797, 20810, 20758, 20616, 20715,
20370, 20444, 20365, 20420, 20263, 20046, 19942, 20301, 20056, 19971, 19798, 19573, 19720, 19676,
19526, 19350, 19325, 19385, 19095, 19333, 19286, 18955, 19190, 49,
18929, 18867, 18912, 18954,
18773,
16481, 18551,
18304, 1607',
18276, 18302, 19367, 18223, 18077, 17848, 18055, 17895, 17757, 17755, 17534, 17617, 17292, 17452,
17367, 13464, 17480, 17456, 17212, 17554, 19548, 17296, 19800, 17989, 17039, 17151, 17113, 16942,
16955, 16744, 16922, 17037, 1597', 16736, 16945, 16537, 16703, 16328, 16587, 15339, 16404, 16492,
16325, 16309, 16374, 16262, 16180, 16202, 16021, 16042, 16129, 16101, 15986, 1919% 15792, 15935,
15914, 5, 15902, 15688, 15713, 5676254
43

---

Under review as a conference paper at ICLR 2023
d.ypomop.1nt64)
- 384
102_edd__12___hhttooorr ap.orcay
6, 0, 9, 0, 1363, 4764, 8434, 16.0, 13205, 6932, 10566, 13887,
16118, 24347, 31871, 66246, 77082, 55887, 66852, 69969, 79068, 86941, 99807, 1:1153,
123150, 137392, 154228, 165204, 180331, 192043,
215316, 221387, 238853, 247644,
253357,
258237, 262474, 266124, 269895, 275211, 277955, 280352, 283614, 286648, 287714. 291932, 292063,
292252, 292122, 291963, 291550, 250741, 289930, 289525, 288843, 289105, 285626, 283735, 293763,
278961, 277495, 275528, 274259, 271725, 269130, 266326, 262998,
262027,
259306,
256137, 253231,
251842, 249255, 246119, 243579, 240920, 239553,
228900, 226724, 222635,
220947,
134504, 192778, 217754, 215699, 213277, 203413, 209457, 206663, 202550, 201057, 199017, 196767,
190108, 198113, 186439, 184212, 182825, 181271, 179263, 171707,
174891, 173922, 172658, 171363,
168E95, 161579, 165974, 164577, 1E3921, 161673, 160832, 158468,
157537,
155880,
154636,
154374,
152753, 151593, 150617,
146336,
140450,
139865, 138122, 137013, 135298, 135120, 133563, 133063, 131795, 181001, 130944, 125152, 128813,
127434, 127698, 126006, 124765, 123580, 123935, 122TE8, 121385, 1212:2, 119757, 118557, 118198,
117536, 117253, 116175, 116240, 115372, 114303, 113925, 113271, 112221, 111853, 110628, 110357,
109411, 109347,
108049, 107465, 106265,
105049,
103313,
101732, 101998, 101922, 100885, 100328, 99BC3, 9977L, 9612D, 98958, 98036, 97756, 57099,
95360, 95916, 947B1, 94124, 96467, 92505, 92947, 93067, 92161, 91783, 91722, 91620,
50588, 90104, 89136, 89196, 88815, 88424, 87636, 87356, 87247, 86421, 86743, 85135,
84004, B3326, 82563, B2220, 81649,
B1101, 80423, B3860, 79756, 79404, 7B346, 7E65S, 78712, 77841, 77453, 77561, 75607,
76480, 78123, 76217, 76223, 75105, 75051, 74794, 74204, 73918, 74153, 74136, 73817,
73022, 72178, 71935, 71819, 71835, TOS87, 70521, 70501, 69927, 70242, T0127, 69685,
69655,
6834 67440, 67554, 67010, 66569, 68745,
65594, 65858, 64803, 64661, 64710, 54451, 640SC, 64068, 53082, 63415, 63325, 62578,
63069, 62079, E2130, 62529, 61561, 51093, 6125C, 60325, 60248, 60187, 60726, 60105,
59547, 59112, 60090, 59104, 58742, 58683, 58425, 58537, 58229, 57599, 57673, 57604,
56866, 56289,
58058, 56437, 95851,
55218,
55359, 54481, 54468, 54634, 54025, 53690, 54213, 53115, 53392, 53114, 53451, 52685,
51918, 52558, 52225, 51882, 51453, 51946, 51435, 51036, 51206, 51581, 51154, 50610,
50705, 50615, 49501, 49823, 49730, 49855, 4926E, 4D119, 48975, 43909, 48687, 43603,
48227, 47013, 52152, 48029,
47846, 61209, 47368, 46891, 46944,
46729, 46052, 46148, 45931, 45702, 46161, 45322, 45857, 45583, 45433, 45154,
44827, 44354, 44175, 44192, 44053, 43849, 43935, 43927, 43549, 43493, 43250, 43172,
42918, 42648, 42747, 42936, 42206, 42169, 61825, 421 90, 41973, 42001, 41717, 41141,
41419, 41234,
40836,
40454, 43242, 40343,
19512, 39971, 39321, 39238, 39143, 35453, 3904E, 38957, 38935, 38984, 38588, 33064,
68165, 38196, 38215, 37930, 37995, 37976, 38212, $7397, 37367, 37575, 37351, 37215,
36850, 36864, 36801, 36822, 35685, 36479, 3639C, 56341, 36355, 35850, 36282, 35294,
25433, 33690, 25534, 35105, 35065, 35092, 34852, 35046, 34539, 39548, 34316, 34918,
34782, 34416, 34643, 34643, 34029, 34078, 35781, 33601, 33636, 33455, 33513, 33516,
33222, 33694, 33571, 32986, 33058, 32760, 32795, 52538, 33060, 32696, 32659, 32522,
32400. 32250, 31852, 31913, 52168, 31532, 41496, $1V28, 31518,
31496, 3111%,
313 31275,
30977, 31021, 30815, 50858,
30219,
30113, 30292, 30075, 30073, 29820, 29749, 29319, 20727, 29824, 29448, 29068, 29252,
28831, 792.7, 29361, 20997, 28648, 25081, 29048, 28V00, 28116, 28536, 20346, 28482,
28525, 28541, 28255, 28145, 27853, 28094, 21736, 77422, 28158, 27547, 27292, 27893,
27497, 27375, 27503, 27509, 2T200, 27160, 21336, 26889, 26950, 26876, 26422, 25895,
26382, 26752, 26113, 26290, 26289, 26319, 26033, 26045, 26801, 25659, 26243. 255 73,
25477, 25590, 25717, 25333, 25555, 25537, 25305, 75326, 25035, 25290, 25129, 25184,
26704, 24956,
24793, 24598, 24614, 20837,
24576,
24204,
24205, 23869, 24080, 23894, 23300, 23916, 25091, 23636, 23204, 23632, 23503, 23316,
23546, 23490, 23438, 23541, 22810, 23053, 25151, 22921, 22966, 23220, 22938, 22880,
22811, 23104, 22819, 22737, 22805, 22293, 22722, 22652, 22258, 22068, 22119, 22286,
21 987, 22228, 21901, 21529, 21975, 21801, 21 748, 21729, 213,3, 21548, 21501, 21695,
21591, 21400, 21389, 21341, 21575, 21345, 2125), 21217, 21294, 21093, 21C79, 21414,
21021, 21200, 2105', 20713. 20106, 20996, 20589, 20543, 20621, 23649, 20612, 20138,
20550, 20299, 20523, 20269, 20529, 20150, 20371, 20306, 20331, 20453, 20064, 20243,
20080,
15589, 1945C, 1976C, 19690,
19768, 19456,
19312, 19364, 19347, 19194, 19264, 19027, 19393, 19117, 19370, 19019, 18950, 18105,
18802, 18690, 18627, 18507, 1843,, 18523, 18592, 18389, 18624, 18446, 18506, 18615,
18359, 18049, 19322, 18004, 18211, 18341, 1838,, 18162, 17597, 19105, 18038, 17843,
17705, 18096, 17998, 10100, 17634, 178811 17008, 17655, 176222, 17509, 17609, 19403,
17727, 17569, 17443, 19332, 17526, 17521, 17632, 17039, 17540, 17027, 17338,
17574, 16956, 17100, 16919, 17032, 16887, 16924, 16720, 16928, 16828, 16831, 18925,
16585, 16953, 16655, 16723, 15658, 16419, 16808, 16566, 16485, 16579, 16287, 15263,
16158, 16258, 16330, 16304, 15578, 16289, 16253, 16257, 16007,
13994,
15842, 13995, 15966, 15877, 13692, 15789, 15691, 15961, 15714, 15521, 15376, 15719,
15513, 15558, 15673, 15422, 15265, 15369, 1528,, 15512. 15327, 15325, 15182, 15177
15186, 15257, 15354, 15283, 15152, 15220, 1479E, 14928, 15041, 14849, 15315, 14860,
16903,
14862, 18816, 14591, 14905,
14595, 14903, 14687,
14431, 14416, 14561, 14263, 1432., 14539, 145 14353, 14188, 14097, 14306, 14413,
16101, 14363, 14199, 14102, 1509L, 14263, 14145, 10080, 14058, 13890, 14070, 13861,
16216, 13963, 13852, 13922, 13890, 13679, 13932, 13826, 13612, 13123. 13660, 13822,
13891, 13699, 13534,
13875, 13617, 13649, 13567, 13585, 13306,
1327.,
13199, 13577, 13185, 13174, 13258, 12153, 13392, 13266, 13022, 13096, 12898, 13160,
13177, 13244, 12522, 12964, 1301., 12995, 13161, 12716, 12891, 12805, 12817, 13645,
13093, 12673, 12827,
12725, 12517, 12613, 12658, 12720, 12517, 12926,
12604, 12597,
12528, 12393,
12775, 12418, 12516,
12463, 12195, 12129, 12111, 11569, 12306, 12118, 12351, 12332, 12169,
12141, 12169,
12000, 11966, 12013, 12142, 12110, 12011, 12265, 11965, 11907, 11752, 12037, 12774,
11771, 11974, 11860, 12046, 11773, 11636, 11751, 11522, 11786, 11521,
11574, 12619,
11598, 12056, 11546, 11554, 1186T, 11332, 11384, 11525, 11548,
11517, 11424,
11398, 11385, 11509, 11297, 11588, 11222, 11452, 11350, 11072, 11121, 11215, 15122,
10392, 10948, 11319, 11001, 13223, 11349, 10749, 11281, 11036, 10907, 11185, 10585,
10321, 11003, 10942, 11047, 10875, 10757, 11116, 10554, 10921, 10784, 10346, 10680,
10553, 10959, 10535, 69636321, dcyperap.int60
44

---

Under review as a conference paper at ICLR 2023
1024
2etpodio_201B_hictoere np.orzay( (:
2473, 1876, 3242, 2262, 1312, 2735, 4075, 5706,
6688, 10490, 11372, 18357, 19043, 17166, 19433, 20247, 22804, 24700, 27419, 30029,
32527, 35910, 39100, 42465, 03513, 40261, 50135, 53069, 55707, 57654, 60733, 63289,
69578, 67824, 75064, 72022, 74545, 75868, 77463, 78728, 80340, 80398, 81369, B2172,
62038, B2545, 82620,
BC926, 81093, 81594, 83329, 91285, B:015,
79730, 79943, 75811, 50007, 78575, 78209, 7E174, 77714, 76950, 78864, 75966, 75074,
74945, 75553, 74347, 73401, 72540, 72502,
71834, 70761, 70221, 69597, 68371, 67207,
6692T, 66421, 65566, 64768, 64117, 52245, 62774, 62196, 61655, 61419, 60955, 59983,
58353,
57572, 57232, 56518, 55995, 55816, S5627, 55505,
54340, 54207, 53927, 53662, 53362, 52812, 52522, 52056, 51834, 51047, 50368, 50703,
50178, 50507, S00B1, 50183, 08568, 45051, 08651, 4B129, 67735, 47660, 47069, 07101,
46740, 48517, 46858, 46588, 45340, 45488, 45065, 45149, 45238, 44779, 49004, 44332,
42671, 42189,
41309, 41411, 40457, 41006, 40225, 40108, 39588, 40082, 39498, 39557, 39808, 39235,
38720, 38549, 29364, 58165, 3826T, 38112, 31755, 57727, 37449, 37474, 37799, 35787,
26550, 36457, 27130, 36613, 36214, 36071, 36418, 36246, 35613, 35805, 35826, 3503',
34758,
34282, 33928, 34027, 34037,
13894, 33497, 23642, 33634, 33393, 33305, 22581, 33038, 32708, 32127, 32435, 32092,
32203, 52239, 21599, 32348, 31203, 31696, 31438, 31155, 30889, 30825, 31209, 30280,
30519, 50494, 30875, 20338, 30435, 29785, 36119, 29787, 25785, 29481, 29369, 20160,
28934, 28961, 28603, 28319, 28558, 23798, 28318, 28095,
28397, 28244, 27782, 27889, 27584, 27322, 21239, 27563, 27056, 26982, 27232, 25753,
26513, 27066, 26812, 26210, 25035, 26053, 26415, 28086, 25182, 25645, 25715, 25757,
25530, 25920, 25268, 25639, 25250, 25564, 25032, 25018, 25226, 25065, 24304, 24613,
24269,
24334, 74497, 24043, 23844, 23872, 23863,
23439, 23613, 23434, 23735, 23325, 23362, 25119, 23373, 23561, 23088, 23213, 23074,
22859, 22651, 22644, 22570, 22813, 22739, 227D4, 22380, 22568, 21998, 22210, 21782,
22120, 22003, 22079, 22104, 21610, 21464, 21687, 21587, 21167, 21427, 21670, 21335,
21291,
20776, 21016, 20513, 20656,
20830,
20213, 20221, 19983, 20175, 20135, 20361, 19928, 19803, 20031, 19887, 19899, 20007,
19746, 19429, 19600, 19353, 1959., 19708, 19247, 19181, 19396, 19501, 19071, 19292,
19370, 18672, 18625, 19062, 18839, 19238, 18735, 18741, 186:1, 18673, 18649, 18607,
18288, 18492, 19250, 18295, 18043, 18118, 18085, 18915, 18246,
17812, 17899, 17832, 17604, 17389, 17259, 17594, 17854, 17632, 17437, 17571, 17484,
17221, 17363, 17137, 17013, 17228, 16546, 16678, 16901, 17203, 17015, 16700, 1547:,
16574, 16551, 16556, 16363, 16261, 16498, 16515, 16469, 16352, 16434, 16283, 16635,
16059,
16299,
15200, 15832, 16017, 15751, 15870, 15851,
15818, 15675, 15504, 15608, 15358, 15712, 15423, 15366, 15539, 15175, 15122, 13092,
15435, 15316, 15097, 15012, 14764, 15226, 14700, 14831, 14973, 14986, 14669, 14639,
14901, 14918, 14416, 14724, 14525, 14643, 14837, 14175, 14598, 14481, 14416, 14192,
14105, 14256, 14249, 14096, 14393, 19043, 14080, 14026, 14113, 14249, 14066, 14003,
14089, 13892, 13609, 13920, 13895, 13422, 15735, 13896, 13? 13631, 13807, 13904,
13447, 13667, 13535, 13467, 1385T, 13624, 15735, 13463, 13257, 13:62, 13450, 13377,
13194, 12986, 13305, 13407, 13192 12968, 13076, 12980, 13911, 12996, 12851, 12932,
12772, 17885, 12939, 12207, 19787, 12675, 12816, 19525, 12386,
12479,
12726, 12451, 12297, 12294, 12252, 12404, 12387, 12421, 12540, 12010, 12297, 12285,
12252, 12021, 12042, 11948, 12015, 11910, 11914, 11931, 120:3, 11587, 11610, 11493,
12047, 11560, 11890, 11661, 1170%, 11683, 11551, 11449, 11450, 11127, 11488, 11365,
11109, 11150, 11363, 11259, 11162, 11156, 1109), 11306, 11144, 11264, 11243, 12068,
11027, 11366, 11078, 11035, 73, 10845, 11028, 10871, 10822, 13974, 10817, 10619,
10532, 10617, 10635, 10513, 10625, 10725, 16434, 10293, 10630, 10616, 10607, 10293,
10503, 20246, 10304, 10439, 10228, 10325, 10331, 9887, 9972, 10385 10159, 10089,
10112, 10180,
10078,
9939, 9914, 10042,
9845, 6,
$889, 9861, 9703, 9578, 9722, 9752, 3, 9483, 9572, 9676 6676, 99 1, 9636,
9629, 9:23, 965 9613, 95.1, 9546, 9432, 9247, 9298, 9284, 9392, 9558,
9428, 9302, 9269, 92.7,, 9215, 9296, 9516, 9561,
91
91 9127,
8933, 9952, 9313, 9017, 9087, 8954, $129, BE95, 9127, 8863, 8791, 8972,
8686, 8990, 9,4 8095, 8191, 0832, 8152, 9646, 9644, 8155, 8156, 8152,
8529, 8637, 8476, 8515, 8595, 8407, 8506, 8600, 8572, 8566, 8521, 8514,
B630,
0327,
0233, 9226, 9159, 820', 8155, 0296, 0203, 9215, 1933, 1092, 9199, 8086
1958, 1994, 8204, 8064, 8010, 2944, 7959, 7854, 7568, 7788, 2853, 2766,
1983, 7895, 1801, 1896, 7011, 7794,
7719, 7670, TEST, T702, 7602, 7694,
1871, 1581, 1640,
1326,
3447, 2567,
7423, 7359, 7557, 2690,
7569, 7310, 2372, 7301,
7219, 7374, 7202, 7160, 7381, 7226, 7179, 7042, 7172, T122, 7170, 7176.
1165. 1284, 1140, 1074, 1026, 1141,
7016,
1006,
1069, 6631, 6961, 6866,
6789,
6625,
6850, 6842, 6705, 6895, 6929, 6935, 6679, 6625, 6672, 5692, 6919, 6317.
6760, 6:04, 6690, 6631, 6461, 6455, 6539. 6108, 6521, 5634, 6597, 6622.
6594, 6361, 6327, 6309, 6568, 6392, 6515, 6188, 624T, 6221, 6608, 6607.
6230, 6319,
6236,
6259, 6260, 6169, 62
6002, 6096, 6166, 6239, 5964, 6007, 6342, 6193,
6242, 6275, 6004, 6297, 6035, 6035, 5945, 5859, 5C62, 5017, 5994, 6016.
1938, 6012, 6110, 5839, 2036, 3799, 5839, 5941, 5133, 5629, 5633, 5920.
5736, S747.
5772, 5720, 5729, 5648, 5620, 5585, 5439, 5292, 5653, 5577, 5674, 5562.
5696. 5945, 5566, 5626, 5362, 5838, 5606, 5461, 5474, 5484, 5332, 5425.
5550, 5476, 5466, 5262, 5270, 5457, 5389, 5453, 5443, 5207, 5334, 5289,
5139,
5361, 5281, 5224, 5218, 5229, 5234, 5101, 5241, 5C71, 5069, 51Y3, 5157,
5034, 5070, 5171, 505T, 5055, 5046, 4968, 5045, 5015, 4988, 5043, 5086.
1982, 5013, 1932, 1938, 1962, 1942, 2000, 0E07, 1895, 4783, 4991, 4986.
4805, 4995,
4970,
4636, 0729, 4629, 4791, 4805, 4896, 4852, 6671, 1937, 4739, 4584, 4671.
1682, 3578, 1370, 4792, 1605, 4751, 3626, 0604, 1603, 1631, 4798, 4395.
4638, 4744, 4571, 4493, 4608, 4480, 4632, 6641, 4625, 4450, 45:2, 4491,
1601, 4562, 4561,
4504, 4425,
3036, 4356, 1405, 4300, 4329, 4501, 4509, M115, 1333, 4368, 4290, 4350,
45

---

Under review as a conference paper at ICLR 2023
4356, 4202, 4337, 4254, 4252, 4323, 4176, 6374, 1435, 4300, 48.5,
4316,
4342, 4316, (329, 4199, 4177, 4206, 4387, 0265, [103, 4227, 4227, 0214,
4230, 0:26, 6193, (159, 4089, 4125, 0215, 0087, 1699, 4064, 4139, 0085,
4074, 6130,
4117,
2956, 2823, 1053, 4064, 4031, 8051, 2990, 3979, 3987, 2924, 1025, 2934.
1951, 1911, 3953, 3921, 4055, 1855, 3935, 0005, 3894, 3852, 3997, 3990,
2869, 3898, 3853, 3866, 3888, 1992, 3764, 2812, 3885, 3675, 3794, 3964,
2852,
3754, 3680, 3632, 3695, 3635, 2715.
3677. 3613, SE13, 3619, 3675, 3652,
2806, 3787, 3128, 3620, 3677, 2575, 2736,
3679, 3724, 3754, 3609, 3613,
2642, 3701, 3558, 3698, 3650, 2651, 2586,
3437,
3513, 3623, 2551, 3580,
3506,
2417, 2554, 3454, 3595, 3410, 26:1,
2496, 2552, 3585, 3498, 25:8, 2438,
3007, 3646, 3589, 3343, 3426, 2195, 2455, 3329, 3368, 3356, 3502, 3682.
3345, 3456, 3348, 3388, 3362, 3371, 3516, 3251,
3349, 3461, 34.5, 3311,
3331, 3203, 3190, 3180, 3308, 2203, 3132. 3155, 3255, 3206, 3155, 3096,
3152, 3160, 3223, 5140, 3252, 2176, 2189, 3247, 3203, 3262, 3227, 2131,
3113, 3235, 3119, 3196, 3130, 2052, 3150,
3093, 3234, 3115, 2039, 3376,
3026,
3049, 3205,
2948, 3110, 2881, 2987, 2950, 3921, 2988. 2965, 3C99, 3069, 2984, 2977,
2957, 2988, 2923, 3071, 2936, 2995, 2937, 3089, 2883, 2991, 2927, 2050,
2806, 3064, 2856, 2876, 2035, 2944, 2864,
2680, 2903, 2782, 2747, 2916,
2928, 2503,
2830, 2846, 2746, 2814, 2852, 2925. 2789, 2906, 2810, 2799, 2787, 2705,
2825, 2803, 2026, 2807, 2755, 2737, 2747, 2395, 2683, 2780, 2844, 2848,
2809, 2525, 2611, 2739, 2717, 2642, 2664, 2157, 280T, 2704, 2809, 2689,
2637,
2677. 2653, 2796, 2619, 2647, 2558. 2727. 2642, 2672, 2603, 2578, 2307.
2815, 2655, 2523, 2661, 2605, 2635, 2562, 2573, 2615, 2534, 2625, 2515,
2658, 2464, 2624, 2564, 2637, 2698, 2572, 2631, 2527, 2622, 2586, 2535,
2474,
2335, 2496, 2492, 2533, 2538, 2582. 2425, 2465, 2540, 2470, 2531, 2566,
2391, 2540, 2856, 2405, 2515, 2435, 2557, 2544, 2561, 2414, 2528, 2536,
2521, 2468, 2458, 2408, 2524, 2397, 2477, 2286, 2278, 2503, 2459, 2385,
2416, 2392, 2409, 2372, 2491, 2236, 2412, 2236. 2413, 2420, 2400, 2370, 2471,
2393,
2314, 2359,
2403, 2421, 2270, 2389, 2230, 2371, 2285, 2563, 2581, 2409, 2245, 2228,
2391, 2304, 2248, 22 2362, 2282, 2236, 2561, 21 68, 2305, 2353, 2260,
2301,
2302,
2293, 2188, 2189, 2255, 2173, 2234, 2098, 2225, 2165, 2276, 2283, 2317,
2213, 2136, 2289, 2220, 2288, 21'2, 2266, 2118, 2270, 2204, 21'0, 2258,
2215, 2227, 2131, 2215, 2255, 2238, 2129, 2141, 2203, 2054, 2171, 2170,
2132, 2162, 2069, 2290, 2221, 2122, 2208, 2121, 2134, 2120, 2137, 21'2,
2165, 2195, 21 00, 2044, 1985, 2058, 2104, 2037, 2125, 2121, 2043, 1994,
2102, 2114, 2003, 2069, 2055, 2125, 2080, 2693, 2658, 2021, 2049, 2097.
2162, 2195, 2022,
2009, 2181, 2039, 2059, 2053,
2068,
1929, 2058, 1997, 2050, 2092, 1922, 1976, 2623, 2085, 2003, 1976, 2027.
1970, 2052, 1978, 2005, 1997, 1992, 1990, 2033, 2035, 1931, 20.2, 2009,
1890, 1960, 1879, 1946, 2078, 1976, 2011 1916, 1963, 2058, 1998, 1966,
1954, 1931, 1886, 1970, 1967, 1922, 1853, 1843, 1983, 1912, 1951, 1932,
1903, 1878, 1915, 1886, 1961, 1899, 1840, 1966, 1889, 1882, 1986, 1923,
1908, 1868, 1913, 1797, 1773, 1871, 1780,
1815, 1981, 1840, 1787, 1920,
1909, 1835, 1932,
1829, 1837,
1809, 1834, 1845, 1624, 1911, 19.6. 1842, 1769, 1837, 1875, 1839, 1904,
1713. 1801, 1579, 1913, 1854, 1899, 1802, 1799, 1859, 1272, 1884, 1797,
1821, 1951, 1939, 1693, 1725, 1816, 1733, 1775,
1761, 1771, 1824, 1860,
1775, 1827, 1808, 1960,
1694, 1753, 1759,
1744, 1750, 1742, 1801,
1783, 1832, 1727, 1764, 1755, 1788, 1766, 1739,
1777, 1761, 1724, 1707.
1796, 1726, 1939, 1717, 1154, 1185, 1119, 1696, 1651, 1152, 1699, 1/17,
1713, 1750, 1697, 1685, 1681, 1684,
1309, 1145,
1503, 1641, 1649, 1710.
1639, 1570,
1746,
1639,
1686, 1534, 1653, 1615, 1626, 19:2, 1916, 1621,
1581, 1669, 1646, 1687,
1748, 1749, 1614, 1629, 1636, 1728, 1568, 1661, 1638, 1614, 1545, 1660.
1612, 1577, 1516, 1627, 1572, 1675, 1725,
1696, 1638, 1613, 1570, 1540,
1643, 1521, 1522,
15.2,
1613, 1584, 1480,
1612,
1550,
1524, 1569, 1575,
1572, 1526,
1570. 1511, 1673, 1537, 1521, 1495, 1902, 1639, 1547, 1602, 1541, 1617.
1640, 1545, 1528, 1610, 1983, 1583, 1511, 1601, 1564, 1527, 1501, 1451,
1539,
1617, 1502, 1491, 1522, 1528, 1486, 1537, 1413, 1572, 1392, 1956, 1396,
151 1471, 1422, 1494, 1406, 15:0, 1512, 1495, 1535, 1454, 1429, 1499,
1485, 1489, 1525, 1529, 1552, 1451, 1500, 1450, 1403, 1428, 1569, 1569,
1509, 1414,
1489, 1439, 1586, 1463, 1319, 1482, 1396,
1405, 1495, 1551, 1413,
1389, 1385, 1360, 1417, 1378, 1435, 1445, 1372, 1483, 1369, 1841, 1353.
1530, 1570, 1401, 1421, 1414, 1493, 1419, 1363, 1372, 1303, 1397, 1411,
1395,
1381, 1375, 1341, 1379, 1420, 1402, 1339, 1336, 1403, 1390, 1370, 1463,
1319, 1436, 1406, 1379, 1401, 1312, 1336, 1406, 1955, 1963, 1377, 1396,
1382, 1341, 1337, 1385, 1322, 1380, 1286, 1503796], dpype-ap. 1nE64)
xikipedia_ 2tr_2o00_____eeeeee__
2040
ap.orray
c, 5.
0,
0,
0,
0,
0.
0,
0,
0, 3,
5,
10,
15, 22, 24, 35, 35,
86,
42,
57.
86,
83,
86,
87,
86
87,
50,
99, 85, 94,
105,
114, 113.
93, 116, 118, 116 116
127,
127,
115,
155,
237.
145.
157
151,
153,
199. 163, 157.
134, 150, 144,
132.
166,
162 175, 160,
149,
151
138
156,
148, 176.
163
182
188,
182,
177, 199,
203,
201,
244,
289,
373
286
553.
608, 673.
712,
722,
745.
692,
69%,
747,
754,
741
773
781
825,
813.
836,
737.
776,
755,
799, 799,
46

---

Under review as a conference paper at ICLR 2023
165, 753,
786,
760,
755.
132,
730,
785.
725,
683,
688, 677, 562,
628,
625.
618,
555,
527
562,
619.
592,
578,
536,
558,
582.
541
575
525
556,
492,
129, 486,
525,
541,
682,
521,
183,
469,
514
629,
647
435,
183,
401,
489,
J81
359,
264,
381,
423,
305,
238, 257
254,
253,
214.
267,
23%
193.
205,
208,
193,
201, 197,
173,
176,
195.
156,
202
119,
155,
183.
195,
178,
163,
153,
171,
146
138,
181,
165,
171,
161,
159,
166,
142,
138,
151,
153,
134,
141,
132,
123,
119,
103,
125,
123,
131.
135,
115,
138,
102,
16,
72.
67
80
77
55
89,
72
49,
82,
54,
42,
83,
56.
45,
42.
32,
30,
36
42
37,
45
25
41,
31.
44
25,
36
47
67
48
65
32
23
35,
35,
20,
23,
22,
21,
27,
26
18,
18
22,
17,
24,
15,
20,
22,
19,
24,
17,
15,
20,
20,
22,
22,
27,
29,
d.ypwmap.
20005 1_3 poggeeg longth 284
47

---

Under review as a conference paper at ICLR 2023
Listing 7: Histogram creation for GLUE training datasets
Copyright 2020 The HargingFace ace Inc. Lean. Xl1 Eights reserved.
Licensed under Apachia Licenas, Version
"Lioenae") you may not use this fila except in compliance with the Micense. You obtain
of the License
httpt//www.ett wwtp///wwww.s... www../awc.........ooooo.... wtwpg///ooenn///eee....
Unleas required applicable las agreed Lo in wricing, soflaere
RETHOUT SARDANTERS eR CONDITIONS distributed KIND, wit her express inglied. See the License for the specific language governing pesnisaions and mimtati onn under the loenss. eeggg data loading
hyaan ion.
Sone code snippets were taken Fron
http://gtttiit con/bogging fave/ cans Corners ola//aaa /etpe//xxallllleeeeeee en/ pyw.oeh/ clasel Eital Lon/ rrnng
originel oode,
Cron Leans Leans-ussnee Curmer impert AuloTokenizes
datasete
agoort nuepy "p
constants
ww_.seguence... hangggh 128 Lok_____
"cola": ("sentence', None),
"enli*;
("prenise", Phypot hes If
"prpo": ("seatencel", "senzence2"" "),
"gpli"; ("question,, "eenterce"),
"gup": I"questionl "question2
"scef: i"sentencel", *sentense2"1,
"sat2*: ("sentence*, None),
"scb": ("sent "senience2"),
"anli"; ("centencel", "sentence2"),
olye_keys ["ocld", fset2', 'napef,
due to niseing sraining 'steb', 'mil"" ixter, "mii']]
ing ue keys ("mnl matched', Amll mimeetcched ipll,, (ax"]
load
for key in alue_keys:
dataset cacaset_loads loads key] = dstasets. decantts.loodddrssetttt dataset ("gluet, key, splitertrein")
tokenize
coterizer setcookenizer.rromm trrppprreee (eeerttteee---ossss))
cokorized_data + ()
dataset_loades key keys(key] key,
set preprooese_ wtt.sesoottnnttoioccoo..oco
**"ookeniza
args
(exampled sentencei key).) it sentercel__ey key Kone
clse texamples [sentenee_eeeyy examples ko/]]
result tekenizer Fadeing-Falee, www_lenntrraaxeeoooccc.oo truncatien-Truel return result
beeenired_ddta/aeee sotaset_loacs key) (preproccess tunction, batched-Trus!
extrast length infornstion (tor histogren plots)
siscogran_ length
tokenized_dats:
for nanber, key in onunerate (tokani zed_ data.kevs (1) for rax_roocrd in tokenized aadiiadd_aaa data [ke]] ["inpat_ids""
histegram_Lennttiiee
(lon for rav_resord x!-0]1)
create histocran for packing
alowwhistonn histogran
data_key bistograr_tenqshi
ap.array nax_coquance_lenae stype-np.int6n for untry in Listogran Senggh
clo__hictscramidtta__a
hitt_histogran Jayaa [entry-i] to
48

---

Under review as a conference paper at ICLR 2023
Listing 8: Longest-pack- histogram packing
Ezon collectiona Laport defaclidiet
regort nuepy "p
sepuct Line
adckpack
Lop, final, limit, pifaet, nan_aequence (ww_aagannooeeigiaeedee. sesgiltor packs seached maximun longih oz numbar componenta.
sanity checks
axsert seax_aeeuen hun foffeet
=* oftsw),, Micarrect offaet."
*Ton offaet."
assert (uffeet: s tun_aequence lengtht,, if len (pack) linit or offset 0:
large offsee."
Final loffaet] l seppend (count, pack)]
Lmp [nplo[[aet] resunt, pack!)
uock_usingg_ lpthp Inietogram, sequence lergth, petpseennes__r___pe___ distrsbuce=rrue)
Longest -pack--k-i first bistogren perggen--pcceee backingg stack Line LineLine(]
reversed histogren cp.tiiiphiseeegrom
Fnitial kuy indicates how nany Lokens are for length. The value is list of tuples, consisting of counce and respective pacts, A pack is (sorted) list of seguenge length values that get concatensted. tagaatoollageen_oee lengghh deTaulidiat (liat)
strategy
diocionary.
et stretegles es per length defaultdict if max sex_sequences pet.e.eep..rr..... peck is fnax":
mmx_eeguences_r
www_seguonc_lenggh
indicates here,
space
histogran
for range wwwp__/eeeeoe___rggooo
aLsequences_to. sicceetttb_tt__.. seversed_histoorrun length to bin
length
snallest while ruseuuencss. to air
affe
offeet
18 (length to bin offset) in top strategiet per per_ langth:
moditied
a "_sequences_ po_pkkk, pack tmg.etrategies.prr_.oooo
length to bin I-peel)-poop))
colculate haw atten the current coquence mexinally rite in
// length_to sex_eegences, per pet.eeeeeee..ppcller.pppppo. pact-lee. (pack))
dependent
shile w_.opponcee.to_sss//rrooo
repeat
distrizuts:
repeat =1
new pack pack (ength to biepsr
count sasait__eeccers__t___aae aLeqpenee__t__bbl//eppa
a_pequences_to__e count:
pack gets
R_ecqumccs_to___a
to_pcckk count
imp_stratsgies_ppr__iee
htgpgggss___p___gghiii_iieie Longthttingttttto_ spppet)
ropeat
else:
i_aoquancas_to_jit
tocp zepeat txp_otrosegies
sds_packinsv_padk
per__iees_pr__ettt__ strategies Secogies_per_irgeee perglength,
nax max_oecunnee_par__aaat offsct [sepeat 1) lonach_ta_bla,
max_soqeence_enng
main
aot tnp_ptaatale__oo__eeeet to. offeet]: sarootogitt_pr_iemee
(leagth_to_bin oftset)
zeset effaet in case best fit changed
offset
c1sc:
offset t=
1 Dees not fit anуиbаre, Create new pack. nax_sequence__t
sopatition but no desendence pack.
repezt nin poggccne__onntt///eoaoeeo whill iLLequence_____ii////eee
nex_scqucoesppor_pee
D:
not distrizuta:
repeat:
(Lanaacckkeertt_ooo__ooo repooa,, 2_sequences_ Laauunooos____DD///eeeeee
cxp_ccsassaaee_oor__iaa stratoolos_pe__engg
mak.sequenos_perraadd. max_sequencw, length-length zen
49

---

Under review as a conference paper at ICLR 2023
narga acratogies
for xey in tmp_stratecies__ce peeeddss_pe__engttt
cccatogles_por_toe (ey.
flacten
dictionary
strategy_sot
strategy stratcgy_ countt [] postocy_ropett_ccomt
for key stsaeeisopper_eeentti
pack.severrae)
strateqy_set aappnddd (pack)
Bunnarize officioncy
Suration tine,tim:() start
sequenow_ ng-arange (3, nax length
stratesy_
ratgial )
sid_mmbbes_ot_ee of__ange bistogram.
cev_number_or_eamppee stratoy_oopst_eout..co in
sequenows ([oonnt
for atsa:egy_aet]]p
siptaraleey_spee.eeoo tozal_ nak nex_sequense__enee
nex_nunbor__r__mmple
topby_tokens ([coun) aeex_s Lengg s.m(pack)) fur gount, pack
acsategy_
afticiancy
anpty_tokana totai_tokena
speedup uppe bound 1.0/11 (histogrrass
- lengcha
max_seeuenc___ege lenct()) .san)) of
pe print (7 ing afficiency [fract ian of real loberals (efficinncr3.443
21soadduup thecretioal Himit: [spaedap apper 3oand:3.44))
StAchleved speed
packed dataset: fold number. of cample//ees.meee mumber of xamplex::.
2f Patked (old sangleel sequences [durat seconds.")
return st sereeegy_ set, strategy. repeet mount
50

---

Under review as a conference paper at ICLR 2023
Listing 9: Extended non-negative least squares histogram-packee
Lmpozt Eina
regort nunpy op
from acipy sapuel optiniss, stats
Zzon Funetools import isa_eache
gwi.paakinggnnte falaaaeeeyy mww_sequenoe cun_acsatacies (strattocyy__)))
= opraeros (nex_sequeeee wngth, nun rggeeee dtypeeng, 32) Tax atzategy in enunerate Gelrateoyy_at);
seg strategys
Alseq len
sucuen
2leucceche (maxii
wws.paakkng_utssaaeiiee jatatt mininun_inerement,, Langet_ depth) gep terget_ length length
stralngies
Complete packing exectly
depth
if yeg >- minimun incremenl:
strategies agpend (gspl)
Complete serple "depsh" steps, recursively
elaez
For new in range enngeaninimmn increment, gap 1);
new_gep target. target__lnggt seart_leength
new_sep strategiee..pperddlll
elaet
options htt_paccinngstsstttteeee
option in options:
If len copt
strattgiss.appenne [ option)
strategies
det pack psingusing wwsingnennssteeeeeooeooeeessssse canisty thistogran, nax sequence Leagto, leagta, nax mxx_eequeness Ber___pee___________ pack):
List all unique ways of pascing to the desired neximun sequence length
print (e"Fackin pet_packin__sratee strking_strttogeesie
involve (len(errategy.
unique packing strategies.")
Get the packing estrix corresponding wew.eeeooc__eongeeeeeee
this Hist packing strategies
boosinggnrriixtttseeee _cct,
Meights that
numbe resulting peoding for range sequerce (ergeh)) ())
residual
np-array
construct the packing natrix
A bar zeres (taosst2maxx_eeeee weq.eneeeeeeeeeeoeoo.ooo length, ler (strategy_oos set) max www_eeeuuene__eeeee (dr) weichted natrix
bar (taax__oquencce_ueeeoo ionghec._____..gh Lecilstrotog__eet!
ap.oxpand__inm (vG, Higher weight to avoid posisive residuel
bar wtw.ccccs___eeerrttaa.
scaistratoqy__ee
(p.e
20*v6anp (eaxx_(eeeeeee wew_eepeer___ceneeeee Length/l_
begative diegonal unity
for nepping
A (eoxmmooosseeeeeo poox_cquuec jonroooooccc.eeerttt.. Jentthi, ien (ctrattoy_scc) ap. ap..xxand_dimg
10*w6anp ones (tw. (e__eeueenc__ennnt))) -poee. (mmxx
Apply voigating to histsgran
b barl requence. Lengtcc.__ennhhh..ooo x0 histogron
bar (nox__oquano__eeeeeeeee Jengthi; 10.==vap.cnes
[eax__oquanc__lengn3 [
histogran
the packing problom.
(ereqqunnee pack: histogram.com
stazt tins.timen
mnom optimize bar, b_baz]
(E non-neсacive least squares took [tine.cimed] start:3.25) seconds."i Round the fleating point soluticn to aearest integer peattay__epea___oou ri.riat
(np_1nt54)
the sesiduals, stratogy Erratogy_ropcst___ wtt.est___eccttttttt_eeeeeeeeeee sesideal histogran
Bandle the safc-over sequences 1.e. pesitive pazt of resideal sapackod_segien ap.ezange max_scquence__ergtt. Jenqut. [residual > for ungacked__cqiien
atzataoy ([2 nax_soquence Lengghhno__enghhh.. 11)
desch strateey
scrstcoy_Andox Stratecy_set. indxx
alcaleoy reppat [atcalegy index] 1e [1-1due][-11]
Ba-canpute residual with updated susater__spaat_comt
This should now stristly sesidual histogran A www.tty___wwa__ooo
add padding based on defici: (nsgative residcal postion of zesidual)
padsing
(resides)
0:
Calcuiate
atarissios
lengths no ng.arang C,, max_sequen:o_ientt) +
mutber sanples biatoggtan, sun()
rav_munbes_ee sangges [a: lnc_/ssseeeoy.eeett.oooo peoadu__uppar_boo
1.0/(1 (bisccoran=
sequence_ lengi mwx_segaeneee.. aequenoe__eegg Jength)) (mggt)))....
.am)) ssan)) (ammt//a pot_a/aaabbrooo__oooooo
cun_padding tokddaan_tkeen_ppaceeee
(aequenca_ lengtis padding) aaunt)
atricioncy non_osdiie_ccoonn_ooooo
(2 ing afficiency (frac: ian real Loberal
215ooed-up thscretioal Hinit: Iapaedap_ boadd bww.d:ooddd...m.. 3.21:344410 Aa),
#tachleved speed-in
pecked dstasets fold mumorr of xamp les wn/new mumber swamp p 55))))
sell, pepala
51

---

Under review as a conference paper at ICLR 2023
APPENDIX REFERENCES
[36] BELOV, G., AND SCHEITHAUER, G. A branch-and-cut--nd--iee algorithm for one- dimensional stock cutting and two-dimensional two-stage cutting. European Journal of Opera- tional Research 171, (may 2006), 85-106.
[37] GAREY, M. R., AND JOHNSON, D. S. Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., USA, 1990.
[38] GUILLÉN, G., DIAZ-CAMINO, C., TORRES, C., APARICIO-FABRE R., HERNÁNDEZ-LLÓPEZ, A., DÍAZ-SÁNCHEZ, M., AND SANCHEZ, F. Detailed analysis of putative genes encoding small proteins legume genomes. Frontiers in Plant Science 4 (2013), 208.
[39] HANSEN, H. B.., DAMGAARD, P. B., MARGARYAN, A., STENDERUP, J., LYNNERUP, N., WILLERSLEV, E., AND ALLENTOFT, M. E. Comparing ancient dna preservation in petrous bone and tooth cementum, PLOS ONE 12, (01 2017), 1-18.
[40] KoTZ, S., AND NADARAJAH, S. Extreme Value Distributions. World Scientific Publishing Company, 2000.
[41] LAWSON, C. L., AND HANSON, R. J. Solving Least Squares Problems. Society for Industrial and Applied Mathematics, jan 1995.
[42] LUO, Y., AND DURAISWAMI, R. Efficient parallel non-negative least squares on multi-core architectures. SIAM Journal on Scientific Computing 33 (2011), 2848 2863.
[43] NVIDIA. Performance catalogue for BERT on Pytorch. /tttps://ngc.vvidee com/
for wytoorhh/perrornmaaaa..
2021.
[44] PENG, Y., YAN, S., AND LU, Z. Transfer Learning in Biomedical Natural Language Processing: An Evaluation of BERT and ELMo on Ten Benchmarking Datasets. In Proceedingg of the 2019 Workshop on Biomedical Natural Language Processing (BioNLP 2019) (2019), pp. 58-65.
[45] VIRTANEN, P., GOMMERS, R., OLIPHANT, T. E., HABERLAND, M., REDDY, T., COURNA- PEAU, D., BUROVSKI, E., PETERSON, P., WECKESSER, W., BRIGHT, J., VAN DER WALT, S. BRETT, M., WILSON, J., MILLMAN, J., MAYOROV, N., NELSON, R. J., JONES,
E., KERN, R., LARSON, E., CAREY, C. POLAT, I., FENG, Y., MOORE, E. W., VANDER- PLAS, J., LAXALDE, D., PERKTOLD, J., CIMRMAN, R., HENRIKSEN, I., QUINTERO, E. A.,
HARRIS, C. R., ARCHIBALD, A. M., RIBEIRO, A. H., PEDREGOSA, F., VAN MULBREGT, P., AND SCIPY 1.0 CONTRIBUTORS. SciPy 1.0: Fundamental Algorithms for Scientific
Computing in Python. Nature Methods 17 (2020), 261-272.
[46] WOLF, T., LHOEST, Q., VON PLATEN, P., JERNITE, Y., DRAME, M., PLU, J., CHAU-
MOND, J., DELANGUE, C., MA, C., THAKUR, A., PATIL, S., DAVISON, J., SCAO, T. L.,
SANH, V., XU, C., PATRY, N., McMILLANN-MIOR,, A., BRANDEIS, S., GUGGER, S.,
LAGUNAS, F., DEBUT, L., FUNTOWICZ, M., Mor, A., RUSH, S., SCHMIDD, P., Cis- Datasets. Gitllub. Note:
TAC, P., MUŠTAR, V., BOUDIER, J., AND TORDIMANN,
/ (2020).
[47] WOLFRAM RESEARCH INC. Mathematica, Version 12.2. Champaign, II, 2020.
52


Reviews:
[{"review_id": "buYVzn3HBd4", "reviewer": "Reviewer_cSJD", "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": "", "summary_of_the_paper": "This paper tackles batching and padding, a core procedure in training machine learning models. It argues that conventional solutions (padding to the max sequence length in a minibatch) may result in 50% of the training data being paddings, substantially wasting the compute. It proposes several techniques to address this problem: better packing of the training sequences, modifications to the transformer architectures, and adjustments to the established hyperparameters. Experiments of training the BERT model show that substantial speedup can be achieved with the proposed technique.\n", "summary_of_the_review": "\nSummary:\n- While the proposed method can be useful, further evaluation is needed to validate its effectiveness. I encourage the authors to consider submitting to some ML system venues, which can be a better fit than ICLR.", "strength_and_weaknesses": "Strength:\n- The paper is fairly clear and well-motivated. \n- The proposed technique can be useful for most practitioners. \n- General guidelines for adjusting existing hyperparamters.\n\nWeaknesses:\n- As a machine learning research paper, the technical contrition is thin. Some venus on MLM systems might be a better fit.\n- I’m not an expert on this, but I feel that existing work must have tried to address this issue, but the paper does not compare to any baseline.\n- The claim is not well supported by the evidence: (1) the paper claims “without impacting performance,” but the only evaluation on accuracy seems to be MLM training accuracy (in terms of word prediction?); (2) the paper fails to acknowledge that the proposed method may not work for neural models other than transformers (e.g., I cannot figure out how to make this work for RNNs)\n- The results are based on IPU, a kind of accelerator that most practitioners probably don’t have access to. This casts some shadow on the paper’s reproducibility, and limits its impact.\n- It is not entirely clear how the “theoretical speedup” is determined. Is it simply 1 divided by the ratio of the real tokens? I don’t think this is correct: transformers have quadratic-complexity components. As an illustrating example, I do not think the time of processing a 512-length sequence is twice that of a 256-length one. \n\nDetails and further comments:\n- End of section 2: please 2.2$\\times$, instead of 2.2$x$.\n- 4.2.1: what is the task? Is it word prediction on the training data (that no one cares about)? I would strongly encourage evaluate on downstream tasks.\n - I would appreciate it if the authors can try (1) other tasks such as text generation, and (2) other pretrained LMs. \n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "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": {}}, {"review_id": "MlHH8HTJMZ-", "reviewer": "Reviewer_PH3R", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "", "summary_of_the_paper": "This paper proposes two algorithms for packing multiple token sequences into batches so as to minimize the amount of padding required. It also describes Transformer-specific techniques for ensuring that sequences within a packed batch are handled completely independently (no information leaks across batches). Experiments with BERT show speedups of almost 2x compared to unpacked batches, with no degradation in model performance.\n", "summary_of_the_review": "I am leaning slightly against acceptance because this seems to be mostly an engineering contribution, and one that is more relevant to older, smaller models. Although such models are still in common use, the training costs of more recent large LMs are so much bigger that they make gains on smaller models seem less important.\n", "strength_and_weaknesses": "Strengths:\n\n1. The proposed techniques are straightforward to implement, and they work well.\n\n2. The experiments are solid, with particular attention to details such as the effect of breaking the iid assumption when packing.\n\nWeaknesses:\n\n1. The contribution seems a bit thin. Although two algorithms are proposed, the simpler of the two (sort sequences by length, allocate by decreasing length to batches with the most space remaining) basically works as well as the more complex matrix formulation, and doesn’t come with the additional restriction of max 3 sequences / batch due to computational constraints. That algorithm is quite obvious, as are the techniques to modify position embeddings and attention to ensure sequence independence.\n\n2. The work is mostly relevant to models such as BERT, which use sentence inputs. More recent models such as GPT-3 and PaLM use much longer sequences, and avoid padding by just concatenating and truncating documents. Larger capacity models also mean that special masks aren’t necessary to distinguish examples, as they can learn to split on just a separator token.\n\n3. Although the paper was quite clear for the most part, it would benefit from a distinct problem definition at the beginning of section 3 that defines terms and gives the inputs and outputs from the algorithm. Some of the descriptions were a bit unclear, e.g. in 4.1 it would be good to have a better definition of sorted batching in the main paper, and also an explanation of how greedy is different from packed BERT.", "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": {}}, {"review_id": "JMYxNQi0fFp", "reviewer": "Reviewer_tpoA", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "", "summary_of_the_paper": "This paper explores efficient packing methods for training sequences of BERT,  which avoids the padding tokens to speed up the training.\nThe authors introduce 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 model performance.  Experiments on the Wikipedia dataset show that the proposed method can achieve 2x speedup while achieving similar training loss.\n\n", "summary_of_the_review": "This paper designs shortest-pack-first histogram-packing (SPFHP) and non-negative least-squares histogram-packing (NNLSHP) algorithms to avoid the padding tokens and speed up the model training. But the technical contribution of this paper is limited. This work seems to be a system paper and the contribution might be not significant enough to publish at ICLR. Some strong baselines should be considered.", "strength_and_weaknesses": "Strengths:\n- This paper designs shortest-pack-first histogram-packing (SPFHP) and non-negative least-squares histogram-packing (NNLSHP) algorithms to avoid the padding tokens and speed up the model training.\n\nWeaknesses:\n- The technical contribution of this paper is limited. Packing is a common technique and has been widely adopted in the official deep learning frameworks, including tensor2tensor and Fairseq. This seems to be a system paper and the contribution might be not significant enough to publish at ICLR. \n- A simple packing technique is to sort sequences by length and merge near-length sequences into one mini-batch. Then it further leverages dynamic batch size to maintain a similar token number for each mini-batch, which significantly speeds up the model training. This paper lacks detailed comparisons with this simple baseline.\n- Currently, dynamic sequence length is supported in CUDA libraries, which may limit the application of the proposed algorithms. \n\nDetailed Comments:\n\nOverall, this paper is easy to follow and this idea is straightforward. But the technical contribution of this paper is limited. This work seems to be a system paper and the contribution might be not significant enough to publish at ICLR. \n\nPacking is a common technique and has been widely adopted in the official deep learning frameworks, including tensor2tensor and Fairseq. For example, a widely used packing technique is to merge near-length sequences into one mini-batch and then adopt dynamic batch size to maintain a similar token number for each mini-batch. It could achieve significant speedup during model training and there is no detailed comparison with this baseline. In addition, the dynamic sequence length of RNN or Transformer is supported in CUDA libraries, in which the CUDA libraries avoid the computation of padding tokens when given sequence length. This way limits the application of the proposed algorithms and this paper lacks correspondent comparisons between the proposed method and dynamic sequence length.\n\n\nQuestions for the Author(s):\n- I would like to know the details of the sorted method in the paper. Does it adopt dynamic batch size to maintain a similar token number for each mini-batch?\n- Currently, dynamic sequence length is supported in CUDA libraries. How about the differences between the proposed method and dynamic sequence length?\n", "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": {}}, {"review_id": "HDESbPIdIU", "reviewer": "Reviewer_1zai", "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": "", "summary_of_the_paper": "The authors are interested in studying the impact of the packing strategy on BERT’s training and performance.\n\nThe authors first observe that the variation in sequence lengths in nlp datasets used for pre-training (such as Wikipedia) can yield a very large amount of padding tokens (50% reported) which means a lot of compute is wasted on padding tokens.\n\nThey propose two heuristics for creating packed sequences taking inspiration from the operational research literature which can scale to very large datasets.\n\nBy adjusting the positional embeddings, the attention masks, and losses, the authors show that the packed sequence training is equivalent to the original non-packed BERT training both in terms of downstream performance and training convergence.\n", "summary_of_the_review": "Overall, this a solid study of well-posed problem, with limited technical and empirical novelty,", "strength_and_weaknesses": "Strengths:\n- The problem is well-posed and relatively well-motivated. This is an important problem that has consequences on a large class of current training schemes and models in NLP but also consequences in training practices outside of NLP.\n- Experiments are relatively straightforward and well constructed, and results are convincing.\n\nWeaknesses:\n- Usage of BERT as a baseline is not well motivated (does it have to do with MLPerf benchmark?). More specifically, several choices in BERT training have been questioned in the RoBERTa reproduction such as the need for 2 phase training (first on short sequences and then longer sequences), the very big batches, the NSP auxiliary loss… I think the experimental setup could be considerably simplified (and more actual).\n- Downstream evaluation performance is somehow weak and not exhaustive enough (only squad performance is reported). I think a minimum of 3 qualitatively different tasks would be enough to convince the reader that the trainings are equivalent. Matching training curves (Figure 3 and 4) seems like only a “sanity check”.\n", "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:

Decision: Reject