2021

Efficient Sequence Packing without Cross-contamination: Accelerating Large Language Models without Impacting Performance

Krell, Mario Michael, Kosec, Matej, Perez, Sergio P. et al.

Understand

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.

Built on

Near-optimal bin packing algorithms
Johnson, D. S · 1973
Earlier work this paper cites.
A 7160 theorem for bin packing
Johnson, D. S., and Garey, M. R · 1985
Earlier work this paper cites.
A Simple On-Line Bin-Packing Algorithm
Lee, C. C., and Lee, D. T · 1985
Earlier work this paper cites.
Computers and Intractability; A Guide to the Theory of NP-Completeness
Garey, M. R., and Johnson, D. S · 1990
Earlier work this paper cites.
Solving Least Squares Problems
Lawson, C. L., and Hanson, R. J · 1995
Earlier work this paper cites.
A fast non-negativity-constrained least squares algorithm
Bro, R., and De Jong, S · 1997
Earlier work this paper cites.
Extreme Value Distributions
Kotz, S., and Nadarajah, S · 2000
Earlier work this paper cites.
A branch-and-cut-and-price algorithm for one-dimensional stock cutting and two-dimensional two-stage cutting
Belov, G., and Scheithauer, G · 2006
Earlier work this paper cites.
Efficient parallel non-negative least squares on multi-core architectures
Luo, Y., and Duraiswami, R · 2011
Earlier work this paper cites.
Combinatorial Optimization
Korte, B., and Vygen, J · 2012
Earlier work this paper cites.
Enumeration of 166 billion organic small molecules in the chemical universe database gdb-17
Ruddigkeit, L., van Deursen, R., Blum, L. C., and Reymond, J.-L · 2012
Earlier work this paper cites.
Detailed analysis of putative genes encoding small proteins in legume genomes
Guillén, G., Diaz-Camino, C., Loyola-Torres, C., Aparicio-Fabre, R., Hernández-López, A., Díaz-Sánchez, M., and Sanchez, F · 2013
Earlier work this paper cites.
Quantum chemistry structures and properties of 134 kilo molecules
Ramakrishnan, R., Dral, P. O., Rupp, M., and von Lilienfeld, O. A · 2014
Earlier work this paper cites.
Librispeech: an asr corpus based on public domain audio books
Panayotov, V., Chen, G., Povey, D., and Khudanpur, S · 2015
Earlier work this paper cites.
SQuAD: 100,000+ questions for machine comprehension of text
Rajpurkar, P., Zhang, J., Lopyrev, K., and Liang, P · 2016
Earlier work this paper cites.
Attention is all you need
Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, u., and Polosukhin, I · 2017
Earlier work this paper cites.

Similar

Comparing ancient dna preservation in petrous bone and tooth cementum
Hansen, H. B., Damgaard, P. B., Margaryan, A., Stenderup, J., Lynnerup, N., Willerslev, E., and Allentoft, M. E · 2017
Cited alongside, same era.
Optimization Methods for Large-Scale Machine Learning
Bottou, L., Curtis, F. E., and Nocedal, J · 2018
Cited alongside, same era.
GLUE: A multi-task benchmark and analysis platform for natural language understanding
Wang, A., Singh, A., Michael, J., Hill, F., Levy, O., and Bowman, S · 2018
Cited alongside, same era.
Neural network acceptability judgments
Original
Warstadt, A., Singh, A., and Bowman, S. R · 2018
Cited alongside, same era.
BERT: Pre-training of deep bidirectional transformers for language understanding
Devlin, J., Chang, M. W., Lee, K., and Toutanova, K · 2019
Cited alongside, same era.
BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding
Devlin, J., Chang, M. W., Lee, K., and Toutanova, K · 2019
Cited alongside, same era.
Pre-training data creation script for BERT
Devlin, J., Chang, M. W., Lee, K., and Toutanova, K · 2019
Cited alongside, same era.
Dissecting the Graphcore IPU architecture via microbenchmarking
Original
Jia, Z., Tillman, B., Maggioni, M., and Scarpazza, D. P · 2019
Cited alongside, same era.
RoBERTa: A Robustly Optimized BERT Pretraining Approach
Liu, Y., Ott, M., Goyal, N., Du, J., Joshi, M., Chen, D., Levy, O., Lewis, M., Zettlemoyer, L., and Stoyanov, V · 2019
Cited alongside, same era.
Convergence analysis of distributed stochastic gradient descent with shuffling
Meng, Q., Chen, W., Wang, Y., Ma, Z. M., and Liu, T. Y · 2019
Cited alongside, same era.
fairseq: A fast, extensible toolkit for sequence modeling
Ott, M., Edunov, S., Baevski, A., Fan, A., Gross, S., Ng, N., Grangier, D., and Auli, M · 2019
Cited alongside, same era.
Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer
Raffel, C., Shazeer, N., Roberts, A., Lee, K., Narang, S., Matena, M., Zhou, Y., Li, W., and Liu, P. J · 2019
Cited alongside, same era.

