LongNet — Dilated Attention

§ 1 · Premise

Quadratic attention versus billion-token sequences

Dense self-attention’s compute scales as $O(N^2 d)$ in sequence length $N$ and model dim $d$. At $N = 10^6$, $d = 4096$ that is $1.6 \cdot 10^{16}$ FLOPs per layer per head — already beyond what a single accelerator can hold the activations for; at $N = 10^9$ the per-layer attention matrix alone is $4 \cdot 10^{18}$ entries, six orders of magnitude past any plausible HBM budget. Ding et al. (arXiv 2307.02486) set the deliberately extreme target of training a Transformer at $N = 10^9$, and the question they ask is: which existing sparse pattern actually composes to that regime?

The 2020-era sparse-attention literature offered several patterns, each with a known limitation at the billion-token scale:

• Sliding window (Longformer, Beltagy et al. 2020, arXiv 2004.05150) attends to the last $W$ keys per query. $O(N W)$ compute, but the receptive field per layer is just $W$; reaching distance $N$ requires $\Omega(N / W)$ layers — for $N = 10^9$, $W = 10^3$ this is $10^6$ layers.
• Sparse Transformer (Child et al. 2019, arXiv 1904.10509) interleaves a local window with a global stride-$\sqrt{N}$ pattern: $O(N \sqrt{N})$ compute, two-hop reach. Better, but $10^9 \cdot \sqrt{10^9} \approx 3 \cdot 10^{13}$ ops is still painful.
• BigBird (Zaheer et al. 2020, arXiv 2007.14062) combines window + random + global tokens for $O(N)$ compute but inherits the same multi-hop reach problem and adds a heavy random-routing overhead.

LongNet’s wager is that the exponential generalization of stride-based attention — Sparse Transformer’s stride extended across a logarithmic number of dilation rates per head — is the right primitive: per-layer compute $O(N \cdot \log N)$, single-layer reachability of any past position at some resolution, and a distributed-training pattern that decomposes along the dilation axis. The contribution is the dilated-attention construction with its mixture-of-dilations softmax recombination, the proof of linear distributed scaling along the sequence dimension, and a demonstration at $N = 10^9$ tokens.

§ 2 · Derivation

From local windows to exponentially-dilated mixture attention

Starting point — local-window attention. With window size $w$ and stride $r = 1$, the per-query computation is

Compute per layer: $O(N w d_h)$. Receptive field per layer: $w$.

Step 1 — dilated indexing. Replace contiguous keys with a strided set. For dilation rate $r$ and segment size $w$, the keys attended to by query $t$ are

The query sees $w$ keys spaced $r$ apart, covering a span of $w \cdot r$ positions but sampling only $1/r$ of them. Mathematically this is gather-then-attend (§2.2, Eq. 2):

A single dilated head at rate $r$ has compute $O(w d_h)$ per query — same as local attention — but a per-layer receptive field of $w \cdot r$.

Step 2 — segment-and-shuffle implementation. A naive gather is hardware-hostile (strided loads break GPU memory coalescing). Ding et al. instead realize dilated attention by segment-and-shuffle (§2.2, Figure 3): split the sequence into segments of length $w \cdot r$, reshape each segment as a $w \times r$ matrix, and transpose so the resulting $r \times w$ blocks naturally group together the indices a query at stride $r$ would attend to. Standard dense attention then runs within each shuffled segment at length $w$. After attention, the inverse shuffle restores the sequence ordering. The overall pattern is mathematically equivalent to the gather formulation but executes as a sequence of contiguous-memory dense-attention kernels — fully Flash-Attention-compatible.

Step 3 — mixture of dilation rates. A single rate $r$ either covers too little reach (small $r$) or too coarsely (large $r$). LongNet mixes $k$ heads with geometrically-growing rates (§2.3):

with $\alpha > 1$ (Ding et al. use $\alpha = 2$) and segment sizes $w_i$ that may also grow. The configuration in Table 1 is $\{(w, r)\} = \{(2048, 1), (4096, 2), (8192, 4), (16384, 8), (32768, 16)\}$ — five dilated patterns covering distances $1 \to 32768 \cdot 16 = 524{,}288$ positions per layer.

The mixture is not a simple sum of softmaxes — that would over-count positions that fall in multiple patterns. LongNet’s combination weighs each pattern’s softmax denominator proportionally to its participation ($\S 2.3$, Eq. 4):

The $Z_i(t)$ are exactly the softmax denominators of each pattern’s local computation; the mixing weight is each pattern’s mass relative to the total. This is the standard online log-sum-exp recombination used in distributed attention, applied across dilation patterns rather than across sequence shards.

