Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes a simple and effective approach to accelerate the standard BERT pretraining by packing multiple sentences to a single training sample with fixed length, in order to reduce padding tokens and fully utilize the computation. The packing algorithms itself are very efficient and the overhead introduced in training (attention mask and loss calculation) is limited (below 5%). Experiments show that with hyperparameter adjustment, the BERT pretrained with packed data can result in nearly 2x speed up. Compared to the unpadding approach with custom computational kernels, the packing approach is inherently load-balanced and thus scale better to multiple distributed accelerators. Overall, I believe this is a quite general approach that can be applied to large-scale training with data having variable lengths.
main_review: This paper with its supplementary document is general well designed with solid experiments and analysis. To me, the idea of packing data with different lengths is not new, has perhaps arguably been tried by researchers or engineers in their working on accelerating BERT training, but not published. Even in the original code of BERT, the preprocessing step considers concatenating multiple segments into one a long sequence, although a significant portion of padding tokens are still introduced.

The paper can be further improved in the following aspects:
* Section 3.1 (packing algorithms) is hard to understand, especially to the readers with little background of packing algorithm. It will be better to have a formal definition of the problem, rather only explaining in words.
* Section 3.3 (calculating per-sequence loss) has the similar problem. It is unclear to me how the losses are computed and aggregated. It would be better to have some formula and figure to present the process, rather than the code snippet.
* In the packed data, how are the positional encodings configured? The positions of multiple sentence in one sample may have influence to the model behavior.
* The proposed method are only evaluated in terms of the pretraining loss, while in practice it may be more important to evaluated the performance of the model (packed BERT) finetuned on downstream tasks. I am wondering whether there will be differences with original BERT on certain tasks.
* “Empirically, a degradation of masked-language modelling accuracy on shorter sequences is indeed observed when not modifying the loss to account for packing”, what is exactly the drop of accuracy in the experiment?
* “packing could potentially eliminate the need for two phase pre-training of BERT.” It will be better to valid this argument, since the two stages pretraining could have the effective of curriculum learning which can speed the coveragence. 

Overall, I think the paper provide a simple and effective method to accelerate BERT training, although the idea could be employed by other practitioners. Some part of the paper is not easy to follow and could be improved with better formulation or graphs. Experiments are generally solid, but lack of experiments on the downstream tasks and analysis on the positional embedding.

limitations_and_societal_impact: Yes, the author has addressed this issue in the paper. I think this work have positive impact since it can save the carbon footprint in training the large-scale models.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: Authors found that at sequence length 512 padding tokens represent in excess of 50% of the Wikipedia dataset used for pretraining BERT (Bidirectional Encoder Representations from Transformers). Authors pre-train BERT-Large using the packed dataset,
demonstrating no loss of convergence and the desired 2x speed-up.
main_review: Authors showed that packing can be easily implemented without the need for any custom kernels while still providing a 2x speed-up. Additionally, we showed that any additional speed-ups resulting from dynamic un-padding approaches diminish for even moderate batch sizes or when additional accelerators are added. In contrast, packing is load-balanced and maintains the 2x throughput when
scaling to large numbers of accelerators.
limitations_and_societal_impact: Yes authors addressed the limitations and potential negative societal impact of their work. Failures in NLP can have a big impact on society; many technologies, such as Alexa, Siri, and Google Home, rely on them. Whilst any errors arising from our approach can be avoided, one potential source of error comes from the implementation.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper proposed two algorithms of packing (batching) variable-length sequences in training deep NLP models, SPFHP and NNLSHP. Experiment shows that these algorithms can accelerate BERT training by 2x compared with naive padding strategies and that they are also more scalable than un-padding strategies.
main_review: Padding and packing (batching) is an important detail in large-scale NLP model training, but it has long been ignored by many NLP researchers and practitioners. The topic of this paper is both innovative and highly practical. Two packing algorithms proposed by the authors are also very close to the optimal, so the author almost "solves" this problem entirely. The proposed algorithms only add little overhead to the whole training process, and they are also more scalable and flexible than un-padding methods. The paper also discussed how to tune hyperparameters given the new packing strategy to achieve good performance.

