Efficient Sequence Packing without Cross-contamination: Accelerating Large Language Models without Impacting Performance
Authors: Mario Michael Krell
Matej Kosec
Sergio P. Perez
Mrinal Iyer
Andrew W Fitzgibbon
Venue: NeurIPS 2022 Submitted (2022)
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.

Efficient Sequence Packing without
Cross-contamination: Accelerating Large Language Models without Impacting Performance
Anonymous Author(s)
Affiliation
Address
email
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, 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 self-attention, by reduction 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-tiaining 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-training and fine-tuning practices.
11
13
15
Introduction
17
Many language datasets, including the de-facto pre-training dataset for BERT Wikipedia, 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 24 dataset generation process which, in BERT, attempts to "pack" together sentences so as to fill the sequence length as completely as possible N We improve this process whole-dataset level.
18
20
21
22
26 We show that, even after this pre- pre-processing, padding tokens represent 50% of all tokens of the Wikipedia pre-training dataset at sequence length 512. Thus, by avoiding processing the padding tokens one can get 2x speed-up for phase 2. Overall, the lengths range between tokens up to 512. Samples of length 512 represent only 23.5% of the dataset,
27
28
Beyond the simple batching, other solutions have been addressed in the literature, and in open-source 31 software implementations. When processing sequences, most libraries and algorithms mention
32 packing as reference to concatenating sentences from the same document (BERT) or from different
33
documents (BERT, T5 24 GPT-3 [4] and RoBERTa [6]] as they arrive (GREEDY) from the
34 source dataset to generate the training dataset. None of the respective papers addresses the packing
Submitted to 36th Conference on Neural Information Processing Systems (NeurIPS 2022). Do not distribute.

---