Why exponential dilations. Two reasons. First, one-layer reachability of every distance: for any distance $d \le N$, there exists a rate $r_i = 2^{i-1}$ with $r_i \le d \le w \cdot r_i$, so some head’s window covers position $t - d$. Second, logarithmic head count to cover linear range: $k = \lceil \log_\alpha(N / w_0) \rceil$ patterns cover the full sequence; for $\alpha = 2$, $N = 10^9$, $w_0 = 2048$ that is $k \approx 19$ patterns — feasible to allocate across heads of a normal multi-head layer (Ding et al. use $H = 12$ in their experiments, overloading some heads with multiple patterns).

Step 4 — cost accounting. Per layer, summing over patterns:

With $w_i = w_0$ constant, this is $O(N \cdot w_0 \cdot \log N \cdot d_h)$ — sub-quadratic by a factor of $N / (w_0 \log N)$. With growing $w_i = w_0 \beta^{i-1}$ as in Table 1, the cost becomes $O(N \cdot w_0 \cdot N \cdot d_h / (\alpha - 1))$, which is back to quadratic when $\beta = \alpha$. Ding et al.’s configuration uses $\beta = 2 = \alpha$ which formally is $\Theta(N^2)$ but with a $1/\alpha$ leading constant; the practical scaling at the $N$ they study is sub-quadratic because of the tiny constant and the distributed-training shape.

Memory: each pattern’s attention matrix is $N \times w_i$; the maximum is the largest $w_i = 32768$, giving an attention-matrix footprint of $N \cdot 32768$ entries per head — for $N = 10^9$ this requires sequence-parallel splitting across many accelerators, which is exactly what the distributed-training section ($\S 3$ of the paper) addresses.

Step 5 — distributed training along the dilation axis. Dilated attention’s special property is that each pattern is local within its shuffled segment (segment size $w_i$). This means the attention computation parallelises naturally along the sequence dimension: shard the sequence across $P$ devices, and each device runs dense attention within its own shard for the local-rate pattern, with cross-device communication only for the coarser-rate patterns. Ding et al. report near-linear scaling to $P = 32$ devices at $N = 10^9$ (Figure 5).

Parameter count. No new parameters introduced; dilated attention reuses standard $W_Q, W_K, W_V, W_O$. The only added “config” is the choice of $\{(w_i, r_i)\}$ per layer.

§ 3 · Reference implementation

Segment-and-shuffle dilated attention in pseudocode

# q, k, v: [B, N, H, d_h]
# patterns: list of (w_i, r_i) tuples assigned to subsets of heads

def longnet_layer(q, k, v, patterns, head_assign):
    # head_assign: list of head indices per pattern
    outs, Zs = [], []
    for (w, r), heads in zip(patterns, head_assign):
        qh, kh, vh = q[..., heads, :], k[..., heads, :], v[..., heads, :]
        # Segment-and-shuffle: reshape so that stride-r positions become contiguous
        N = q.shape[1]
        # 1) Pad to multiple of w*r
        # 2) Reshape [B, N/(w*r), w*r, H', d_h] -> [B, N/(w*r), r, w, H', d_h] (transpose)
        # 3) Flatten the r dimension into the batch: [B * N/(w*r) * r, w, H', d_h]
        qs, ks, vs = segment_shuffle(qh, w, r), segment_shuffle(kh, w, r), segment_shuffle(vh, w, r)

        # Standard dense attention within each shuffled block (Flash-Attn under the hood)
        out_i, lse_i = flash_attention(qs, ks, vs, return_lse=True)  # lse = log Z_i

        # Inverse-shuffle back to [B, N, H', d_h]
        out_i = inverse_shuffle(out_i, w, r)
        lse_i = inverse_shuffle(lse_i, w, r)
        outs.append(out_i)
        Zs.append(exp(lse_i))                         # [B, N, H', 1]

    # Mixture combination across patterns (log-sum-exp recombination)
    Z_total = sum(Zs)
    o = sum(Z_i * o_i for Z_i, o_i in zip(Zs, outs)) / Z_total

    # Re-merge heads back to [B, N, H, d_h]
    return scatter_heads(o, head_assign)

The sketch elides three production concerns: (1) causal masking — dilated indices need a causal-respecting gather that drops keys with index $> t$; (2) padding handling when $N$ is not a multiple of $w \cdot r$; (3) the actual heads-to-patterns assignment, which Ding et al. keep as a fixed configuration per layer rather than learned.

§ 4 · Empirical evidence

What is and isn’t known

Introducing paper (Ding et al. 2023).

