CoChat
Sign Up
PreprintCited by 1,063Topic ModelingAdvanced Neural Network ApplicationsMultimodal Machine Learning Applications

Generating Long Sequences with Sparse Transformers

Open access
Child, Rewon, Gray, Scott, Radford, Alec, Sutskever, Ilya·2019·arXiv
DOI 10.48550/arxiv.1904.10509arXiv 1904.10509
Open this paper in CoChat — free accountOpen PDF

Abstract

Transformers are powerful sequence models, but require time and memory that grows quadratically with the sequence length. In this paper we introduce sparse factorizations of the attention matrix which reduce this to $O(n \sqrt{n})$. We also introduce a) a variation on architecture and initialization to train deeper networks, b) the recomputation of attention matrices to save memory, and c) fast attention kernels for training. We call networks with these changes Sparse Transformers, and show they can model sequences tens of thousands of timesteps long using hundreds of layers. We use the same architecture to model images, audio, and text from raw bytes, setting a new state of the art for density modeling of Enwik8, CIFAR-10, and ImageNet-64. We generate unconditional samples that demonstrate global coherence and great diversity, and show it is possible in principle to use self-attention to model sequences of length one million or more.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.1904.10509

Cites

3 of 3 references verified0 citation errors · 0 not checkable

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • For large sequence lengths N, s is often set to N^{-1/2} or N^{-1} log N, resulting in Θ(N sqrt N) or Θ(N log N) IO complexity.

    “For large sequence lengths 𝑁 , 𝑠 is often set to 𝑁 1 2 [11] or 𝑁 1 log 𝑁 [3, 17, 92], resulting in Θ 𝑁 𝑁 or Θ 𝑁 log 𝑁 IO complexity.”

    From FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness (2022) · cites this paper as [11]

    The citation to Child et al. is attached to the logarithmic-complexity option. Instead, Section 4.3 (p. 4) chooses a stride close to √N, and Section 4.2 (p. 4) gives O(N√N) computation. The paper does not give the attributed Θ(N log N) IO complexity. (LLM, conf=0.85)

    Checked by a reasoning model — may be wrong.

    Experimental — accuracy not yet measured

  • Child et al. (2019) propose two sparse attention patterns with the property that overlapping layers yields a full-context model, but their best image architecture (Strided Sparse Transformer) requires custom sparse attention GPU kernels and cannot be easily implemented on other hardware such as TPUs.

    “Child et al. (2019) propose two sparse attention patterns with this property. However, the architecture they propose that works best for images (the Strided Sparse Transformer) requires custom sparse attention GPU kernels to implement a specific block-sparse variant of matrix-matrix-multiply. The model cannot be easily implemented on other hardware such as TPUs.”

    From Axial Attention in Multidimensional Transformers (2019) · cites this paper as Child et al., 2019

    Split into 2 atoms — 1 confirmed, 1 partially supported, 0 disputed, 0 misattributed, 0 unverifiable. Expand the claim to see per-atom verdicts.

    Experimental — accuracy not yet measured

  • Self-attention is remarkably effective at learning long-range dependencies between data dimensions, and neural networks incorporating self-attention are state-of-the-art on many tasks from language modelling and machine translation to image and video modelling.

    “Self-attention is remarkably effective at learning long-range dependencies between data dimensions and neural networks that incorporate self-attention in their designs are state-of-the-art on many tasks from language modelling and machine translation to image and video modelling (Parmar et al., 2018; Child et al., 2019).”

    From Axial Attention in Multidimensional Transformers (2019) · cites this paper as Child et al., 2019

    Split into 2 atoms — 1 confirmed, 1 partially supported, 0 disputed, 0 misattributed, 0 unverifiable. Expand the claim to see per-atom verdicts.

    Experimental — accuracy not yet measured

  • Existing autoregressive models either suffer from excessively large computational resource requirements for high-dimensional data, or make compromises in distribution expressiveness or ease of implementation to decrease resource requirements.

    “Existing autoregressive models either suffer from excessively large computational resource requirements for high dimensional data, or make compromises in terms of distribution expressiveness or ease of implementation in order to decrease resource requirements.”

    From Axial Attention in Multidimensional Transformers (2019) · cites this paper as Child et al., 2019

  • The lossless codelengths are better than the large estimates reported for energy based models and score matching using annealed importance sampling, but not competitive with other types of likelihood-based generative models.

    “Still, while our lossless codelengths are better than the large estimates reported for energy based models and score matching using annealed importance sampling [11], they are not competitive with other types of likelihood-based generative models [7].”

    From Denoising Diffusion Probabilistic Models (2020) · cites this paper as [7]

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

