Elamur Research⌕
☰
home / papers / 2019 / Generating Long Sequences with Sparse Transformers

Generating Long Sequences with Sparse Transformers

Paper · 2019 · Rewon Child, Scott Gray, Alec Radford et al.

Summary

The classic Transformer scales poorly to long sequences because the time and memory required for self-attention grow quadratically with input length. The authors from OpenAI propose the Sparse Transformer, which replaces the full attention matrix with sparse factorized patterns. The strided pattern suits data with a periodic structure, such as images or music, while the fixed pattern suits text. This substitution reduces complexity to O(n√n), yet any position remains reachable from any other within a few attention steps. In addition, the authors modified the residual block and the initialization so that networks with hundreds of layers can be trained. To save memory, attention matrices are recomputed during the backward pass, and fast GPU kernels were written for training. The same architecture works with raw bytes of text, images, and audio. It set new density modeling records on Enwik8, CIFAR-10, and ImageNet 64x64 and generates samples with coherent global structure. The work showed that attention can be applied to sequences tens of thousands of steps long, and theoretically even up to a million. The idea of sparse attention later became one of the foundations for long-context models.

Key points

  • CIFAR-10: a strided model with 59M parameters and 128 layers achieves 2.80 bits per dim, compared with the previous record of 2.85 set by PixelSNAIL. The model also outperforms dense attention (2.82) and trains faster.
  • Enwik8: a fixed model with 95M parameters and 30 layers, with a context of 12,288, reaches 0.99 bits per byte. This is better than Transformer-XL 88M (1.03) and matches Transformer-XL 277M. The strided pattern performs poorly on text.
  • ImageNet 64x64: a model with 152M parameters and 48 layers achieves 3.44 bits per dim versus 3.52 for SPN. Training took 7 days on 64 V100 GPUs.
  • Long context: when the available context is increased during evaluation on Enwik8, compression improves monotonically from 0.9952 to 0.9908. The model therefore genuinely uses long-range dependencies.
  • Audio: on raw recordings of classical music (5 s, 12 kHz), the model achieves 1.97 bits per byte. Generated samples are up to 65,536 steps long.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Fields, topics and concepts

📚 Shelves 5The field of science this work belongs to (OpenAlex fields).Computer Science · 16,667 worksArtificial Intelligence · 16,194 worksArts and Humanities · 16,039 worksLanguage and Linguistics · 15,891 worksComputer Vision and Pattern Recognition · 2,869 works

Cite

Cite as Rewon Child, Scott Gray, Alec Radford and Ilya Sutskever. 2019. Generating Long Sequences with Sparse Transformers. arXiv:1904.10509.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.48550/arxiv.1904.10509 · arXiv 1904.10509

@misc{child2019generating,
  title = {{Generating Long Sequences with Sparse Transformers}},
  author = {Rewon Child, Scott Gray, Alec Radford and Ilya Sutskever},
  year = {2019},
  doi = {10.48550/arxiv.1904.10509},
  eprint = {1904.10509},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.48550/arxiv.1904.10509}
}

References