Still, I think there are still many problems in this paper. There are two major issues and two minor issues.

Surprisingly, **packing is not a problem in masked language model (BERT) pre-training**. The RoBERTa paper (https://arxiv.org/pdf/1907.11692v1.pdf) has talked about this problem in detail. Table 2 of the RoBERTa paper shows that the sentence-pair scheme used by the original BERT codebase is worse than "Full-Sentences" or "Doc-Sentences", where multiple contiguous sentences are packed into a single sequence, such that the total sequence length is at most 512 tokens. **Language pre-training never requires each sequence to be a single sentence**; instead, it can be a concatenation of an arbitrary number of contiguous sentences. Therefore, the discussions in Section 3.2 (attention masking) and Section 3.3 (calculating per-sequence loss) seem useless, since cross-contamination between contiguous sentences is not harmful but even beneficial (as is shown in the RoBERTa paper). Although the proposed strategies are perhaps useless in language pre-training, **they can still be useful in other NLP tasks**, where the training dataset is a noncontiguous set of variable-length sentences. These tasks are machine translation, sentence classification, QA tasks, and so forth.

However, in some of these tasks, **practitioners are already using packing strategies better than naive batching**. For example, the fairseq codebase (https://github.com/pytorch/fairseq/blob/f2146bdc7abf293186de9449bfa2272775e39e1d/fairseq/tasks/fairseq_task.py#L208) for machine translation uses following packing strategy:

1. Sort sentences in the training dataset w.r.t. their lengths.
2. Iterate over sentences in the sorted dataset and try to add sentences greedily into the current batch.
    - If the resulting batch has more than n_tokens (a preset hyperparameter), finish the current batch and put this sentence into a new batch. Otherwise, add the sentence to the current batch.
3. Pad all batches so that all sentences have the same length as the longest sentence in the batch. Since sentences in the same batch are contiguous sentences in the sorted dataset, they have similar lengths. Thus we will not end up adding too many padding tokens.
4. This batching strategy also prevents cross-contamination automatically (since different sentences are not even in the same sequence), and it is even easier to calculate the per-token loss.

Although this strategy is probably never published, it is widely used in many NLP projects (https://github.com/pytorch/fairseq#pre-trained-models-and-examples), especially machine translation (https://github.com/pytorch/fairseq/blob/master/examples/translation/README.md). Unfortunately, **the author of this paper ignores this extremely commonly used baseline**. Instead, the author compares their algorithms with *naive padding*. However, except for small downstream NLP tasks, naive padding is almost only used by the vanilla BERT codebase and some projects using the Huggingface *transformers* codebase, probably for compatibility with Google's TPU instead of efficiency.

Writing is one of the minor issues. The description of the algorithm and TensorFlow source codes are informative and clear. However, unlike other algorithm papers, this paper has no derivation of (sequential) time complexity, parallel time complexity, and space complexity of their algorithms.

Another minor issue is that the author fails to explain how they have chosen *the weight of 0.09 for all sequences of length 8* for NNLSHP. If these hyperparameters are manually tuned, it would be better to add a sensitivity analysis showing whether the efficiency depends on a specific choice of this hyperparameter.

To summarize, this paper chooses an interesting topic and tries to solve this problem instead of making incremental improvements. The proposed methods are efficient and scalable. However, the author tries to solve a non-existent problem in BERT pre-training, although they may still be helpful in other NLP tasks other than LM pre-training. Also, the author only compares the methods with the weakest baseline, ignoring a very commonly used strong baseline. Therefore, I think this paper needs to be reworked.
limitations_and_societal_impact: N/A
review_title: null

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

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

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

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

Decision: Reject