Flagged first, then by citations

Research works printed but not linked: 24

  1. Al-Rfou, R., Choe, D., Constant, N., Guo, M., and Jones, L. Character-level language modeling with deeper selfattention. arXiv preprint arXiv:1808.04444 , 2018. · arXiv
  2. Ba, J. L., Kiros, J. R., and Hinton, G. E. Layer normalization. arXiv preprint arXiv:1607.06450 , 2016. · arXiv
  3. Britz, D., Guan, M. Y., and Luong, M.-T. Efficient attention using a fixed-size memory representation. arXiv preprint arXiv:1707.00110 , 2017. · arXiv
  4. Chen, T., Xu, B., Zhang, C., and Guestrin, C. Training deep nets with sublinear memory cost. arXiv preprint arXiv:1604.06174 , 2016. · arXiv
  5. Chen, X., Mishra, N., Rohaninejad, M., and Abbeel, P. Pixelsnail: An improved autoregressive generative model. arXiv preprint arXiv:1712.09763 , 2017. · arXiv
  6. Chiu, C.-C. and Raffel, C. Monotonic chunkwise attention. arXiv preprint arXiv:1712.05382 , 2017. · arXiv
  7. 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.
  8. 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.
  9. He, K., Zhang, X., Ren, S., and Sun, J. Identity mappings in deep residual networks. arXiv preprint arXiv:1603.05027 , 2016. · arXiv
  10. Hendrycks, D. and Gimpel, K. Bridging nonlinearities and stochastic regularizers with gaussian error linear units. arXiv preprint arXiv:1606.08415 , 2016. · arXiv
  11. 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. · arXiv
  12. Jozefowicz, R., Vinyals, O., Schuster, M., Shazeer, N., and Wu, Y. Exploring the limits of language modeling. arXiv preprint arXiv:1602.02410 , 2016. · arXiv
  13. Kingma, D. P. and Dhariwal, P. Glow: Generative flow with invertible 1x1 convolutions. In Advances in Neural Information Processing Systems , pp. 10236-10245, 2018.
  14. Koutnik, J., Greff, K., Gomez, F., and Schmidhuber, J. A clockwork rnn. arXiv preprint arXiv:1402.3511 , 2014. · arXiv
  15. 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. · arXiv
  16. 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
  17. Menick, J. and Kalchbrenner, N. Generating high fidelity images with subscale pixel networks and multidimensional upscaling. arXiv preprint arXiv:1812.01608 , 2018. · arXiv
  18. 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. · arXiv
  19. Oord, A. v. d., Kalchbrenner, N., and Kavukcuoglu, K. Pixel recurrent neural networks. arXiv preprint arXiv:1601.06759 , 2016. · arXiv
  20. Parmar, N., Vaswani, A., Uszkoreit, J., Kaiser, Ł., Shazeer, N., and Ku, A. Image transformer. arXiv preprint arXiv:1802.05751 , 2018. · arXiv
  21. 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
  22. 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
  23. Sukhbaatar, S., Weston, J., Fergus, R., et al. End-to-end memory networks. In Advances in neural information processing systems , pp. 2440-2448, 2015.
  24. 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.

Cited by

Sorted by citations

Authors
Child, R., Gray, S., Radford, A., & Sutskever, I.
Venue
arXiv
Publisher
arXiv
Published
2019
ISSN
2331-8422 (ISSN-L)
DOI
10.48550/arxiv.1904.10509
arXiv
1904.10509
OpenAlex
W2940744433
Cited by
1,063
References
3
Citations by year
2026: 15 · 2025: 114 · 2024: 161 · 2023: 194 · 2022: 154 · 2021: 255 · 2020: 129 · 2019: 40 · 2018: 1
Type
posted content
Language
en
Open access
Licence
arxiv.org/licenses/nonexclusive-distrib/1.0/
Locations
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
Topics
  • Physical Sciences › Computer Science › Artificial Intelligence › Topic Modeling
  • Physical Sciences › Computer Science › Computer Vision and Pattern Recognition › Advanced Neural Network Applications
  • Physical Sciences › Computer Science › Computer Vision and Pattern Recognition › Multimodal Machine Learning Applications
Keywords
sparse transformer, long sequence generation, sparse factorization, quadratic complexity, memory-efficient training, unconditional image generation, density estimation, CIFAR-10

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review