28 references, 5 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Al-Rfou, R., Choe, D., Constant, N., Guo, M., and Jones, L. Character-level language modeling with deeper self-attention. arXiv preprint arXiv:1808.04444, 2018. find
  2. Ba, J. L., Kiros, J. R., and Hinton, G. E. Layer normalization. arXiv preprint arXiv:1607.06450, 2016.
  3. Britz, D., Guan, M. Y., and Luong, M.-T. Efficient attention using a fixed-size memory representation. arXiv preprint arXiv:1707.00110, 2017. find
  4. Chen, T., Xu, B., Zhang, C., and Guestrin, C. Training deep nets with sublinear memory cost. arXiv preprint arXiv:1604.06174, 2016. find
  5. Chen, X., Mishra, N., Rohaninejad, M., and Abbeel, P. Pixelsnail: An improved autoregressive generative model. arXiv preprint arXiv:1712.09763, 2017. — [arXiv:1712.09763](https://arxiv.org/abs/1712.09763) find
  6. Chiu, C.-C. and Raffel, C. Monotonic chunkwise attention. arXiv preprint arXiv:1712.05382, 2017. find
  7. Dai, Z., Yang, Z., Yang, Y., Cohen, W. W., Carbonell, J., Le, Q. V., and Salakhutdinov, R. Transformer-xl: Language modeling with longer-term dependency. 2018. find
  8. Dieleman, S., van den Oord, A., and Simonyan, K. The challenge of realistic music generation: modelling raw audio at scale. In Advances in Neural Information Processing Systems, pp. 8000–8010, 2018. find
  9. Gehring, J., Auli, M., Grangier, D., Yarats, D., and Dauphin, Y. N. Convolutional sequence to sequence learning. arXiv preprint arXiv:1705.03122, 2017.
  10. Gruslys, A., Munos, R., Danihelka, I., Lanctot, M., and Graves, A. Memory-efficient backpropagation through time. In Advances in Neural Information Processing Systems, pp. 4125–4133, 2016. find
  11. He, K., Zhang, X., Ren, S., and Sun, J. Identity mappings in deep residual networks. arXiv preprint arXiv:1603.05027, 2016. find
  12. Hendrycks, D. and Gimpel, K. Bridging nonlinearities and stochastic regularizers with gaussian error linear units. arXiv preprint arXiv:1606.08415, 2016. find
  13. Huang, C.-Z. A., Vaswani, A., Uszkoreit, J., Shazeer, N., Hawthorne, C., Dai, A. M., Hoffman, M. D., and Eck, D. An improved relative self-attention mechanism for transformer with application to music generation. arXiv preprint arXiv:1809.04281, 2018. find
  14. Jozefowicz, R., Vinyals, O., Schuster, M., Shazeer, N., and Wu, Y. Exploring the limits of language modeling. arXiv preprint arXiv:1602.02410, 2016. find
  15. Kingma, D. P. and Dhariwal, P. Glow: Generative flow with invertible 1x1 convolutions. In Advances in Neural Information Processing Systems, pp. 10236–10245, 2018. find
  16. Koutnik, J., Greff, K., Gomez, F., and Schmidhuber, J. A clockwork rnn. arXiv preprint arXiv:1402.3511, 2014. — [arXiv:1402.3511](https://arxiv.org/abs/1402.3511) find
  17. Liu, P. J., Saleh, M., Pot, E., Goodrich, B., Sepassi, R., Kaiser, L., and Shazeer, N. Generating wikipedia by summarizing long sequences. arXiv preprint arXiv:1801.10198, 2018.
  18. Mehri, S., Kumar, K., Gulrajani, I., Kumar, R., Jain, S., Sotelo, J., Courville, A., and Bengio, Y. Samplernn: An unconditional end-to-end neural audio generation model. arXiv preprint arXiv:1612.07837, 2016. — [arXiv:1612.07837](https://arxiv.org/abs/1612.07837) find
  19. Menick, J. and Kalchbrenner, N. Generating high fidelity images with subscale pixel networks and multidimensional upscaling. arXiv preprint arXiv:1812.01608, 2018. — [arXiv:1812.01608](https://arxiv.org/abs/1812.01608) find
  20. Micikevicius, P., Narang, S., Alben, J., Diamos, G., Elsen, E., Garcia, D., Ginsburg, B., Houston, M., Kuchaev, O., Venkatesh, G., et al. Mixed precision training. arXiv preprint arXiv:1710.03740, 2017. find
  21. Oord, A. v. d., Kalchbrenner, N., and Kavukcuoglu, K. Pixel recurrent neural networks. arXiv preprint arXiv:1601.06759, 2016. find
  22. Parmar, N., Vaswani, A., Uszkoreit, J., Kaiser, Ł., Shazeer, N., and Ku, A. Image transformer. arXiv preprint arXiv:1802.05751, 2018. find
  23. Radford, A., Narasimhan, K., Salimans, T., and Sutskever, I. Improving language understanding by generative pre-training. URL https://s3-us-west-2.amazonaws. com/openai-assets/research-covers/language-unsupervised/language understanding paper. pdf, 2018. ↗
  24. Reed, S., Oord, A. v. d., Kalchbrenner, N., Colmenarejo, S. G., Wang, Z., Belov, D., and de Freitas, N. Parallel multiscale autoregressive density estimation. arXiv preprint arXiv:1703.03664, 2017. — [arXiv:1703.03664](https://arxiv.org/abs/1703.03664) find
  25. Salimans, T., Karpathy, A., Chen, X., and Kingma, D. P. Pixelcnn++: Improving the pixelcnn with discretized logistic mixture likelihood and other modifications. arXiv preprint arXiv:1701.05517, 2017. — [arXiv:1701.05517](https://arxiv.org/abs/1701.05517) find
  26. Sukhbaatar, S., Weston, J., Fergus, R., et al. End-to-end memory networks. In Advances in neural information processing systems, pp. 2440–2448, 2015. find
  27. Van Den Oord, A., Dieleman, S., Zen, H., Simonyan, K., Vinyals, O., Graves, A., Kalchbrenner, N., Senior, A., and Kavukcuoglu, K. Wavenet: A generative model for raw audio. CoRR abs/1609.03499, 2016.
  28. Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, Ł., and Polosukhin, I. Attention is all you need. In Advances in Neural Information Processing Systems, pp. 5998–6008, 2017.

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/child-2019-generating-long-sequences-sparse-transformers/