LIT-225: Generating Long Sequences with Sparse Transformers

Child et al. (2019) — ARXIV-1904.10509

Key takeaways

• The sliding window is one half of a factorization, and the paper is explicit that the other half is what makes it work. Causal attention is split across p = 2 heads whose union connects every pair of positions in at most p + 1 steps. The first head is the window — A_i^(1) = {t, ..., i} for t = max(0, i - l), with the stride l chosen close to sqrt(n) — and the second is what carries information out of it. A stack of purely local layers is named in the text as a softening of the connectivity criterion, a possibly useful inductive bias rather than the design.

• Two second halves, and which one you need is a property of the data. Strided — the second head attends to every l-th position — suits data with periodic structure, images and some music. Fixed — specific cells at the end of each block summarize it and are visible to every later block — is for data without that structure. On enwik8 strided attention failed (1.13 bpb against dense attention’s 1.00) and fixed recovered and passed it (0.99). On CIFAR-10 strided won. The window was never the part in dispute.

• Sparse was cheaper and better on two of three comparisons, which is the finding that does not follow from the complexity argument. Enwik8 at 12,288 context: dense 1.00 bpb at 1.31 s/iter, fixed 0.99 at 0.55. CIFAR-10: dense 2.82 at 0.54, strided 2.80 at 0.38. The authors offer two readings — a useful inductive bias, or an optimization problem in full attention — and decline to choose.

• State of the art on three density-modeling benchmarks at the time, from raw bytes with one architecture: enwik8 0.99 bpb at 95M parameters, matching a Transformer-XL with more than double the parameters; CIFAR-10 2.80 bits/dim; ImageNet 64×64 3.44. Sequences of over one million timesteps are shown to be trainable, at 3M parameters — the capacity/length trade is measured, not waved at: 4× the length costs roughly 8× the capacity.

• Three of the paper’s four contributions are not about attention at all, and two of them the field kept wholesale: the pre-activation residual block with residual-output weights initialized at 1/sqrt(2N) so the ratio of embedding scale to block scale is invariant in depth, and recomputing attention and feed-forward activations in the backward pass, which is what buys hundreds of layers at 16,384 context. The fourth is the block-sparse GPU kernel — a window computed as-is, a stride computed by transposing and then computing a window — and the note that the upper triangle is never materialized at all.

Standing in the anthology

This is the missing trunk under a branch the record already carries, in exactly DP-007’s shape. The reading list holds LIT-033 (Longformer, which names this paper as “the model with the most similar attention pattern to ours” and reports matching its enwik8 result), LIT-191 (attention sinks, whose streaming setting is a window), LIT-204 (Griffin), LIT-176 (native hybrid attention), LIT-208 and LIT-209 (NoPE global layers interleaved with windowed local ones), and LIT-143 (natively trainable sparse attention) — seven notes downstream of a window whose origin nobody had filed. It arrived here as an assumption seven times and never once as a claim.

One practice is filed from it and two are repointed at it.

SOTA-208 is its own recommendation — the window-plus-escape factorization, with the stride near sqrt(n) — filed Superseded rather than omitted. The record’s answer went to exact attention made fast (SOTA-086, SOTA-087) and then to sparsity that is learned rather than fixed (SOTA-138), and a superseded claim is still a claim: its enwik8 failure is the cleanest evidence the corpus has for what a hand-chosen pattern risks, which is the argument for its own successor.

Two practices were dated to papers that did not introduce them, and now carry introduced_by: pointing here (ADR-029). SOTA-087 — recompute attention in the backward pass — is this paper’s §5.4, three years before the FlashAttention note it is sourced to. This paper’s §5.2 also scales the residual-output projections, but it is not where SOTA-060’s factor starts: GPT-2, two months earlier, already scaled residual-layer weights by 1/sqrt(N), and Megatron-LM (LIT-022) is where the 1/sqrt(2N) form appears beside N(0, 0.02).

Two things in it are live arguments the record can use, and neither is the complexity result:

• The local window is not the design; the escape from it is. Every hybrid the record holds pairs a window with something global — designated tokens, emergent sinks, NoPE layers, linear-attention state, long-term slots. This paper states that pairing as a requirement rather than a convenience — the connectivity criterion is what makes it one — and its enwik8 result is the cleanest demonstration in the corpus of what happens when the escape is the wrong shape for the data. SOTA-153 and SOTA-176 are both instances of the pattern it names.

• Sparse beat dense on loss, in 2019, and the paper says it does not know why. The record’s later sparse-attention practices assert efficiency and treat parity on quality as the good case. An unexplained result in the opposite direction, unclaimed by its own authors, is worth having on file before anyone re-derives it.