1. Sub-quadratic scaling demonstrated. Trained MAGNETO Transformer backbones (Wang et al. 2022) with LongNet attention at sequence lengths $2$K, $8$K, $32$K, $128$K, $512$K, and $1$M, reporting near-flat wall-clock per token vs. growing-quadratically wall-clock for dense attention (Figure 4). Dense attention OOMs at $32$K on their hardware; LongNet continues smoothly.
2. Distributed scaling. The distributed implementation reaches near-linear throughput as training devices scale from 1 to 32 GPUs at fixed $N = 32$K (Figure 5), and the paper describes (though does not benchmark at full hardware) the procedure for scaling to $N = 10^9$ tokens.
3. Language modeling perplexity. On the Stack (Kocetkov et al. 2022, a code corpus) and Pile (Gao et al. 2020), LongNet at $N = 32$K trained for $300$B tokens reaches lower perplexity than dense attention at $N = 2$K trained for the same number of tokens (Table 2, Table 3). The improvement is modest ($\sim 0.05$ bpb on the Pile, $\sim 0.1$ bpb on the Stack) and is the result of the extended context, not an intrinsic property of the dilation pattern.
4. Receptive-field ablation. Removing the larger dilation rates (keeping only $r \le 4$) degrades perplexity by $\sim 0.15$ bpb on long-document subsets of the Pile (Table 4), confirming that the mixture’s long-range patterns contribute beyond what the small-$r$ patterns alone provide.

Independent follow-up.

• Survey coverage. LongNet appears in the standard long-context surveys (Pawar et al. 2024, arXiv 2402.02244, §3.4; Liu et al. 2024 “Understanding LLMs’ Long-Context Capabilities”, arXiv 2404.02060) as the canonical dilated-attention design.
• YOCO / FocusLLM (Sun et al. 2024, arXiv 2405.05254, §2) compares against LongNet as a representative sub-quadratic attention baseline and reports that on RULER-style long-context recall benchmarks, fixed-pattern sparse attention (LongNet, BigBird) underperforms the cache-compression family on multi-hop tasks despite competitive language-modeling perplexity — an extension of the dense-vs-sparse-attention quality gap Hsieh et al. document.
• Mixture-of-Sparse-Attention work. Subsequent work has refined the dilated pattern with learned routing rather than fixed strides — e.g., Native Sparse Attention (Yuan et al. 2025, arXiv 2502.11089) cites LongNet as the fixed-stride predecessor that motivates learned-routing alternatives.

Sensitivity studies — what is not publicly known. The introducing paper does not study (a) how the dilated-attention model behaves on needle-in-a-haystack benchmarks like RULER (Hsieh et al. 2024) or the LongBench / NIAH lineage — the paper’s evaluation is language-modeling perplexity, not retrieval accuracy; (b) how LongNet composes with subsequent positional-encoding rescaling techniques (the paper uses xPos / MAGNETO’s positional encoding, not RoPE); (c) whether the configuration optimal at $N = 32$K transfers to the $N = 10^9$ regime — the billion-token result is a system demonstration, not a downstream-task evaluation. I don’t know of an independent reproduction at $> 1$B model parameters; published LongNet results sit at $\sim 125$M–$2.7$B MAGNETO scales.

Production adoption. None recorded in this knowledge base. No frontier dense or MoE production decoder ships pure dilated attention as its long-context primitive — the production-frontier choice in the 32K–1M regime has converged on interleaved SWA + global attention (Gemma 3, Mistral) with positional-encoding rescaling on top (YaRN, NTK-aware extension). LongNet’s specific value is asymptotic: at the billion-token regime where $\log N$ heads materially outperform $\sqrt{N}$ patterns; that regime is not yet the production frontier.

@article{arxiv2307_02486,
  title  = {LongNet: Scaling Transformers to 1,000,000,000 Tokens},
  author = {Jiayu Ding and others (Microsoft Research)},
  year   = {2023},
  eprint = {2307.02486},
  archivePrefix = {arXiv},
  url    = {https://arxiv.org/abs/2307.02486}
}

@article{arxiv_2307_02486,
  title         = {LongNet: Scaling Transformers to 1,000,000,000 Tokens},
  author        = {Jiayu Ding et al. (Microsoft Research)},
  year          = {2023},
  eprint        = {2307.02486},
  archivePrefix = {arXiv},
  url           = {https://arxiv.org/abs/2307.02486}
}

{
  "id": "arxiv_2307_02486",
  "type": "article-journal",
  "title": "LongNet: Scaling Transformers to 1,000,000,000 Tokens",
  "author": [
    {
      "literal": "Jiayu Ding et al. (Microsoft Research)"
    }
  ],
  "issued": {
    "date-parts": [
      [
        2023
      ]
    ]
  },
  "URL": "https://arxiv.org/abs/2307.02486",
  "number": "2307.02486",
  "source": "arXiv"
}

TY  - JOUR
TI  - LongNet: Scaling Transformers to 1,000,000,000 Tokens
AU  - Jiayu Ding et al. (Microsoft Research)
PY  - 2023
JO  - arXiv
AN  - arXiv:2307.02486
UR  - https://arxiv.org/abs/2307.02486
ER  -