35
efficiency, i.e., remaining fraction of padding. To "separate" sequences from different documents, separator token introduced. However. this not sufficient and can have a 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%. Alternative common approaches to overcome the large amount of padding in many datasets are "un-padding" as in Effective Transformer [5] and sorted batching (SORT) as in Faster Transformer [2I. lingvo 23 fairseq [22], and RoBERTa. However, for running efficiently arbitrary accelerators, these approaches require substantial harewfie- low-level code optimizations only available on GPUs, Further details are in Sections C and 4.4
36
37
38
39
40
42
43
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 (PyTorch Geometric) combines multiple small graphs in batch to account for the large variation in size and to optimize the hardware usage when training Graph Neural Network (GNN). Another example is the RNN implementation in Py Porch 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 implemented an efficient manner while avoiding interaction between sequences. Even though 51 we focus on BERT 6 and other transformers in this paper, the general principles can be transferred
44
45
46
47
48
50
52 to many more machine learning algorithms with differently sized data samples.
53 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.
54
55
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 3.1 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 describe 'cross-contamination" -the cause of the accuracy reduction which separator tokens do 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 nearly-optimal packing scheme for Wikipedia pre-training dataset (Section 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-packed dataset with 2x throughput increase on the Wikipedia sequence length 512 pre-training dataset. Further experiments underline the necessity and
57
58
59
and Section
3.3 we
80
61
62
63
64
65
66
efficiency of our changes.
Sequence length distributions
68
shsorofical spreS-up 1,230
Useeretica max www.dupp........ 1,242
Beoorticcll max 30sedhat: 2.00
Cola
304
p0bbasitty secodity
5.533
603
E432
E43L
Scauence longts
Segganse kougth
SenseTIc Fergth
Sequence longth
Loce
Look
Lock
030
50 1N
24
14
200 23 24
12
25
Figure 1: Sequence length distributions for different datasets. The three graphics 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 to not using any padding tokens and not having any overhead from processing the different lengths. Top right: GLUE datasets. Bottom from left right: SQuAD 1.1, LibriSpeech text labels, LibriSpeech audio token sequence, and QM9 molecules of a graph in a sequence.

---

69
BERT is pre-trained using masked-languaat modelling and next-sentence prediction on a large corpus of Wikipedia articles. Each sequence composed of one <CLS> token followed by the first "segment" of sentences, followed by a <SEP> token, and then finally the second "segment" of sentences. Because these "segments" are created in sentence-level increments there no token-level control of sequence length. Furthermore 10% (default value, 77) of sequences are intentionally cut short. This leads to significant levels of padding, especially for longer maximum sequence lengths (see Figure ! and Section M.M. At sequence length 128 (commonly used in phase I 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.
70
71
72
73
74
76
78
80
81
82
Note that the skewed sequence length distributions are neither limited to Wikipedia, as shown with GLUE 30 31 from Section II and SQuAD 1.1 2 from Section K I (2.2z speed up). to BERT training. as shown with LibiSpeech text distributions P from Section M I. nor to text itself,
83
84
given the LibriSpeech audio data distributions, and the QM9 molecular data 127 26 (1.6z speed-up,
86
Section O I. D. 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.
88
3 Methods
89
90
Our approach consists of three distinct components. Firstly, we pack the n data samples efficiently during pre-prceessing to make full use of the maximum sequence length, s. (Sections 3. and [ Secondly, we introduce series of model changes in Section 3.2 that preserve the equivalence with
91
93 the original BERT implementation. The changes include a self-attention mask to prevent the model
94 from attending between different sequences in the same pack (Section 3.2.2). and an adjustment
95 of the the positional embeddings (Section 3.2. to handle packs of sequences. Other components of the model, such as the feed-forward layer 22 operate a per-token basis and do not require
97
modification for pre-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.3) that lead to analogous convergence behavior between the packed and un in-packed BERT implementations. Additional videos and animations are provided as supplemental material.
99
100
101
102
3.1
Packing algorithms
103
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 is strongly NP- No-complete [14, numerous approximate
104
105
106
solutions have been proposed [I2] [5 [K] (6). Since most existing approximations have a high complexity of at least On log n),, we propose two new heuristic offline algorithms that are tailored
108
to the NLP setting applied to the whole dataset. For a detailed introduction to packing see Section
109
3.1.1 Shortest-pack-fun histogram-packing (SPFHP)
110
Shortest-pack-fire histogram-packing (SPFHP) works on the bins in the sequence length histogram (with bin size 1) rather than the individual samples. The histogram is traversed in sorted order from longest to shortest sequences. Then, to pack the data during the traversal. we apply the worst-fi fit such that the histogram bin being processed goes the "pack" that has the most space remaining ("shortest-pace -pccktsstp.ck-iisstt".......))") 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 it is not already at maximum packing depth. The detailed code for the algorithm is provided in Listing 3 The time and space
111
112
113
algorithm 12 36
114
115
116
117
complexity of the algorithm are O(n + 8%) and (s²)) (Section II..
We avoid the ambiguous terms "bin" and "sample/seqqence""ne and use "pack" instead to refer to the multiple sequences concatenated during packing.
3

---

119
3.1.2
Non-negative least squares seatogrra-pccckinn (NNLSHP)
120
The proposed NNLSHP algorithm is based on re-stating the packing problem as (weighted) non- negative least squares problem (NNLS) B] of the form WAr = wh where z 2 0. The vector b is the histogram containing the counts of all the sequence lengths in the dataset. Next, we define the A
121
122
123
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 column that consist of at most 3 sequences per pack (independent of b) and encode each strategy
124
125
126
of the sparse matrix A. For example, a strategy consisting of the sequence length 128, 128, and 256 in represented column vector that has the value 2 at the 128th row, the value 1 at the 256th row, and zero at all other rows. The variable z describes the non-negative repetition count for each strategy. So 24 in the ith row of z means that the strategy represented by the ith column of A should repeat 24 times. Moreover, in the un un-weighted setting, Az = states that we would like to "mix" " the defined strategies (columns of A) such that the number of samples matches the histogram b, and where each strategy is used x 2 0 times. We use the residual weight w to control the penalization of the Ax residual different sequence lengths (different rows of b). Heuristically, we set the weight of 0.09 for all sequences of length 8 or smaller because they are considered acceptable padding sequences while all other sequence lengths get weight 1. We discuss this heuristic choice of The overall efficiency of the packing is not greatly influenced
128
130
132
133
134
135
136
parameters in Section F.4.5 and F.5 I.
137
by the weighing (less than 1% extra speed-up).
138
After solving wAx = wh for x 2 0 using an off- shflff solver, we obtain a floating point solution, which means that the repetition counts not necessarily integers. Since we cannot use naturalll 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 On + s and ( 3 Further details provided in Section F.4
140
142
143
144
3.2
packedBERT: model changes
145
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, as well as being required by benchmarks such as MLPerfTM The presented approaches and principles apply to variety of other models.
146
148
150
3.2.1
Adjust positional embeddings
The BERT model uses three types of embeddings: token, segment, and positional embeddings. The latter is canonically implemented as a bias add operation, rather than a full embedding look-up. This is possible because the positional indices 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 2 and one of length 3, the positional embedding indexes that need to be picked up are j0, 1, O, 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
152
153
154
156
157
158
159
required adjustment has only minor impact absolute accuracy/loss (see Section 2 and
180
3.2.2
Adjust attention masking
input
maak ap.array([[s, 1, 1, 2, 2]1> # D, nask
Ungass pack Aegts
Lasaaco
sero_one_nwak tf tf..quul (mws,, maak. for with softewe_neek tf. (chere saro_onk_zank,, O, -1000)
Figure 2: Attention mask code [left]. respective zero-one mask [middle], and vectorized unpacking of the sequence loss(right]. White rectangles correspond to padding.

---

161
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 to implement in modern frameworks (see Figure 2 Naturally, there is a cost to both the mask construction and applying it to the attention matrix. However, it is required to keep the accuracy (see Table I Section 4.1 See also the code of the deprecated [ensor2tensor] library and our own provided code.
162
163
164
165
166
168
Section 4.2)
169
3.2.3
Adjust per-sequence loss and accuracy
170
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 a 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 a per-pack weighted loss. In other words, the overall loss on the micro-batch would sum-up the losses on the individual packs, rather than individual sequences. As result, the model would converge to different optimum than when running with the un- un-packed implementation. For instance, pack of single sequence would contribute to the loss with the same weight as pack of three sequences.
171
172
173
174
175
176
178
179
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 2 This minimizes the latency overhead of un-packing the loss calculation. As an example, we show how per sequene 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.
180
181
182
184
185
186
188
189
3.3
Adjust hyperparameters
190
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 the sentence level, the number of sentences in one batch increases
131
182
193
by the packing factor. Similarly, the number of tokens in one batch increases. Hence, hyperparameters that are sensitive to these numbers need be adjusted.
194
195 A direct solution is to reduce the computational batch size by the packing factor (average number of sequences per pack) and keep all other hyperparameters the same. For example, if the packing factor is 2. 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 it might imply under-utilizing the memory/compute, especially if the miero batch size needs be reduced.
196
197
198
199
200
201
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 [35] For packed dataset with a packing factor p. we update the decay parameters as: 31 := 3P. B3 := 3 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. show that this reduces convergence speed.
203
205
206
207
Since these adjustments are only heuristics the convergence of the model will comparable but not identical, In particular, it is unlikely that simply adjusting the hyperparameters will fully undo the impact of the increased batch size. However, with these adjustments, researchers should be able to continue to use existing configurations.
209
5

---

4
Experiments
211
212
4.1
Bin packing algorithm comparison
213
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 f'actor.. For SPFHP, we analyse different (maximum) packing depth, since packing is less efficient with smaller depth and we want to get a general understanding
215
216
217
218
219
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) [ (IPU-M2000, 16 accelerator chips), BERT phase 2 pretraining
220
221
222
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 excessive padding or continuous changes of the code, our approach can work with the same code for the whole dataset. So in this setting the IPU architecture would especially benefit from our approach since it avoids code changes. Nevertheless, it can be applied to any implementation on GPU or TPU. For determining the speed-up, we take advantage of the precompiled kernel. Since time measurements are quite noisy, we can profile the kernel and how 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.
223
224
226
228
many cycles it takes for processing a batch. That way,
230
232
Table I: Key performance results of proposed packing algorithms (SPFHP and NNI NNISHPP 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
210
GREEDY
<78
11.6
44.48
11.5
SPFHP
80.5
1.61
4.283
1.544
3
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 Section 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
233
The main results for the performance metric evaluation are displayed in Table 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-Fi-Decreeasnn requires 87-120s, 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
234
235
236
237
238
best speed-up up is obtained with NNLSHP at depth 3 which required 28.4 4s on the CPU for processing and ran out of memory for larger depth. With a value of 1.913, is close to the theoretical upper bound of 2.001. The results show that efficiency, packing factor, and speed-up can be viewed inter-
239
241
changeably. The amount of time needed to process sample (a pack of sequences) is barely changed relative to the un un-packed implementation. The packing factor, or the improvement in efficiency,

---

243
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 I00 and confirmed that our approach is hardware and software independent giving it a huge advantage over existing approaches.
244
246
247
248
249
4.2
MLPerfIM phase 2 pretraining setup: learning curves and hyperparameter adjustment
250
For depth I (classic BERT) and NNLSHP with depth 3, we additionally evaluate on the MI.PerfTM ver- sion 0.7 BERT pre-training benchmark [7]. Briefly, this involves training from a standard checkpoint to masked- laasked-lngguge model accuracy of 71.2% using 3 million sequences with a maximum length of 512 tokens (refer to [9] for details). Following this standardized benchmark supports reproduction of results even on other systems and makes sure that the reproduction effort is moderate and setup rules are clearly documented. We compare the resulting speed-up as well as the respective learning curves by evaluating the data on a held-out validation dataset. The objective of this additional evaluation is
251
253
255
256
257
to analyse if convergence behavior is changed by the packing strategy and if the theoretical speed-up can be achieved in practice.
258
259
With packing, we effectively increase the average batch size by the packing factor (+% 2). However, with 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, we 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.
261
263
285
287
268
269
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 is based on the reduction in the computational work needed to process the dataset. However, packing the data also reduces the latency of the transferring the data the device. Figure showows that the realized total speed-up up from packing exceeds 2r.
271
273
275
276
277
278
279
280
281
282
283
204
285
286
4.2.1
Ablation study
287 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 g 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 crucial to avoid reduction in performance.
289
291
292
of 72.1%. So overall, both adjustments
293
When running packed BERT without the NSP loss but keeping everything else the same in a full training setup, we observed that downstream performance on SQuAD reduced the Fl measure by 1.31% % and EM by 1.15%. Hence, we do not consider removing NSP as done in approaches like
295
RoBERTa and T5 discussed in Section!] II
7

---

3,5
patkes, ebs: 768"2. beter 0.81
packed, beta: 0.66
classic, beta: 0.81
3.5
classic bs: 3000, bete: 0.06
1500.
1.0
packed, 0.66, double fr
pacced, ebs: 150012, bete: 0.66
packed. 0.82, double
2.5
2.5
2.0
2.0
1.5
1.0
2.0
samples
Figure 3: Comparison of learning curves for packed and unpacked processing, where all experiments converged the target accuracy within the same number of training samples(3 million). [left] same effective batch size (ebs is batch size times packing factor), [middle] different heuristic adjustments of the hyperparameters (batch size 1500 for all runs, such that ebs for packed runs is 1500 * 2), and [right] realized speed-up from packing (in excess of desired 2x). Further learning curves are provided Section
O
training accuracy (percent)
70-
4
packed baseline pos. emb. adjustment
adjustment
63
training
80-
adjustment packed BERT baseline
x
55
pos. emb. adjustment
0
500
1000
1500
500
1000
1500
Iteration count
Iteration count
Figure 4: Comparison of learning curves with and without mask positional embedding adjustment in our packed BERT approach. The grey accuracy baseline to reach is 72.1%.
4.3
Full pretraining and SQuAD finetuning
298
Packing slightly violates the i.i.d. assumption of data. Thus, we have to check that downstream performance is not impacted by packing. This is especially relevant in 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, we 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
300
301
302
303
304
305
308
307
Section 4.2 For Phase 2, we use sequence length 384 since longer range attention is not relevant
309
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 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 the median of 10 different seeds, displayed in Table 3 They comparable to the reference ones in 3 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%).
311
313
315
Table 2: Measured speed-ups in BERT pretraining with packing.
Table 3: SQuAD 1.1 scores after BERT pretrain- ing with packing.
Model size
Sequence length
Packing factor
Realized speed-up
Model size
Configuration
F1
Exact
match
128
1.17
1.15
6
88.5
80.8
base
base
384
1.70
1.68
Packed
88.32
81.03
128
1.17
1.15
90.9
84.1
large
large
384
1.70
1.69
Packed
90.65
84.12
8

---

317
4.4
Scaling analysis: Impact of accelerators count
318
further advantage of packing over 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 to packing, where the attention matrix is computed in its entirety and then masked. Because of these additional savings, un-padding can exceed the theoretical upper bound for speed-up from packing (2.013 on Wikipedia). As result of the dynamic nature of the approach, the processing time with un-padding is different for each sequence in the batch, and the amount of time required to process a batch of sequences will be determined by the processing time of the longest sequence in the batch (with the sequences being processed in parallel). Furthermore, in the multiple accelerator setting the processing time on each device will vary depending on the sequences in the batch that it receives. Devices which finish early have to wait for the slowest device to finish before exchanging gradients. This boadiibalaance between the devices (and inside the batch) leads to a considerable
319
320
322
323
324
326
328
330
decrease in the speed-up from un-padding as the number of accelerators is increased (see Figure and Section ). In contrast, packing (our approach) is inherently load-balanced. The processing time each accelerator is independent of the content inside the batch received by the device. Any
332
338
334
number of accelerators can therefore operate in unison without having to wait for the slowest batch to
335
process (all per-device batches are equally fast).
6 1.913
1.800
1.700
$ 11600
1.500
1.400
theoretical upuar-bound
1.300
packing (our approach)
1.200
un-padding (Effective Transformer)
1.100
padding (common baseline!
1,000
1
16
128 512 1024
accelerators
Figure Comparison of the theoretical speed-up as the number of accelerators is increased.
Conclusion
336
Whereas packing is well known concept, this paper sheds new light onto it in multiple aspects. First, we 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 a lot of datasets and that in many cases, more than 2x acceleration can be achieved by removing 50% or more padding. Second,
338
339
340
provide two highly efficient packing approaches based on established solvers that leave almost no padding and that can tackle arbitrarily large datasets in a matter of seconds, in contrast existing approaches that are slow and suboptimal. Third, we demonstrate that without adjusting the sequence processing algorithm (e.g.. BERT) to the packed sequences, predictive performance reduced. Thus, we 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.
342
343
344
345
346
347
349
351 In the future, an interesting direction is the packing of images of different sizes help accelerate computer-vision applications. This is especially relevant given the recent advances in the use of transformer-based approaches in the computer vision domain, for example the visual transformer [33] Note that many images come in different shapes and resolutions and packing them can be new approach to tackle this diversity instead of casting them all to the same resolution and shape. Masking out the self- attention within transformers is easier to implement than avoiding cross-come contamaottiiinooon of
352
353
354
355
356
357
convolutions applied packed images. Future work should explore improving the performance of
other models (RoBERTa, GPT-3, T5) by avoiding contamination between non-contiguous segments
359
from different documents. Even BERT itself might benefit from avoiding contamination between the
two concatenated segments.

---

361 References
ANONYMOUS. Supplemental Material for "Efficient Sequence Packing without Cross-contamination: Accelerating Large Language Models without Impacting Performance', 2022.
365
364
[2]
BOTTOU, L., CURTIS, F. E., AND NOCEDAL, J. Optimization Methods for Large-Scale Machine Learning. SIAM Review 60, 2 (jan 2018), 223-311.
388
BRO, R., AND DE JONG, S. fast non Chemometrics 11,5 (sep 1997), 393 401.
least squares algorithm. Journal of
367
388
[4] BROWN, Т. B., MANN. B., RYDER. N., SUBBIAH, M., KAPLAN, J., DHARIWAL, P., NEELAKANTAN,
A.. SHYAM, P., SASTRY, G., ASKELL, A., AGARWAL, S.. HERBERT- Voss, A., KRUEGER. G.,
370
HENIGHAN, T., CHILD, R., RAMESH, A., ZIEGLER, D. M.. WU, J., WINTER, C., HESSE, C., CHEN,
371
M., SIGLER, E., LITWIN, M., GRAY, S., CHESS, B., CLARK, J., BERNER, C., MCCANDLISH, S.,
372
RADFORD, A., SUTSKEVER, I., AND AMODEI, D. Language Models are Few-Shot Learners. In Advances in Neural Information Processing Systems 33 pre-proceedings (NeurlPS 2020) (may 2020).
374
[5] BYTEDANCE INC. transformer 2021.
Effective Transformer.
375
378
[6] 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 (act 2019), 4171-4186.
379
380
[7] DEVLIN, J., CHANG, M. W., LEE, K.. AND TOUTANOVA, K. BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding. https://githis comm/goolee--/ooooooooooooooeoeo reee/ 2019.
382
[8] DEVLIN, J., CHANG, M. W., LEE, K., AND TOUTANOVA, K. Pre-training data creation script for BERT. https::/ //gtt////tttttttt/ee com/ data. pYL223, 2019.
383
384
[9] FEDUS, w.. ZOPH, B., AND SHAZEER. N. Switch Transformers: Scaling to Trillion Parameter Models with Simple and Efficient Sparsity. arXiv (jan 2021).
386
387 [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).
389
390
[12] JOHNSON, D. S. Near-optimal bin packing algorithms. PhD thesis, Massachusetts Institute of Technology, 1973.
381
[13] JOHNSON, D. S., AND GAREY, M. R. A 7160 theorem for bin packing. Journal of Complexity 1, (oct 1985), 65-106.
393
394
[14] KORTE, B., AND VYGEN, J. Combinatorial Optimization, vol. 21 of Algorithmms and Combinatorics. Springer Berlin Heidelberg, Berlin, Heidelberg, 2012.
395
[15] LEE, C. C., AND LEE, D. T. Simple On-Line Bin-Packing Algorithm. Journal of the ACM (JACM) 32, (jul 1985), 562-572.
397
398
[16] LIU, Y., OтT, M., GoYAL, N., DU, J., JOSHI, M., CHEN, D., LEVY, O., LEWIS, M., ZETTLEMOYER, I.., AND STOYANOV, V. RoBERTa: A Robustly Optimized BERT Pretraining Approach. arXiv (jul 2019).
400
[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. MLPerf: An Industry Standard Benchmark Suite for Machine Learning Performance. JEEE Micro 40, 2 (2020), 8-16.
401
402
[18] MENG, Q. CHEN, W., WANG, Y., MA, Z. M., AND LIU, T. Y. Convergence analysis of distributed stochastic gradient descent with shuffling, Neurocomputing 337 (apr 2019), 57.
404
405
[19]
MLCOMMONS. v0.7 Results. https: //ml httt:::://ccoommo/ commons. org en/ wrw//e//teeeeeeeee trainiriiinnniinnnnn normal- -07/ 2020. Result not verified by MLPerf. Throughput/speedup is not the primary metric of MLPerf. MLPerf name and logo trademarks. See www. www.rf.pffff.mmmmmmmmmmmmmm org for more information.
408
10

---

408
[20]
NVIDIA. Reference numbers for BERT un-padding results.
http://ttwww.oooo//oooooooaaaaaa Satpa:aaaaionn220002 06 wtt.ppyytooobrrreeope
braining_ressee rww.rrssessss.e.
410
result_ txt 2020. Throughpuu/speedup not primary metric of MLPerf. MLPerl name logo
411
are trademarks. See www.wwwwpe........... ww..perf..oo. org for more information.
412
[21] NVIDIA. Faster Transformer.
413
master Saster/PaaterTrrnsfforrerr
2021.
414
[22] OTT, M., EDUNOV, S., BAEVSKI, A., FAN, A., GROSS, S., NG, N., GRANGIER, D., AND AULL, M. fairseq: A fast, extensible toolkit for sequence modeling, In Proceedings of NAACL-HLLT 2019:
415
Demonstrations (2019).
[23] PANAYOTOV, V., CHEN, G., POVEY, D., AND KHUDANPUR, S. Librispeech: 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.
419
420
[24] RAFFEL, C., SHAZEER, N., ROBERTS, A., LEE, K., NARANG, S., MATENA, M., ZHOU, Y., LI, AND LIU, P. Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer. Journal of Machine Learning Research 21 (oct 2019).
421
422
423
[25] RAIPURKAR, P., ZHANG, J., LOPYREV, K., AND LIANG, P. SQuAD: 100,000+ questions for machine comprehension of text. In Proceedings of the 2016 Conference Empirical Methods in Natural Language Processing (Austin, Texas, Nov. 2016), Association for Computational Linguisties, pp. 2383 2383-2392 2392.
425
[26] RAMAKRISHNAN, R., DRAL. P. O., RUPP, M., AND LILIENFELD, O. A. Quantum chemistry structures and properties 134 kilo molecules. Scientific Data (2014).
427
127] RUDDIGKEIT, L., VAN DEURSEN, R., BLUM, L. C., AND REYMOND, J.-L. Enumeration of 166 billion organic small molecules in the chemical universe database gdb-17. 17. Journal of Chemical Information and Modeling 52, 11 (2012),
429
430
PMID: 23088335.
431
[28] SHEN, J., NGUYEN, P., WU, Y., CHEN, 7.,, ET AL. Lingvo: a modular and scalable framework for sequence-to-sequeece 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..
435
436
p. 6000 6010.
437
[30] WANG, A., SINGH, A., MICHAEL, J., HILL,, F., LEVY, O., AND BOWMAN, GLUE: multi-task benchmark and analysis platform for natural language understanding. In Proceedings of the 2018 EMNLP Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP (Brussels, Belgium, Nov. 2018), Association for Computational Linguistics, pp. 353-355.
438
[31] WARSTADT, A.. SINGH, A., AND BOWMAN, S. R. Neural network acceptability judgments. arXiv preprint arXiv: 805. /247| (2018).
[32] WOLF, T., DEBUT, L., SANH, 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 Empirical Methods in Natural Language Processing: System Demonstrations (Online, Oct. 2020), Association for Computational Linguistics, pp. 38
444
445
446
448
[33] WU, B., XU, C., DAI, X., WAN, A., ZHANG, P., YAN, Z.,, TOMIZUKA, M., GONZALEZ, J., KEUTZER, K., AND VAJDA, P. Visual transformers: Token-based image representation and processing for computer vision, 2020.
450
451
452
[34]
XLA, T. XLA: Optimizing Compiler for Machine Learning. https://www..eesorfoo 2021.
453
454
[35] YOu, Y., LI, J., REDDI, S., HSEU, J., KUMAR, S., BHOIANAPALLI, S., SoNG, X., DEMMEL, J., KEUTZER, K., AND HSIEH, C.-J. Large Batch Optimization for Deep Leaming: Training BERT in 76 minutes. arXiv (apr 2019).
[36] YUE, M., AND ZHANG, L.. simple proof of the incquality MFFD(L) PT(L) +1, for MFFD bin bin-packing algorithm. Acta Mathematicae Applicatae Sinica 11, 3 (jul 1995), 318-330.
458
11

---

Checklist
459
480
1. For all authors...
461
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] Our paper has four main claims. First, in Figure [ we show the sequence length distribution of Wikipedia and many other datasets and the excessive padding that they require. Second, in Section 4. we show that we can efficiently pack the data which can be easily reproduced with the shared data and code M. Third, in Figure rightt, we clearly show the 2x performance gain from packing and the related hyperparameter adjustment scheme. Fourth, multiple additional experiments downstream tasks, ablation studies, and packing variants further verify the validity of our proposed approaches.
462
463
465
467
489
470
(b) Did you describe the limitations of your work? [Yes] We see three potential limitations that we discuss in the paper. First, as stated in Section A "Broader Impact" in the appendix M. our approach is clearly dependent on the sequence length distribution of the dataset. However, we looked into several other datasets beyond Wikipedia and observed even higher potential for acceleration and document this in multiple sections throughout the paper well as in the appendix [. Second, we explain our focus on the IPU hardware in Section 4. Our theoretical analysis in Section 4.4 indicates that our approach benefits also GPUs. We also cite other work, that shows that our approach is hardware independent. Third, our changes to the network with modified attention mask and loss calculation come with some overhead. This is addressed in Table || [overhead column] in Section [.]
472
474
476
478
479
480
481
(c) Did you discuss any potential negative societal impacts of your work? [Yes] We address this point in Section A "Broader Impact", third paragraph, in the appendix (1
482
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
484
485
2.
If you are including theoretical results...
486
(a) Did you state the full set of assumptions of all theoretical results? [Yes] Detailed algorithm explanations, clarifications of assumptions, and proofs are provided in the supplemental material (.
487
488
489
(b) Did you include complete proofs of all theoretical results? [Yes] Sections D and
490
in the supplemental material [ provide the necessary derivations on theoretical
491
results.
492
3. If you ran experiments..
493
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes] All packing code is provided in the paper. The packing results on BERT got verified by multiple independent parties. One party used draft of this paper to successfully reproduce its main findings. Links to implementations in three different frameworks will be provided after acceptance, to avoid violating the blind submission rules.
494
495
496
497
498
499
(b) Did you specify all the training details (e.g.. data splits, hyperparameters, how they were chosen)? [Yes] In the first part, we follow the MLPerf 0.7 benchmark rules. We document the parameters that we changed and why we change them. For the downstream tasks, we follow the reference and report where, how and why we change hyperparameters.
500
501
502
503
504
(c) Did you report error bars (e.g., with respect to the random seed after running exper- iments multiple times)? [No] The packing algorithms are deterministic and have no error. Other experiments are only executed once to compare convergence curves. For downstream tasks, we report repetition details and the median as in the reference.
505
506
507
508
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [Yes] We used 16 Graphcore MK2 IPUs for acceleration on an internal cluster.
509
510
511
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets... (a) If your work uses existing assets, did you cite the creators? [Yes] Appropriate references to the BERT authors, all datasets, and the code snippet from the HugginFace inc, are appropriately referenced with citations and links.
512
513
12

---

515
(b) Did you mention the license of the assets? [Yes] For the only taken code snippet, the license is part of the file [Listing M. Dataset licenses like Wikipedia's "Creative Commons AtriibtionnShhae-Aee Alike 3.0 License" are covered by the references. New materials like packing code and histograms will be provided under an MIT license which will be added over link to the resources in the final paper version.
516
518
(c) Did you include any assets either in the supplemental material [Yes] New materials like packing code and histograms are included in the supplement document well separate file. To avoid violating the blind submission rules, they will be linked in the final version like many other assets which are already publicly available under MIT license.
URL?
521
523
625
(d) Did you discuss whether and how consent was obtained from people whose data you'l 're using/curating? [N/A] We did not curate other people's 's data. We only provide very high level aggregate the used data.
527
528
(e) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [N/A] We did not curate other people's 's data.
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A] Our experiments did not include crowdsourcing or human subjects. (b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A] Our experiments did not include crowdsourcing or human subjects.
532
535
535
536
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A] Our experiments did not include crowd- sourcing or human subjects.
538
13


Reviews:
[{"review_id": "SP3fEgzoE6L", "reviewer": "Reviewer_ysRz", "summary": "This paper describes an approach for packing sequences into batches in order to improve the training efficiency of large-scale language models (and related tasks). \nFirst, several datasets are analyzed with respect to their sequence length variations and the potential speed-up if batches were packed with minimized padding. The paper then formalizes the packing problem and proposes two new algorithms, that in turn require slight model adaptations for the example of BERT. In experiments on BERT pre-training, they showcase the packing efficiency on IPUs and resulting realized speed-up in comparison to other packing (or none) algorithms, and investigate required hyperparameter changes on the MLPerf benchmark. An ablation study of the model adaptations of BERT confirm that these are indeed necessary, and that packed pretraining does not negatively affect fine-tuning (non-packed) on the SQuAD benchmark.", "questions": "1. Which BERT pre-processing is referred to in Section 1 (line 23)?", "limitations": "The authors mention more challenging applications in computer vision as a next step, and potential difficulties with the implementation. I'd appreciate if the limitations of the current approach would be discussed in more depth: are there any edge cases where the overhead would be prohibitively large? In which data conditions should this packing approach be avoided?", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. The paper sheds light on a problem that has previously been hidden in NLP implementations and has not been clearly documented/researched/discussed, despite its effect on required training resources, hyperparameters, and model quality. The paper is educational for anyone who has not delved deeply into this topic or has not implemented packing themselves (like myself included), and brings transparency into the choice of packing implementations and their impact.\n2. As the paper outlines in Section 2, the potential gain of efficiency is large, since sequence length varies a lot in many NLP tasks. The proposed solution is therefore a very impactful contribution to NLP implementations, thereby the efficiency of NLP research. \n3. The empirical results are strong, with theoretical speed-ups being close to be realized with little overhead.\n\nWeaknesses:\n1. Packing is only applied during pre-training, not during fine-tuning. Adding an experiment on top of the existing SQuAD experiments where packing is continued during fine-tuning would make the proposed approach more convincing, especially since Section 2 lists fine-tuning datasets for motivation.\n2. The experimental conditions for 4.1 are not well introduced. Is it BERT pre-training?", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "9TqegVtut1Z", "reviewer": "Reviewer_51Ua", "summary": "The paper proposes speeding large-scale pre-training by constructing the data pipeline with the explicit goal of minimizing the need for padding tokens, which only lead to wasted computation. The approach is to consider the dataset as a whole and apply bin-packing algorithms to merge several short examples into one longer example, which is done up-front as part of preprocessing. Two bin packing strategies (SPFHP and NNLSHP) are proposed and evaluated. Pre-training may be sped up by up to 2x compared to a naive approach.", "questions": "none", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The main strengths include, of course, the ability to achieve sizable speed-ups in practice. Moreover, the idea of having a whole-dataset preprocessing step aimed at optimizing it for accelerator use is a very general one. Bringing this to the attention of the community, and suggesting how to think about this in terms of concepts/terminology/abstractions, could lead to less computationally wasteful practices across the board in the field. It's especially helpful to see a quantitative analysis that reveals that padding is a big source of inefficiency in pre-training, where one might naively assume that it's not an issue because the underlying Wikipedia articles are actually quite long.\n\nIn terms of weaknesses, my immediate impression reading the paper for the first time is that many aspects of the idea of packing examples together are not, in fact, novel. The paper acknowledges that frameworks already concatenate short examples as a way to speed up training, and that this practice is commonly referred to as \"packing\". The claim in Sec 3.2.2 that the paper \"propose[s] directly masking the attention matrix\" is not novel either. (As prior art, see [tensor2tensor](https://github.com/tensorflow/tensor2tensor/commit/c9144dfa5f514cab529f487b069415daee5e211e#diff-3c271923bb62bdd35f3b0f6a2c94ea320825d834bbf51334a9acbc04fbea9763R538) for code essentially the same as Figure 2). Likewise for positional embedding and loss adjustment.\n\nIt seems that the actual novelty of the paper is in highlighting packing efficiency as a key criterion in designing a data pipeline, proposing to optimize this criterion at a whole-dataset level (instead of ad-hoc or streaming-based approaches), as well as showing that this can be done in a way that is scalable to large-scale datasets. At least for me, the writing of the paper did not succeed in delineating the scope of the contribution from what has been done in prior work. Additionally, the term \"packing\" has acquired a certain meaning in the context of modern transformer training, and I would recommend that the authors adopt distinct terminology to differentiate their approach. [Edit: to clarify, I am not referring to the use of the term \"packing\" in the title (which is fine), but usages like \"packed\" in Table 3 or even \"packed (our approach)\" in Figure 5. For example, looking at Table 3 / Figure 5 in isolation would be confusing to readers that have a different prior conception of what the term \"packing\" refers to].\n\nI also would have found it helpful if the paper had made explicit its assumption that packing takes place during an up-front pre-processing stage where the whole dataset is available for random access, and not in an on-line streaming manner. Approaches like padding and greedy concatenation would all work when streaming the data from storage one example at a time, while the proposed method does not. Even if engineering practice in the narrow area of pre-training does data processing up-front, the corresponding academic literature often doesn't necessarily go into this and sometimes presents a picture that leaves open an interpretation where padding/packing/batching or even tokenization are done via streaming processing.\n\nIn summary, the main weakness of the paper is how it frames the discussion for an academic audience, including how it contrasts its contributions from the literature as a whole.", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "5gLAhUBUAb1", "reviewer": "Reviewer_cYew", "summary": "This paper proposes two methods for reducing the padding tokens when packing multiple sentences into a single sequence: shortest-pack-first histogram-packing and non-negative least squares histogram-packing. Both these packing methods alter the input sequences provided to NLP models. As a result, the paper proposes basic alterations for BERT models so they can interpret packed input sequences correctly. With these changes, the paper demonstrates that a nearly 2x acceleration can be achieved versus a model using a naive token padding approach without any effect on performance.", "questions": "- The paper mentions that “The best speed-up is obtained with NNLSHP at depth 3 which required 28.4s for processing and ran out of memory for larger depth.”  Is there any data to support this claim? Are there circumstances where the approach would run out of memory when a depth of 3 is used?\n- On lines 288-290, the paper mentions that when not using an adjusted positional embedding calculation with one of its packing algorithms, “the accuracy stalls at 71.8% and does not reach the target accuracy of 72.1%.  So overall, both adjustments are crucial.”  However, when examining the percentages and Figure 4, this claim does not seem valid.  The need for the adjustment makes sense, but is there another reason why it is a crucial change? Additionally, in Figure 4, is there a reason the lines for “packed BERT baseline” and “no pos. emb. Adjustment” end before the line for “no mask adjustment” ends?\n- It feels as though an important metric is missing; for instance, why do “Faster Transformer [21], lingvo [28] fairseq [22], and RoBERTa” on line 40 all use sorted batching (SORT) to reduce padding tokens when it appears to be unviable given the results in Table 1?\n", "limitations": "n/a", "rating": 4, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n+ Potential broader applicability to many NLP tasks. While the paper mainly focuses the packing algorithms on BERT, it could also apply to nearly all transformer-related architectures.\n+ Multiple factors, such as packing efficiency, processing speed-up, load balancing, convergence behavior, are considered when analyzing the validity of packing algorithms.\n+ Clear writing and explanation; detailed background; helpful supplemental materials\n\nWeaknesses:\n- Incremental contribution. Bin packing is mature topic. While the specific context and constraints are different in the scope of this paper, it is unclear why many other existing bin packing algorithms cannot be applied (with reasonable modifications). The proposed two schemes are also very simple.\n- Results for SORT are a bit surprising and conflicting. Section 4 concludes that SORT “cause a major overhead that exceeds the benefits of avoiding the padding”, yet Section 1 mentions that sorted batching is being used in the “Faster Transformer , lingvo, fairseq, and RoBERTa”. The seems to imply that either the evaluation results are inaccurate,or SORT has other benefits that are not discussed explicitly/clearly in the paper.\n- Lack of supporting evidence for certain claims and not evaluating all parts of proposition thoroughly. For instance, on line 236, there is no provided data to support the claim that “the best speed-up is obtained with NNLSHP at depth 3”. Additionally, nearly no specifications for the training setup are provided, such as the specific GPU used. This makes the claim that the NNLSHP packing algorithm runs “out of memory for larger depth” on line 237 challenging to interpret. Also, a minor complaint is that Table 1 uses the notation >>100 and << 1.000; it would be more useful if actual numbers are provided (this is not a figure where very large/small data may not be represented well).\n", "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": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Reject