Then

Language Models are Few-Shot Learners
Brown, T. 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., 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 · 2020
Later among the works it cites.
MLPerf: An Industry Standard Benchmark Suite for Machine Learning Performance
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 · 2020
Later among the works it cites.
v0.7 Results
MLCommons · 2020
Later among the works it cites.
Reference numbers for BERT un-padding results
NVIDIA · 2020
Later among the works it cites.
Transformers: State-of-the-art natural language processing
Wolf, T., Debut, L., Sanh, V., Chaumond, J., Delangue, C., Moi, 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 · 2020
Later among the works it cites.
Visual transformers: Token-based image representation and processing for computer vision, 2020
Wu, B., Xu, C., Dai, X., Wan, A., Zhang, P., Yan, Z., Tomizuka, M., Gonzalez, J., Keutzer, K., and Vajda, P · 2020
Later among the works it cites.
SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python
Virtanen, P., Gommers, R., Oliphant, T. E., Haberland, M., Reddy, T., Cournapeau, D., Burovski, E., Peterson, P., Weckesser, W., Bright, J., van der Walt, S. J., Brett, M., Wilson, J., Millman, K. J., Mayorov, N., Nelson, A. R. J., Jones, E., Kern, R., Larson, E., Carey, C. J., Polat, İ., Feng, Y., Moore, E. W., VanderPlas, 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 · 2020
Later among the works it cites.
Datasets
Wolf, T., Lhoest, Q., von Platen, P., Jernite, Y., Drame, M., Plu, J., Chaumond, J., Delangue, C., Ma, C., Thakur, A., Patil, S., Davison, J., Scao, T. L., Sanh, V., Xu, C., Patry, N., McMillan-Major, A., Brandeis, S., Gugger, S., Lagunas, F., Debut, L., Funtowicz, M., Moi, A., Rush, S., Schmidd, P., Cistac, P., Muštar, V., Boudier, J., and Tordjmann, A · 2020
Later among the works it cites.
Mathematica, Version 12.2
Wolfram Research Inc · 2020
Later among the works it cites.
Effective Transformer
ByteDance Inc · 2021
Closest in time.
Switch Transformers: Scaling to Trillion Parameter Models with Simple and Efficient Sparsity
Fedus, W., Zoph, B., and Shazeer, N · 2021
Closest in time.
Faster Transformer
NVIDIA · 2021
Closest in time.
XLA: Optimizing Compiler for Machine Learning
XLA, T · 2021
Closest in time.
Performance catalogue for BERT on Pytorch
NVIDIA · 2021
Closest in time.
Supplemental Material for “Efficient Sequence Packing without Cross-contamination: Accelerating Large Language Models without Impacting Performance’, 2022
Anonymous · 2022
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…